Traffic Lights

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
8 upvotes
Asked in company
Salesforce

Problem statement

There is a street of length X with positions numbered from 0 to X (0,1,…, ’X’). Initially, there are no traffic lights in these slots. Later ‘N’ sets of traffic lights are added to the street one after another. The ‘POS’ array tells the position of the ‘i’th light.

Your task is to calculate the length of the longest passage without traffic lights after each addition.

For example:

Given:- ‘X’ = 5 and ‘N’ = 2.
‘POS’[] = 3, 4
The output will be 3 and 3.
Initially, there are no lights, and we install a light at position three; therefore, there is a segment between the 3 and 6. 
Then we install a light at position four; therefore, the largest gap becomes between 0 to 3.
Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers, 'X' and ‘N’, where ‘X’ is the length of the road and ‘N’ is the number of lights.

The next line contains ‘N’ space-separated integers denoting the position of the ith light.

Output format :

For each test case, print a single line containing a single integer denoting the maximum gap for every light we install.

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 <= 10
1 <= N <= 2000
1 <= X <= 10 ^ 8
1 <= POS[i] <= X 

Where ‘T’ is the total number of test cases, ‘N’ is the number of lights we install, ‘X’ is the length of the road, and ‘POS[i]’ denotes the position of the 'i th' light.

Time limit: 1 sec.

Sample Input 1 :

2
5 2
3 4
6 3
4 5 1

Sample Output 1 :

3 3 
4 4 3

Explanation of the Sample Input 1:

For the first test case :  
The output will be 3 3.
Initially, there are no lights, and we install a light at position 3 therefore, there is a segment between the 3 and 6. 
Then we install a light at position 4; therefore, the largest gap becomes between 0 to 3.

For the second test case : 
The output will be 4 4 3.
Initially, there is no light. Then we install a light at position 4. Therefore the max gap becomes between 0 and 4.
Then we install a light at position 5, and the largest gap is still 0 to 4.
Then we install a light at position 1 then the largest gap is between 1 to 4, which is 3.

Sample Input 2 :

2
6 3
5 3 4
7 4
1 2 3 4

Sample Output 2 :

5 3 3 
6 5 4 3
Hint

Can you use a multiset to keep track of the distances of the adjacent traffic lights?

Approaches (2)
Using Set

The main idea is to use a set ‘LIGHTS’ and a multiset ‘DISTANCE’ to maintain the position of light and distance maintains all the distances. For a given position, find the next position of the light and the previous position of the light, and put it into the ‘DISTANCE’ set, and the end of the set contains the answer since the values are always sorted in increasing order.

 

  • Maintain a set ‘LIGHTS’ and multiset ‘DISTANCE’.
  • Push 0 and ‘X’ in the ‘LIGHT’ to mark polls.
  • For every position in the ‘POS’ array :
    • Find ‘GREATER_POS’, which is the upper_bound of  the current position from ‘LIGHTS.’
    • Find ‘SMALLER_POS’, which is the previous position of the ‘GREATER_POS’.
    • The answer is maximum value till now, which is the last position of the ‘DISTANCE’ set.
  • Maintain a vector ‘RES’, which contains the max gap till the ith position.
  • Return ‘RES’ as the final answer.
Time Complexity

O(N * log(X)), where ‘N’ is the number of lights, and ‘X’ is the length of the road.

 

Since we have to find the max gap for each light position and we have to query, and each query takes log(X) time. Therefore total net complexity is O(N * log(X)).

Space Complexity

O(N), where ‘N’ is the number of lights.

 

Since we are using set and multiset to keep track of elements extra space.

Code Solution
(100% EXP penalty)
Traffic Lights
Full screen
Console