Skip to main content
Talentd

Traffic Light Controlled Intersection - Solution & Explanation

EasyPremiumFree on FleetCodeConcurrency7 min read
Practice this problem

Problem Statement

There is an intersection of two roads. First road is road A where cars travel from North to South in direction 1 and from South to North in direction 2. Second road is road B where cars travel from West to East in direction 3 and from East to West in direction 4.

There is a traffic light located on each road before the intersection. A traffic light can either be green or red.

  1. Green means cars can cross the intersection in both directions of the road.
  2. Red means cars in both directions cannot cross the intersection and must wait until the light turns green.

The traffic lights cannot be green on both roads at the same time. That means when the light is green on road A, it is red on road B and when the light is green on road B, it is red on road A.

Initially, the traffic light is green on road A and red on road B. When the light is green on one road, all cars can cross the intersection in both directions until the light becomes green on the other road. No two cars traveling on different roads should cross at the same time.

Design a deadlock-free traffic light controlled system at this intersection.

Implement the function void carArrived(carId, roadId, direction, turnGreen, crossCar) where:

  • carId is the id of the car that arrived.
  • roadId is the id of the road that the car travels on.
  • direction is the direction of the car.
  • turnGreen is a function you can call to turn the traffic light to green on the current road.
  • crossCar is a function you can call to let the current car cross the intersection.

Your answer is considered correct if it avoids cars deadlock in the intersection. Turning the light green on a road when it was already green is considered a wrong answer.

 

Example 1:

Input: cars = [1,3,5,2,4], directions = [2,1,2,4,3], arrivalTimes = [10,20,30,40,50]
Output: [
"Car 1 Has Passed Road A In Direction 2",    // Traffic light on road A is green, car 1 can cross the intersection.
"Car 3 Has Passed Road A In Direction 1",    // Car 3 crosses the intersection as the light is still green.
"Car 5 Has Passed Road A In Direction 2",    // Car 5 crosses the intersection as the light is still green.
"Traffic Light On Road B Is Green",          // Car 2 requests green light for road B.
"Car 2 Has Passed Road B In Direction 4",    // Car 2 crosses as the light is green on road B now.
"Car 4 Has Passed Road B In Direction 3"     // Car 4 crosses the intersection as the light is still green.
]

Example 2:

Input: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40]
Output: [
"Car 1 Has Passed Road A In Direction 2",    // Traffic light on road A is green, car 1 can cross the intersection.
"Traffic Light On Road B Is Green",          // Car 2 requests green light for road B.
"Car 2 Has Passed Road B In Direction 4",    // Car 2 crosses as the light is green on road B now.
"Car 3 Has Passed Road B In Direction 3",    // Car 3 crosses as the light is green on road B now.
"Traffic Light On Road A Is Green",          // Car 5 requests green light for road A.
"Car 5 Has Passed Road A In Direction 1",    // Car 5 crosses as the light is green on road A now.
"Traffic Light On Road B Is Green",          // Car 4 requests green light for road B. Car 4 blocked until car 5 crosses and then traffic light is green on road B.
"Car 4 Has Passed Road B In Direction 3"     // Car 4 crosses as the light is green on road B now.
]
Explanation: This is a dead-lock free scenario. Note that the scenario when car 4 crosses before turning light into green on road A and allowing car 5 to pass is also correct and Accepted scenario.

 

Constraints:

  • 1 <= cars.length <= 20
  • cars.length = directions.length
  • cars.length = arrivalTimes.length
  • All values of cars are unique
  • 1 <= directions[i] <= 4
  • arrivalTimes is non-decreasing

Approach Overview

Problem Overview: Multiple cars arrive concurrently at a two‑road intersection controlled by a traffic light. Only one road can have a green signal at a time. When a car arrives from the road that currently has the red light, your code must safely switch the light before allowing the car to cross.

Approach 1: Unsynchronized Shared State (Naive) (Time: O(1), Space: O(1))

