Ninja And Theatre

Easy
0/40
profile
Contributed by
1 upvote
Asked in companies
MicrosoftGoogle inc

Problem statement

The lockdown is over, and the Ninja goes to see a movie. As the covid is not entirely over, Ninja decides to sit in a seat such that the distance between him and the closest person to him is maximized.

Given an array representing a row of ‘SEATS’, where ‘SEATS[i]’ = 1 represents a person sitting in the ith seat and ‘SEATS[i]’ = 0 represents the seat is empty, can you tell ninja the maximum possible distance to the closest person.

For example: 
You are given ‘SEATS’ = {1, 0, 1, 0 , 0, 0, 1}. The answer will be 2 because if the ninja sits on the ‘SEAT[4]’, then the person on ‘SEAT[2]’ or the person on ‘SEAT[6]’ will be at a maximum distance of 2. If the ninja sits on any other empty seat, the nearest person's distance will be less than 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains an integer ‘N’ representing the length of the ‘SEATS’ array.

The second line of each test case contains ‘N’ space-separated integers representing the ‘SEATS’ array.
Output Format: 
For each test case, print a single integer, representing the maximum possible distance to the closest person.

The output of each test case will be printed in a separate line.
Constraints: 
1 <= T <= 10 
1 <= N <= 5000
0 <= SEATS[I] <= 1

Time limit: 1 sec
Note: 
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Sample Input 1:
2
7
1 0 1 0 0 0 1
7
1 0 1 1 0 0 0
Sample Output 1:
2
3
Explanation:
For the first test case, The answer will be 2 because if the ninja sits on the ‘SEAT[4]’, then the person on ‘SEAT[2]’ or the person on ‘SEAT[6]’ will be at a maximum distance of 2.

For the second test case, the answer will be 3 because if the ninja sits on the ‘SEAT[6]’, then the person on ‘SEAT[3]’ will be at a maximum distance of 3.
Sample Input 2:
2
5
1 0 0 1 0
4
1 0 1 1
Sample Output 2:
1
1
Hint

Try to calculate the maximum possible difference in both directions.

Approaches (2)
Distance Arrays

In this approach, we will find the maximum possible distance to the left and right for every seat. We will create two arrays, ‘LEFT’ and ‘RIGHT’, where ‘LEFT[I]’ stores the maximum possible distance to the nearest person from ‘SEAT[I]’ in the left direction similarly  ‘RIGHT[I]’ stores the maximum possible distance to the nearest person from ‘SEAT[I]’ in the right direction. Now, the maximum possible distance to the nearest person from ‘SEAT[I]’ will be the minimum of ‘LEFT[I]’ and ‘RIGHT[I]’.

 

To construct ‘LEFT’ if ‘SEATS[I]’ is 1 set LEFT[I] as 0 otherwise ‘LEFT[I]’ will be ‘LEFT[I - 1]’ + 1. Similarly, To construct ‘RIGHT’ if ‘SEATS[I]’ is 1 set ‘RIGHT[I]’ as 0 otherwise ‘RIGHT[I]’ will be ‘RIGHT[I + 1]’ + 1.

 

We will find the maximum possible distance to the nearest person for every seat from 0 to ‘N’ - 1, and the maximum of them will be our final answer. 

 

Algorithm:

  • Initialize an integer array 'LEFT' for storing left distances.
  • Initialize an integer array 'RIGHT' for storing the right distances.
  • Set every value of 'LEFT' and 'RIGHT' as 'N'.
  • Iterate 'I' in 0 to 'N'
    • If 'SEATS[I]' = 1, set 'LEFT[I]' = 0.
    • Otherwise, if 'SEATS[I]' = 0 and 'I' > 0, set 'LEFT[I]' = 'LEFT[I]' + 1.
  • Iterate 'I' in 'N' - 1 to 0.
    • If 'SEATS[I]' = 1, set 'RIGHT[I]' = 0.
    • Otherwise, if 'SEATS[I]' = 0 and 'I' < 'N -1', set 'RIGHT[I]' = 'RIGHT[I]' + 1.
  • Initialize a variable 'ANS' to store the final answer.
  • Iterate 'I' in 0 to 'N'.
    • Update 'ANS'. Set 'ANS' as the maximum of 'ANS' and minimum of 'LEFT[I]' and 'RIGHT[I]'.
  • Finally, return 'ANS'.
Time Complexity

O(N), where ‘N’ is the length of the input array 'SEATS'.

 

We are iterating the input array at most two times, once to create the array, ‘LEFT’ and the other to create the array, ‘RIGHT’. We are iterating arrays, ‘LEFT’ and ‘RIGHT’ only once. Hence the overall time complexity is O(N).

Space Complexity

O(N), where ‘N’ is the length of the input array 'SEATS'.

 

The length of arrays, ‘LEFT’ and ‘RIGHT’ will be equal to the length of the input array i.e, ‘N’. Hence, the total time complexity will be O(N).

Code Solution
(100% EXP penalty)
Ninja And Theatre
Full screen
Console