# 13.09.2023 [135. Candy]
Minimum candies count to satisfy condition: `ratings[i] < ratings[i-1]` must give more candies to `i-1`
13.09.2023
135. Candy hard
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/338
Problem TLDR
Minimum candies count to satisfy condition: ratings[i] < ratings[i-1]
must give more candies to i-1
Intuition
Let’s observe the example:
// 0 1 2 3 4 5 6 7 8
// 1 2 2 3 2 1 5 3 4
// 1 1 1 1 1 1 1 1 1
// 1 1 1 1 1
// 1
// 1 -> [0]
// 3 -> [2, 4]
// 6 -> [5, 7]
// 8 -> [7]
//
// 1 2 3 4 5 6 7 8 9
// 1 1 1 1 1 1 1 1 1
// 1 1 1 1 1 1 1 1
// 1 1 1 1 1 1 1
// 1 1 1 1 1 1
// 1 1 1 1 1
// 1 1 1 1
// 1 1 1
// 1 1
// 1
// 1 <- 2 <- 3 ...
We can look at this as a graph with nodes of siblings from higher rating to lower. Then the minimum number of candies is a maximum graph path length.
Approach
we can reuse
depth
value for each visited node
Complexity
Time complexity:
O(n)Space complexity:
O(n)
Code
fun candy(ratings: IntArray): Int {
val fromTo = mutableMapOf<Int, MutableList<Int>>()
for (i in 1..<ratings.size)
if (ratings[i] > ratings[i - 1])
fromTo.getOrPut(i) { mutableListOf() } += i - 1
else if (ratings[i] < ratings[i -1])
fromTo.getOrPut(i - 1) { mutableListOf() } += i
val depth = IntArray(ratings.size)
fun maxDepth(curr: Int): Int =
depth[curr].takeIf { it > 0 } ?:
(1 + (fromTo[curr]?.map { maxDepth(it) }?.maxOrNull() ?: 0))
.also { depth[curr] = it }
return ratings.indices.sumBy { maxDepth(it) }
}