[Solved] Candies Online Coding Interview Problem
[Solved] Candies Online Coding Interview Problem

[Solved] Candies Online Coding Interview Problem

Candies Online Coding Interview: Given an array ‘STUDENTS’ of size ‘N’ that contains the grades for each student, your task is to find what is the minimum number of candies Prateek must buy so that he can distribute them among his students according to the criteria given above.

Example :

Given students' ratings : [5, 8, 1, 5, 9, 4]. 
He gives the students candy in the following minimal amounts : [1, 2, 1, 2, 3, 1]. He must buy a minimum of 10 candies.

Note :

1. If two students having the same grade are standing next to each other, they may receive the same number of candies.
2. Every student must get at least a candy.

Candies Online Coding Interview Problem

Input Format :

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.

The first line of each test case contains an integer ‘N’ representing the number of students.

The second line of each test case contains 'N' space-separated integers representing the grades of each student.

Output Format :

For each test case, print the minimum number of candies required.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10^2
1 <= N <= 10^4
1 <= STUDENTS[i] <= 10^5

Time Limit : 1 sec

Sample Input 1 :

3
2
1 5
3
1 3 4
3
1 2 2

Sample Output 1 :

3
6
4

Explanation For Sample Input 1 :

(i) Optimal distribution will be 1 2
(ii) Optimal distribution will be 1 2 3
(iii) Optimal distribution will be 1 2 1 because for children with equal grades one child can have less candies

Sample Input 2 :

3
1
100
5
1 5 3 4 6
6
1 9 1 3 2 4

Sample Output 2 :

1
9
9

Explanation For Sample Input 2 :

(i) Optimal distribution will be 1
(ii) Optimal distribution will be 1 2 1 2 3
(iii) Optimal distribution will be 1 2 1 2 1 2

Solution

Approach 1

Brute Force

There can be four cases :

CASE 1: STUDENTS[i – 1]  > STUDENTS[i]  < STUDENTS[i + 1]

CASE 2: STUDENTS[i – 1]  < STUDENTS[i]  < STUDENTS[i + 1]

CASE 3: STUDENTS[i – 1]  > STUDENTS[i]  > STUDENTS[i + 1]

CASE 4: STUDENTS[i – 1]  < STUDENTS[i]  > STUDENTS[i + 1]

  1. For case 1, the ‘i’th child will get one candy.
  2. For case 2, the ‘i’th child will get ‘CANDIES’[i – 1] + 1 candies.
  3. For case 3, the ‘i’th child will get ‘CANDIES'[i + 1] + 1 candies.
  4. For case 4, the ‘i’th child will get MAX(‘CANDIES'[i – 1],’CANDIES'[i + 1]) + 1 candies.

