Last Updated: 23 Oct, 2021
Ninja And Theatre
Easy
Asked in companies
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.
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.
Approaches
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'.
In this approach, we will use two pointers to keep track of last seen 1 and current 1. The pointer ‘LEFT’ will store the position of the last seen 1, and ‘RIGHT’ will store the position of the current 1 if found. The answer for this state will be '(RIGHT - LEFT)/2'. After finding answer for any state we will set ‘LEFT’ to ‘RIGHT’. We will traverse the complete ‘SEATS’ array and update ‘ANS’ for all such states.
If the ‘LEFT’ is -1(We initialized ‘LEFT’ with -1), then this state’s answer will be ‘RIGHT’ because if ‘LEFT’ is -1, it means this is the first time we see any 1. So, the maximum distance to the closest person will be when we sit on the first seat.
Similarly, if the last seat is empty i.e., ‘SEATS[‘N’ - 1]’ is 0, we need to check if we sit on the last seat will result in the maximum possible distance to the closest person. The answer for this state will be ‘N’ - 1 - ‘LEFT’ because distance will be counted from the last seen 1 and (-1) because of (0-based indexing).
Algorithm:
- Initialize a variable 'ANS' to store the final answer.
- Initialize left pointer 'LEFT' with value -1.
- Iterate 'RIGHT'(right pointer) from 0 to n
- If 'SEATS[RIGHT]' is 0, continue.
- If 'LEFT' is -1, set 'ANS' as the maximum of 'ANS' and 'RIGHT'.
- Otherwise, set 'ANS' as maximum of 'ANS' and '(RIGHT - LEFT)/2'.
- Set 'LEFT' to 'RIGHT'
- If 'SEATS[N - 1] is 0, set 'ANS' as as maximum of 'ANS' and 'N - 1 - LEFT'.
- Finally, return 'ANS'.
Similar problems