The simplest idea is to keep a shared variable like currentGreenRoad. When a car arrives, check whether its road already has the green light. If not, call turnGreen() and update the variable, then allow the car to cross using crossCar(). This works in a single‑threaded environment but breaks in concurrent execution. Multiple threads may read and update the shared variable simultaneously, causing race conditions where two cars switch the light incorrectly or cross at the same time.

Approach 2: Mutex / Lock Synchronization (Optimal) (Time: O(1), Space: O(1))

The correct solution protects the shared state with a mutex. Each car arrival acquires a lock before checking or modifying currentGreenRoad. Inside the critical section, the thread verifies whether the incoming car’s road already has the green light. If not, it calls turnGreen() and updates the state. After ensuring the correct road is green, it calls crossCar(). The lock guarantees that only one thread modifies the intersection state at a time, preventing race conditions.

This pattern is a classic example of coordinating threads around shared resources. The traffic signal acts as shared mutable state, and the mutex enforces mutual exclusion. Because each operation only checks or updates a variable and triggers callbacks, both time and space complexity remain constant.

The problem tests understanding of concurrency, thread safety, and critical sections. Using primitives such as locks or mutexes from common threading libraries ensures predictable execution even when many cars arrive simultaneously. Similar patterns appear in systems programming where multiple workers coordinate access to shared infrastructure.

Recommended for interviews: The mutex‑based synchronization approach is what interviewers expect. Mentioning the naive unsynchronized version shows you understand the race condition, but implementing a lock around the shared state demonstrates practical knowledge of concurrency control and safe multi‑threaded design.

Solution

Code

PythonJava

Python

Java

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Unsynchronized Shared StateO(1)O(1)Conceptual baseline; demonstrates why race conditions occur in concurrent systems
Mutex / Lock SynchronizationO(1)O(1)Correct approach for concurrent environments where multiple threads access shared state

Video Solution

When My City's Traffic Lights Turn Off || ViralHog • ViralHog • 88,107,173 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Traffic Light Controlled Intersection easy or hard?
Traffic Light Controlled Intersection is classified as an Easy problem on LeetCode with an acceptance rate around 72%. The challenge is understanding concurrency concepts rather than algorithmic complexity.
Traffic Light Controlled Intersection Python/Java solution
Both Python and Java implementations use built‑in locking primitives. Python typically uses threading.Lock to guard the critical section, while Java uses synchronized blocks or ReentrantLock. The logic remains identical: lock, check road, switch light if needed, then allow the car to cross.
How to solve Traffic Light Controlled Intersection in O(1)?
Store the road that currently has the green light in a shared variable and protect it with a mutex. When a thread representing a car arrives, it locks the critical section, checks the variable, calls turnGreen() if the road differs, then calls crossCar(). Since only constant operations occur, the complexity remains O(1).
What is the best approach for Traffic Light Controlled Intersection?
The best approach uses a mutex or lock to protect the shared traffic light state. Each arriving car acquires the lock, checks which road currently has the green signal, switches it if necessary using turnGreen(), and then calls crossCar(). This guarantees thread-safe execution with O(1) time and O(1) space.
Is Traffic Light Controlled Intersection asked at Google/Amazon/Meta?
Concurrency design questions similar to this problem appear in interviews at companies like Google, Amazon, and Meta. They test understanding of thread safety, race conditions, and synchronization primitives such as mutexes or locks.
What data structure is used in Traffic Light Controlled Intersection?
The solution mainly relies on a shared variable representing the current green road and a synchronization primitive such as a mutex or lock. No complex data structures are required, but understanding concurrency control is essential.
What is the time complexity of Traffic Light Controlled Intersection?
Each car arrival performs a constant number of operations: acquiring a lock, checking the current road, possibly switching the light, and allowing the car to cross. Therefore the time complexity per operation is O(1) with O(1) additional space.

Ready to solve this problem?

Practice Traffic Light Controlled Intersection with our built-in code editor and test cases.

Practice on FleetCode
Previous

Print in Order

Next

Print FooBar Alternately