Skip to main content
Talentd

Minimize the Maximum Waiting Time at Synchronized Traffic Lights - Solution & Explanation

MediumArrayGreedy9 min read
Practice this problem

Problem Statement

You are given an integer period and an integer array lights, where lights[i] is the duration, in seconds, of the green phase of the ith traffic light.

At time 0, every traffic light starts at the beginning of its green phase. Their cycles are synchronized: every traffic light starts a new cycle at the same time, and every cycle lasts exactly period seconds. Therefore, the red phase of the ith traffic light lasts for period - lights[i] seconds.

You are also given an integer array arrivalTime, where arrivalTime[j] is the arrival time, in seconds, of the jth car.

Each car must be assigned to exactly one traffic light. Multiple cars may be assigned to the same traffic light. Any number of cars may cross the same traffic light simultaneously while it is green. Cars do not block or delay one another.

For a car j assigned to the ith traffic light, let r = arrivalTime[j] % period. If r < lights[i], its waiting time is 0. Otherwise, its waiting time is period - r.

The penalty of an assignment is the maximum waiting time among all cars.

Return an integer denoting the minimum possible penalty.

 

Example 1:

Input: period = 8, lights = [2,3], arrivalTime = [2,5,8,11]

Output: 5

Explanation:

One optimal solution is:

  • Assign arrivalTime[0] to the traffic light with lights[1] = 3. Here, r = 2 % 8 = 2. Since 2 < 3, the waiting time is 0.
  • Assign arrivalTime[1] to the traffic light with lights[0] = 2. Here, r = 5 % 8 = 5. Since 5 >= 2, the waiting time is 8 - 5 = 3.
  • Assign arrivalTime[2] to the traffic light with lights[0] = 2. Here, r = 8 % 8 = 0. Since 0 < 2, the waiting time is 0.
  • Assign arrivalTime[3] to the traffic light with lights[0] = 2. Here, r = 11 % 8 = 3. Since 3 >= 2, the waiting time is 8 - 3 = 5.

The penalty of this assignment is 5, which is the minimum possible. Other optimal assignments may exist.

Example 2:

Input: period = 10, lights = [3,6,8], arrivalTime = [4,9,15]

Output: 1

Explanation:

One optimal solution is:

  • Assign arrivalTime[0] to the traffic light with lights[2] = 8. Here, r = 4 % 10 = 4. Since 4 < 8, the waiting time is 0.
  • Assign arrivalTime[1] to the traffic light with lights[2] = 8. Here, r = 9 % 10 = 9. Since 9 >= 8, the waiting time is 10 - 9 = 1.
  • Assign arrivalTime[2] to the traffic light with lights[2] = 8. Here, r = 15 % 10 = 5. Since 5 < 8, the waiting time is 0.

The penalty of this assignment is 1, which is the minimum possible.

Example 3:

Input: period = 5, lights = [2], arrivalTime = [2,3,4,5,6]

Output: 3

Explanation:

One optimal solution is:

  • Assign arrivalTime[0] to the traffic light with lights[0] = 2. Here, r = 2 % 5 = 2. Since 2 >= 2, the waiting time is 5 - 2 = 3.
  • Assign arrivalTime[1] to the traffic light with lights[0] = 2. Here, r = 3 % 5 = 3. Since 3 >= 2, the waiting time is 5 - 3 = 2.
  • Assign arrivalTime[2] to the traffic light with lights[0] = 2. Here, r = 4 % 5 = 4. Since 4 >= 2, the waiting time is 5 - 4 = 1.
  • Assign arrivalTime[3] to the traffic light with lights[0] = 2. Here, r = 5 % 5 = 0. Since 0 < 2, the waiting time is 0.
  • Assign arrivalTime[4] to the traffic light with lights[0] = 2. Here, r = 6 % 5 = 1. Since 1 < 2, the waiting time is 0.

The penalty of this assignment is 3, which is the minimum possible.

 

Constraints:

  • 2 <= period <= 109
  • 1 <= lights.length <= 104
  • 1 <= lights[i] <= period - 1
  • 1 <= arrivalTime.length <= 105
  • 1 <= arrivalTime[i] <= 109

Approach Overview

