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_

Image of Datadog

How to Diagram Your Cloud Architecture

Cloud architecture diagrams provide critical visibility into the resources in your environment and how they’re connected. In our latest eBook, AWS Solution Architects Jason Mimick and James Wenzel walk through best practices on how to build effective and professional diagrams.

Download the Free eBook

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay