CODEWITHSUNDEEP
pythonalgorithm
PhysicsMath
PhysicsMath

Reputation: 171

LeetCode Problem 135 Candy one-pass solution to find the number of candies given to each child

The problem (https://leetcode.com/problems/candy/description/) statement is as follows:

There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements:

(1) Each child must have at least one candy.

(2) Children with a higher rating get more candies than their neighbors.

(3) What is the minimum candies you must give?

e.g. Input: [1,0,2], Output: 5; Input: [1,2,2], Output: 4

In the problem discussion there is a proposal of one-pass solution:

https://leetcode.com/problems/candy/discuss/42770/One-pass-constant-space-Java-solution

while however only gives the total number of candies given out. I wish to modify the solution to output the number of candies given to each child. My attempt is as follows:

class Solution:
    def candy(self, ratings: List[int]) -> int:
        if not ratings: return 0
        n = len(ratings)
        res = [1]*n   # minimum 1 for each
        i = 1
        while i < n:
            if ratings[i-1] > ratings[i]:
                # check whether needed to add candy to current child 
                # based on right neighbor
                r = i   
                while r < n and ratings[r-1] > ratings[r]:
                    for j in range(i, r): res[j-1] += 1
                i = r
            else:
                # add candy to current child based on left neighbor
                if ratings[i-1] < ratings[i] and res[i-1] >= res[i]: res[i] = res[i-1] + 1
                i += 1
        print(res)

Could somebody help me to troubleshoot or provide a one-pass solution?

Upvotes: 1

Views: 2255

Answers (1)

DarrylG
DarrylG

Reputation: 17166

Here's a one-pass solution that shows the candies assigned to each child.

def candy(ratings):
  n = len(ratings)

  # Start off giving every child one candy
  # c is array of candies
  # desc_buf is the sequence of immediately preceding rating descents
  c, desc_buf = [1]*n, []

  curr_prev_pairs = list(zip(ratings[1:], ratings))
  for i, (curr, prev) in enumerate(curr_prev_pairs, start=1):
    if curr < prev:
      # rating less than previous
      if not desc_buf:
        # start new descent sequence
        desc_buf = [i-1]
      desc_buf.append(i)
      if i != n-1:
        continue

    if curr > prev:
      # increasing rating
      c[i] = c[i-1] + 1

    if desc_buf:
      for extra, idx in enumerate(desc_buf[::-1]):
        c[idx] = max(c[idx], extra + 1)
      del desc_buf[:]

  return c

ratings = [1, 0, 2]
print(candy(ratings))    # [2, 1, 2] (5 total)

ratings = [1, 2, 2]
print(candy(ratings))    # [1, 2, 1] (4 total)

Upvotes: 2

Related Questions