DEV Community

Md. Abir Hasan
Md. Abir Hasan

Posted on

LeetCode 135.Candy Problem

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_

Top comments (0)