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
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_
Top comments (0)