LeetCode Entry

135. Candy

13.09.2023 hard 2023 kotlin

Minimum candies count to satisfy condition: ratings[i] < ratings[i-1] must give more candies to i-1

135. Candy hard blog post substack image.png

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) }
    }