NINJAS GARDEN

Easy
0/40
Average time to solve is 10m
47 upvotes
Asked in company
IBM

Problem statement

Nowadays ninja develops an interest in gardening. He wants to grow flowers in his garden. So he makes his garden in the form array-like there is an ‘N’ number of slots in the garden. Ninja has grown special flowers that have unique properties like ‘N’ flowers will bloom one by one in N days. On each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

So your task is to return on which day there exists two flowers in the status of blooming, and also the number of flowers between them is K and these flowers are not blooming.

You will be provided with an array of ‘FLOWERS’ consisting of a number from 1 to N. Each number in the array represents the place where the flower will open on that day and an integer ‘K’.

For example, FLOWERS[i] = X means that the unique flower that blooms at day ‘i’ will be at position X, where i and X will be in the range from 1 to N.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains two space-separated integers ‘N’ and ‘K’ denoting the size of the ‘flowers’ array and the integer ‘K’.

The next line contains ‘N’ space-separated integers denoting the values of elements of the ‘FLOWERS’ array.

Output Format:

For each test case, print a single line containing a single integer denoting the day. If there are multiple answers, choose the smallest, if there isn't such day, output -1.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 5000
1 <= FLOWERS[i] < 10 ^ 4

Where ‘T’ is the number of test cases, ‘N’ is the size of an array, and ‘FLOWERS[i] = X’ represents that the unique flower that blooms at day ‘i’ will be at position X.

Time Limit: 1 sec.

Sample Input 1:

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

Sample Output 1:

2
-1

Explanation for sample input 1:

Test Case 1:
For the first test case on day 2, the first and third flowers are blooming and there is one flower that is not blooming so we return ‘2’ as our answer.

Test Case 2:
For this test case, the first two flowers are open and next to each other. So for this test case, no day exists for which our required condition satisfies so we return ‘-1’.

Sample Input 2:

1
5 2
1 4 2 3 5

Sample Output 2:

2

Explanation of sample input 2:

For this test case on day 2, the first and fourth flowers are blooming and there are 2 flowers in between them that are not blooming.
Hint

Can you check each and every position?

Approaches (3)
Brute Approach

The idea here is to go to every position and check for the given condition. If at any position our condition becomes true we return that day as the answer.


 

Algorithm:

  • Initialize an array ‘dayOfFlowerBloomed’ to store days on which each flower will bloom.
  • Traverse the days array with i starting from zero and update the array as dayOfFlowerBloomed[flower[i]] = i + 1.
  • Set result as INT_MAX
  • Traverse the array again. Store the left and right values with k slots between 2 variables and find it maximum.
  • At each step traverse from 1 to K and check if dayOfFlowerBloomed[i + j] is less than the maximum value, break the inner loop, and set done false.
  • If the done is true, set the ans as the maximum value.
  • If the ans is equal to INT_MAX return -1 else return ans.
Time Complexity

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

 

As we are using two nested loops for iterating the given array.

Space Complexity

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

 

As we are storing days which takes extra space

Code Solution
(100% EXP penalty)
NINJAS GARDEN
Full screen
Console