Problem Overview: You have an array of cars arriving at synchronized traffic lights, and you need to minimize the maximum waiting time any car experiences. The lights cycle through green and red phases, and you can control the green phase duration to achieve this.

Approach 1: Brute Force (O(n^2) Time, O(1) Space)

Try every possible green phase duration from 1 to the maximum arrival time. For each candidate, simulate the waiting time for each car by iterating through the array and calculating when each car can pass. Track the maximum waiting time and choose the candidate that minimizes it. This approach is straightforward but inefficient for large inputs because it repeats the simulation for each candidate. Use it only when the input size is very small or as a baseline to verify correctness.

Approach 2: Greedy (O(n) Time, O(1) Space) - Optimal

The key insight is that the optimal green phase duration is simply the maximum arrival time among all cars. Why? Because if you set the green phase to that value, every car arrives during a green phase and waits zero time. Any shorter green phase would force some cars to wait for the next cycle, increasing the maximum waiting time. So you just iterate through the array once, track the maximum arrival time, and return it. This is a classic greedy solution that exploits the problem's structure directly.

Recommended for interviews: Interviewers expect the greedy solution because it shows you can identify the underlying pattern rather than overcomplicating it. The brute force demonstrates you understand the problem, but the optimal solution proves you can think critically about constraints and derive a simple answer. Always start by explaining the brute force to show your reasoning, then pivot to the greedy insight.

Solution

Let mx = max(lights) be the longest green duration. For car j, let r = arrivalTime[j] bmod period.

  • If r < mx, we can assign the car to the light with the longest green phase, and the waiting time is 0.
  • If r \ge mx, then r \ge lights[i] for every light, so the waiting time is period - r regardless of the assignment.

Therefore, the penalty is the maximum of period - r over all cars with r \ge mx. If every car can pass during a green light, the answer is 0.

The time complexity is O(n + m), and the space complexity is O(1), where n and m are the lengths of lights and arrivalTime, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute ForceO(n^2)O(1)Small inputs or as a baseline for testing
Greedy (Optimal)O(n)O(1)General case, expected in interviews

Video Solution

Minimize the Maximum Waiting Time at Synchronized Traffic Lights | LeetCode 4025 | Developer Coder • Developer Coder • 75 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Minimize the Maximum Waiting Time at Synchronized Traffic Lights easy or hard?
It is rated Medium on FleetCode with a 64.1% acceptance rate. The problem is conceptually simple once you see the greedy insight, but it can be tricky if you overcomplicate it with simulation.
Minimize the Maximum Waiting Time at Synchronized Traffic Lights Python/Java solution
In Python, use max(arr). In Java, use a loop to find the maximum. Both solutions are O(n) and return the maximum arrival time as the answer. Code examples are available on FleetCode in Python, Java, C++, Go, and TypeScript.
How to solve Minimize the Maximum Waiting Time at Synchronized Traffic Lights in O(n)?
Iterate through the array once, keeping track of the largest element. Return that maximum value as the green phase duration. This works because any shorter duration would cause at least one car to wait, increasing the maximum waiting time.
What is the best approach for Minimize the Maximum Waiting Time at Synchronized Traffic Lights?
The best approach is a greedy algorithm that finds the maximum arrival time in the array. Setting the green phase duration to that maximum ensures every car arrives during green, resulting in zero waiting time. This runs in O(n) time and O(1) space.
Is Minimize the Maximum Waiting Time at Synchronized Traffic Lights asked at Google/Amazon/Meta?
While not a widely known problem, greedy problems like this are common in interviews at top tech companies such as Google, Amazon, and Meta. The core skill tested is pattern recognition and deriving a simple optimal solution.
What data structure is used in Minimize the Maximum Waiting Time at Synchronized Traffic Lights?
No complex data structure is needed. The greedy approach uses only a simple array traversal with a variable to store the current maximum. This makes it memory efficient and easy to implement.
What is the time complexity of Minimize the Maximum Waiting Time at Synchronized Traffic Lights?
The optimal greedy solution has O(n) time complexity because it requires a single pass through the array to find the maximum arrival time. Space complexity is O(1) as no extra data structures are used.

Ready to solve this problem?

Practice Minimize the Maximum Waiting Time at Synchronized Traffic Lights with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays