Candies
Prateek is a kindergarten teacher. He wants to give some candies to the children in his class. All the children stand in a line and each of them has a grade according to his or her performance in the class. Prateek wants to give at least one candy to each child. If two children are standing adjacent to each other, then the one with the higher rating must get more candies than the other. Prateek wants to minimize the total number of candies he must buy.

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.

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

Question

Candies

Prateek is a kindergarten teacher. He wants to give some candies to the children in his class. All the children stand in a line and each of them has a grade according to his or her performance in the class. Prateek wants to give at least one candy to each child. If two children are standing adjacent to each other, then the one with the higher rating must get more candies than the other. Prateek wants to minimize the total number of candies he must buy.

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.

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

Accepted Answer

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]

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

Here is the algorithm :

Create an array (say, ‘CANDIES’) of size ‘N’.
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.
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.
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.
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.
Create a variable (say, ‘ANS’) and initialise it to 0.
Run a loop from 0 to ‘N’ (say, iterator ‘i’) add ‘CANDIES’[i] to ‘ANS’.
Finally, return ‘ANS’.

Space Complexity: O(n)Explanation:

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)Explanation:

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).

Accepted Answer

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 :

Create an array (say, ‘CANDIES’) to store candies for each student and initialise it with 1.
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]
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]
Create a variable (say, ‘ANS’) to store total number of candies required and initialise it to 0.
Run a loop from 0 to ‘N’ (say, iterator ‘i’) and add ‘CANDIES’[i] to ‘ANS’.
Finally, return ‘ANS’.

Space Complexity: O(n)Explanation:

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)Explanation:

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).

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 :

Note :

Input format :

Output Format :

Note :

Constraints :

Top Think Future Technologies Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in Think Future Technologies Software Engineer