LeetCode 135.Candy Problem

LeetCode 135.Candy Problem

Publish Date: Feb 23
0 0

I tackled LeetCode 135 (Candy) and shared my solution in a Medium blog, breaking down the two-pass strategy for optimal candy distribution..
Although I have shared the solution approach on the Medium however I will share the psuedo-code/algorithm here

function candy(ratings: array of integers): integer
  if length(ratings) is 1 then
    return 1

  size = length(ratings)
  left = array of integers of size 'size'
  right = array of integers of size 'size'

  left[0] = 1
  right[size - 1] = 1

  // Left to Right pass
  for i from 1 to size - 1:
    if ratings[i] > ratings[i - 1] then
      left[i] = left[i - 1] + 1
    else
      left[i] = 1

  // Right to Left pass
  for i from size - 2 down to 0:
    if ratings[i] > ratings[i + 1] then
      right[i] = right[i + 1] + 1
    else
      right[i] = 1

  sum = 0
  for i from 0 to size - 1:
    sum = sum + max(left[i], right[i])

  return sum
Enter fullscreen mode Exit fullscreen mode

Two Passes: traverse the children twice, once left-to-right, then right-to-left.
Compare with its next/prev: In each pass, compare a child's rating to their immediate neighbor. If higher, they get one more candy than the neighbor. Otherwise, they get one candy.
Maximum Candies: For each child, keep the higher candy count from the two passes.
Total Sum: Add up all the individual maximum candy counts to get the final result.

To read the full blog-
Medium/Leetcode_135_

Comments 0 total

    Add comment