Here is the algorithm :

  1. Create an array (say, ‘CANDIES’) of size ‘N’.
  2. Run a loop from 0 to ‘N’ (say, iterator ‘i’) over ‘STUDENTS’[i] :
    • If ‘STUDENTS’[i -1] ≥ ‘STUDENTS’[i] and ‘STUDENTS’[i] ≤ ‘STUDENTS’[i + 1], do ‘CANDIES’[i] = 1.
  3. Run a loop from 0 to ‘N’ (say, iterator ‘i’) over ‘STUDENTS’[i] :
    • If ‘STUDENTS’[i – 1] < ‘STUDENTS’[i] and ‘STUDENTS’[i] < ‘STUDENTS’[i + 1], do ‘CANDIES’[i] = ‘CANDIES’[i – 1] + 1.
  4. Run a loop from ‘N’ – 1 to 0 (say, iterator ‘i’) over ‘STUDENTS’[i] :
    • If ‘STUDENTS’[i – 1] ≥ ‘STUDENTS’[i] and ‘STUDENTS’[i] ≥ ‘STUDENTS’[i + 1], do ‘CANDIES’[i] = ‘CANDIES’[i + 1] + 1.
  5. Run a loop from 0 to ‘N’ (say, iterator ‘i’) over ‘STUDENTS’[i] :
    • If ‘STUDENTS’[i – 1] < ‘STUDENTS’[i] and ‘STUDENTS’[i] ≥ ‘STUDENTS’[i + 1], do ‘CANDIES’[i] = MAX(‘CANDIES'[i – 1], ‘CANDIES’[i + 1]) + 1.
  6. Create a variable (say, ‘ANS’) and initialise it to 0.
  7. Run a loop from 0 to ‘N’ (say, iterator ‘i’) add ‘CANDIES’[i] to ‘ANS’.
  8. Finally, return ‘ANS’.

Time Complexity

O(N), where ‘N’ is the size of the array.

We traverse the many times individually to calculate the number of candies. Hence, the overall time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the size of the array.

We use an array of size ‘N’ to store the candies for the students. Hence, the overall space complexity will be O(N).

/*
    Time Complexity : O(N)
    Space complexity : O(N)
    
    Where N is the number of elements in array
*/

#include <cstring>
#include <limits.h>
int requiredCandies(vector < int > &students) {

        int n = students.size();
        int grades[n + 2];

        // Initializing 1st element to max integral value.
        grades[0] = INT_MAX;

        // Initializing last element to max integral value.
        grades[n + 1] = INT_MAX;

        for (int i = 1; i <= n; i++){
            grades[i] = students[i - 1];
        }

        int candies[n + 1];

        // Initializing all elements of the candies list with 0.
        memset(candies, 0, n+1);

        // Case 1 of the logic.
        for (int i = 1; i <= n; i++) {
            if (grades[i - 1] >= grades[i] && grades[i] <= grades[i + 1]) {
                candies[i] = 1;
            }
        }

        // Case 2 of the logic.
        for (int i = 1; i <= n; i++) {
            if (grades[i - 1] < grades[i] && grades[i] <= grades[i + 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // Case 3 of the logic (**NOTE - Here the traversal is reversed!).
        for (int i = n; i >= 1; i--) {
            if (grades[i - 1] >= grades[i] && grades[i] > grades[i + 1]) {
                candies[i] = candies[i + 1] + 1;
            }
        }

        // Case 4 of the logic.
        for (int i = 1; i <= n; i++) {
            if (grades[i - 1] < grades[i] && grades[i] > grades[i + 1]) {
                candies[i] = max(candies[i - 1], candies[i + 1]) + 1;
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += candies[i];
        }
        return ans;
    }

/*
	Time Complexity : O(N)
	Space complexity : O(N)
	
	Where N is the number of elements in array
*/

public class Solution {
    public static int requiredCandies(int[] students) {

        int n = students.length;
        int grades[] = new int[n + 2];

        // Initializing 1st element to max integral value.
        grades[0] = Integer.MAX_VALUE;

        // Initializing last element to max integral value.
        grades[n + 1] = Integer.MAX_VALUE;

        for (int i = 1; i <= n; i++) {
            grades[i] = students[i - 1];
        }

        int candies[] = new int[n + 1];

        // Case 1 of the logic.
        for (int i = 1; i <= n; i++) {
            if (grades[i - 1] >= grades[i] && grades[i] <= grades[i + 1]) {
                candies[i] = 1;
            }
        }

        // Case 2 of the logic.
        for (int i = 1; i <= n; i++) {
            if (grades[i - 1] < grades[i] && grades[i] <= grades[i + 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // Case 3 of the logic (**NOTE - Here the traversal is reversed!).
        for (int i = n; i >= 1; i--) {
            if (grades[i - 1] >= grades[i] && grades[i] > grades[i + 1]) {
                candies[i] = candies[i + 1] + 1;
            }
        }

        // Case 4 of the logic.
        for (int i = 1; i <= n; i++) {
            if (grades[i - 1] < grades[i] && grades[i] > grades[i + 1]) {
                candies[i] = Math.max(candies[i - 1], candies[i + 1]) + 1;
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += candies[i];
        }
        return ans;
    }
}

'''
	Time Complexity : O(N)
	Space complexity : O(N)
	
	Where N is the number of elements in array.
'''

import sys

def requiredCandies(students):
    n = len(students) 
    grades = [0] * (n + 2)

    # Initializing 1st element to max integral value.
    grades[0] = sys.maxsize 

    # Initializing last element to max integral value.
    grades[n + 1] = sys.maxsize 
    
    for i in range(1, n + 1):
        grades[i] = students[i - 1]
    
    # Initializing all elements of the candies list with 0.
    candies = [0] * (n + 1)

    # Case 1 of the logic.
    for i in range(1, n + 1):
        if grades[i - 1] >= grades[i] <= grades[i + 1]:
            candies[i] = 1

    # Case 2 of the logic.
    for i in range(1, n + 1):
        if grades[i - 1] < grades[i] <= grades[i + 1]:
            candies[i] = candies[i - 1] + 1

    # Case 3 of the logic (**NOTE - Here the traversal is reversed!).
    for i in range(n, -1, -1):
        if grades[i - 1] >= grades[i] > grades[i + 1]:
            candies[i] = candies[i + 1] + 1

    # Case 4 of the logic.
    for i in range(1, n + 1):
        if grades[i - 1] < grades[i] > grades[i + 1]:
            candies[i] = max(candies[i - 1],candies[i + 1]) + 1

    ans = 0
    for i in range(1, n + 1):
        ans += candies[i]

    return ans

Approach 2

Linear Time

We can iterate through the array of scores of student and assign a value of candy to each student depending upon his score. If his score is greater than the previous student in line, he will get a candy more than the previous student. Same goes for the student next in line.

Here is the algorithm :

  1. Create an array (say, ‘CANDIES’) to store candies for each student and initialise it with 1.
  2. Run a loop from 1 to ‘N’ (say, iterator ‘i’), if ‘STUDENTS’[i] is less than ‘STUDENTS’[i – 1] :
    • Update ‘CANDIES’[i] to ‘CANDIES’[i] + ‘CANDIES’[i – 1]
  3. Run a loop from ‘N’ – 2 to 0 (say, iterator ‘i’), if ‘STUDENTS’[i] is greater than ‘STUDENTS’[i + 1] and ‘CANDIES’[i] is smaller than ‘CANDIES’[i + 1] + 1:
    • Update ‘CANDIES’[i] to ‘CANDIES’[i] + ‘CANDIES’[i + 1]
  4. Create a variable (say, ‘ANS’) to store total number of candies required and initialise it to 0.
  5. Run a loop from 0 to ‘N’ (say, iterator ‘i’) and add ‘CANDIES’[i] to ‘ANS’.
  6. Finally, return ‘ANS’.

Time Complexity

O(N), where ‘N’ is the size of the array.

We traverse the 3 times individually to calculate the number of candies. Hence, the overall time complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the size of the array.

We use an array of size ‘N’ to store the candies for the students. Hence, the overall space complexity will be O(N).

/*
    Time Complexity : O(N)
    Space complexity : O(N)
    
    Where N is the number of elements in the array.
*/

int requiredCandies(vector < int > &students) {

    int n = students.size();
    int candies[n + 1];
    for (int i = 0; i <= n; i++) {
        candies[i] = 1;
    }
    
    for (int i = 1; i < n; i++) {
        if (students[i] > students[i - 1]) {
            candies[i] += candies[i - 1];
        }
    }

    // Second pass, give candies to the left.
    for (int i = n - 2; i >= 0; i--) {

        /*
            This time, we need to consider max{candies[i], candies[i+1]+1}.
            Since we don't know whether the ascending or descending trend is larger.
        */
        if (students[i] > students[i + 1] && candies[i] < candies[i + 1] + 1) {
            candies[i] = candies[i + 1] + 1;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += candies[i];
    }
    return ans;
}
/*
	Time Complexity : O(N)
	Space complexity : O(N)
	
	Where N is the number of elements in the array.
*/

public class Solution {
    public static int requiredCandies(int[] students) {

        int n = students.length;
        int candies[] = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            candies[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            if (students[i] > students[i - 1]) {
                candies[i] += candies[i - 1];
            }
        }

        // Second pass, give candies to the left.
        for (int i = n - 2; i >= 0; i--) {

            /*
            	This time, we need to consider max{candies[i], candies[i+1]+1}. Since we
            	don't know whether the ascending or descending trend is larger.
            */
            if (students[i] > students[i + 1] && candies[i] < candies[i + 1] + 1) {
                candies[i] = candies[i + 1] + 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += candies[i];
        }
        return ans;
    }

}

'''
	Time Complexity : O(N)
	Space complexity : O(N)
	
	Where N is the number of elements in the array.
'''

def requiredCandies(students):

    n = len(students)

    # Initializing candies list with all values equal to 1 (since each child would get atleast 1 candy).
    candies = [1] * (n + 1) 

    # Assigning candies to the child with bigger rating from left to right.
    for i in range(1, n):
        if students[i] > students[i - 1]:
            candies[i] += candies[i - 1]

    # Assigning candies to the child with bigger rating from right to left.
    for i in range(n - 2, -1, -1):
        if students[i] > students[i + 1] and candies[i] < (candies[i + 1] + 1):
            candies[i] = candies[i + 1] + 1

    ans = 0
    for i in range(n):
        ans += candies[i]

    return ans

Happy Learning – If you require any further information, feel free to contact me.

Share your love
Saurav Hathi

Saurav Hathi

I'm currently studying Bachelor of Computer Science at Lovely Professional University in Punjab.

📌 Nodejs and Android 😎
📌 Java

Articles: 444

Leave a Reply

Your email address will not be published. Required fields are marked *

You May Also Like