Coding Essentials 101

Hya Hoo! This is Aman khan Roohani again, This time I’ve come up with a very innovative approach of explaining you how I approached a coding problem, passed some test cases, but still was unable to solve it.

After having a look on the solution after 3 days of trying, I finally got where I was going wrong, and how near I was to the solution, I was very glad when I compared my solution to the accepted one as some of the main logic behind the problem was what I intercepted it to be. But still i wasn’t able to get the solution. Why?

let’s understand first what was the problem.

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors [i-1] and [i+1].

Return the minimum number of candies you need to have to distribute the candies to the children.

Examples:

List<int> ratings = [1,0,2];

for i=0 by default 1 assigned
for i=1 0<1 so 1 assigned
for i=2 2>0 so 2 assigned (1+1)

List<int> ratings = [1,2,87,87,2,1];

for i=0 by default 1 assigned
for i=1 2<1 so (1+1) 2 assigned
for i=2 87>2 so (2+1) 3 assigned
for(i=3 87=87 but here 87>(i+1) which is greater than (i+2)
so w eagain have to ierate from (ratings.length-1)to 87
so we get 1,2,3 respectively so i=3 is assigned 3

output is 1+2+3+3+2+1 = 12

To approach this problem I started with this method:

public int candy(int[] ic) {
    List<Integer> oc = new ArrayList<Integer>(Collections.nCopies(ic.length, 0));
         
      
        for(int i=0;i< ic.length;i++){

          if(i== 0){
            if(ic[i] > ic[i+1]){
              oc.set(i+1,1);
              oc.set(i,(oc.get(i+1)+1));
            }
            else{
              oc.set(i,1);
            }
          }

          else if(i == ic.length-1){
             if(ic[i] > ic[i-1]){
              oc.set(i,(oc.get(i-1)+1));
            }
            else if(ic[i] < ic[i-1]){
              oc.set(i,1);
              for(int j=i+1;j< ic.length; j--){
                if(ic[j] > ic[j-1]){
                  oc.set(j,(oc.get(j-1)+1));
                }
              }
            }
            else{
              oc.set(i,1);
            }
          }

          else{
            if(ic[i] > ic[i+1] && ic[i] < ic[i-1]){
              oc.set(i,(oc.get(i+1)+1));
              oc.set(i-1,(oc.get(i)+1));
          }
          else if(ic[i] > ic[i-1]){
            oc.set(i,(oc.get(i-1)+1));
          }
          else if(ic[i] < ic[i-1]){
            oc.set(i,1);
          }
          else if(ic[i] < ic[i+1] && ic[i] > ic[i-1]){
              oc.set(i,(oc.get(i-1)+1));
              oc.set(i+1,(oc.get(i)+1));
          }
          else if(ic[i] == ic[i+1] && ic[i] == ic[i-1]){
              oc.set(i,1);
          }
          else if(ic[i] == ic[i-1] && ic[i] > ic[i+1]){
              oc.set(i,(oc.get(i+1)+1));
          }
          else{
            oc.set(i,1);
          }
          }
        
        }
         Integer[] arr = new Integer[oc.size()];
 
        // ArrayList to Array Conversion
        for (int i = 0; i < oc.size(); i++)
            arr[i] = oc.get(i);

        int s = sum(arr, arr.length);
        return s;
    }

But as it is shown when i tried to handle all the conditions using a singular array and setting values according to conditions, so many conditions emerged and it created a hoch-poch.

Also Not all the test cases passed due to this, because they were tailored for the short term solution only.

Although my logic check was correct. I ddn’t think of all conditions and problems it might craete on different conditions.

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] left = new int[n];
        Arrays.fill(left,1);
        for(int i=1; i<n; i++){
            if(ratings[i] > ratings[i-1]) left[i] = left[i-1]+1;      
        }
        int[] right = new int[n];
        Arrays.fill(right,1);
        for(int i=n-2; i>=0; i--){
            if(ratings[i] > ratings[i+1]) right[i] = right[i+1]+1;
        }
        int totalCandies = 0;
        for(int i=0; i<n; i++){
            totalCandies += Math.max(left[i],right[i]);
        }
        return totalCandies;
    }
}

A proper solution which I found was create two new arrays which would traverse from left to right and vic versa checking the same conditions and then return the total candies by returning sum of max candies found by comparing two arrays with each other at the end.

Please let me know if you also can relate to sloving problems this way and it clogs your mind. this happened with me. Let me know if this happened with u too by giving a clap to this story.