LeetCode 1279 - Traffic Light Controlled Intersection

This problem asks us to design a thread-safe traffic light system for a road intersection where cars arrive concurrently

leetcodeeasyconcurrency

LeetCode Problem 1279

Difficulty: 🟢 Easy
Topics: Concurrency

Solution

Problem Understanding

This problem asks us to design a thread-safe traffic light system for a road intersection where cars arrive concurrently from two different roads. The challenge is not about processing cars sequentially, but about correctly synchronizing multiple threads so that cars from different roads never cross the intersection simultaneously.

There are two roads:

  • Road A (roadId = 1), where traffic flows north-south and south-north
  • Road B (roadId = 2), where traffic flows west-east and east-west

At any moment, only one road may have a green light. If Road A has a green light, Road B must have a red light, and vice versa. Initially, Road A starts green and Road B starts red.

Each car arrival triggers a call to:

carArrived(carId, roadId, direction, turnGreen, crossCar)

The parameters represent:

  • carId: unique identifier for the car
  • roadId: which road the car belongs to
  • direction: travel direction of the car
  • turnGreen(): callback that changes the traffic light to green for the car's road
  • crossCar(): callback that allows the car to pass through the intersection

The goal is to guarantee that:

  1. Cars on different roads never cross at the same time.
  2. The solution is deadlock-free.
  3. The light changes only when necessary.
  4. Calling turnGreen() on an already green road is considered incorrect.

The concurrency aspect is the important challenge here. Multiple cars may arrive at nearly the same time from different threads. If two cars from different roads both attempt to modify the traffic light simultaneously, race conditions could occur.

The constraints are very small, with at most 20 cars, but this does not reduce the importance of synchronization. Since this is a concurrency problem, correctness matters far more than raw performance. The input guarantees that arrival times are non-decreasing and car IDs are unique, but the actual thread execution order may still vary.

Several edge cases are important to consider upfront. Multiple cars may arrive consecutively on the same road, in which case the light should not repeatedly switch. Cars from different roads may arrive simultaneously, requiring proper synchronization to avoid collisions. A naive implementation without locking could allow two cars from opposite roads to cross concurrently, violating the rules.

Approaches

Brute Force Approach

A brute force solution would attempt to manually coordinate cars using repeated checking or busy waiting. For example, a thread could continuously poll the current traffic light state until its road becomes green.

Whenever a car arrives, it would:

  1. Continuously check whether its road is green.
  2. If not green, attempt to switch it.
  3. Wait until the intersection becomes available.
  4. Cross the intersection.

This approach is correct in theory because every car eventually waits for a safe state before crossing. However, it introduces unnecessary complexity and inefficiency. Busy waiting wastes CPU cycles, and without proper locking, race conditions can still happen. Two threads could simultaneously observe the same state and incorrectly switch lights or cross together.

Since synchronization primitives exist specifically for mutual exclusion, manually coordinating thread access is unnecessary.

Optimal Approach, Mutual Exclusion With a Lock

The key observation is that the entire intersection behaves like a critical section. At any moment, only one thread should be allowed to inspect or modify the traffic light state and let a car cross.

This naturally suggests using a mutex lock.

We maintain one shared variable:

current_green_road

This tracks which road currently has the green light.

When a car arrives:

  1. It acquires the lock.
  2. It checks whether its road already has the green light.
  3. If not, it safely switches the light using turnGreen().
  4. It calls crossCar().
  5. It releases the lock.

Because the entire operation is protected by mutual exclusion, two cars from different roads cannot interfere with each other. Only one car may enter the critical section at a time.

This solution is both simple and correct.

Approach Time Complexity Space Complexity Notes
Brute Force O(wait time) O(1) Uses repeated polling or coordination, inefficient and error-prone
Optimal O(1) O(1) Uses a mutex lock and one shared traffic light state

Algorithm Walkthrough

  1. Initialize the traffic light state.

Since the problem states that Road A starts green, we initialize a variable:

current_green_road = 1

This means Road A is initially active. 2. Create a mutex lock.

Because multiple threads may invoke carArrived() simultaneously, we need synchronization. A lock ensures only one thread may manipulate the traffic light system at a time. 3. When a car arrives, acquire the lock.

The entire process of checking the light, potentially switching it, and crossing the intersection must happen atomically. 4. Check whether the arriving car's road is already green.

If:

roadId == current_green_road

then no light change is necessary.

Otherwise, the car's road currently has a red light. 5. Switch the light only if necessary.

If the current road differs from the green road:

  • Call turnGreen()
  • Update current_green_road

This ensures we never incorrectly call turnGreen() on an already green road. 6. Let the car cross.

Once the correct road has the green light, call:

crossCar()
  1. Release the lock.

After the car finishes crossing, another waiting thread may proceed.

Why it works

The key invariant is that only one thread may modify or inspect the intersection state at a time. Because every car acquires the same mutex before interacting with the traffic light, no two cars from different roads can cross simultaneously.

Additionally, current_green_road always accurately reflects which road has the green light. Since turnGreen() is only called when the requested road differs from the current green road, unnecessary or invalid light changes never occur.

This guarantees deadlock freedom and correctness.

Python Solution

from threading import Lock
from typing import Callable

class TrafficLight:
    def __init__(self):
        self.current_green_road = 1
        self.lock = Lock()

    def carArrived(
        self,
        carId: int,
        roadId: int,
        direction: int,
        turnGreen: 'Callable[[], None]',
        crossCar: 'Callable[[], None]'
    ) -> None:
        with self.lock:
            if self.current_green_road != roadId:
                turnGreen()
                self.current_green_road = roadId

            crossCar()

The implementation begins by importing Lock from Python's threading module. This lock guarantees mutual exclusion so that only one thread interacts with the intersection at a time.

Inside __init__(), we initialize current_green_road = 1 because the problem explicitly states that Road A starts green. We also create a mutex lock.

The carArrived() method wraps the critical section inside:

with self.lock:

This automatically acquires and releases the lock safely.

Inside the critical section, we compare roadId against current_green_road. If they differ, the arriving car is on a road with a red light, so we call turnGreen() and update the internal state.

Finally, we call crossCar() to let the vehicle pass. Because the lock is still held, another car from the opposite road cannot cross simultaneously.

Go Solution

package main

import "sync"

type TrafficLight struct {
	currentGreenRoad int
	mutex             sync.Mutex
}

func Constructor() TrafficLight {
	return TrafficLight{
		currentGreenRoad: 1,
	}
}

func (this *TrafficLight) CarArrived(
	carId int,
	roadId int,
	direction int,
	turnGreen func(),
	crossCar func(),
) {
	this.mutex.Lock()
	defer this.mutex.Unlock()

	if this.currentGreenRoad != roadId {
		turnGreen()
		this.currentGreenRoad = roadId
	}

	crossCar()
}

The Go solution mirrors the Python implementation but uses sync.Mutex for synchronization.

Instead of Python's context manager syntax, Go explicitly locks and unlocks the mutex using:

this.mutex.Lock()
defer this.mutex.Unlock()

Using defer ensures the mutex is always released, even if the function exits unexpectedly.

Go does not require special handling for integer overflow or nil values here because the logic only compares small integer road identifiers. The struct stores shared state directly, and pointer receivers ensure updates persist across method calls.

Worked Examples

Example 1

Input

cars = [1,3,5,2,4]
directions = [2,1,2,4,3]
arrivalTimes = [10,20,30,40,50]

Initial state:

current_green_road = 1
Step Car Road Current Green Action New Green
1 1 1 1 Cross immediately 1
2 3 1 1 Cross immediately 1
3 5 1 1 Cross immediately 1
4 2 2 1 Call turnGreen() 2
5 4 2 2 Cross immediately 2

At step 4, Road B requests access while Road A is green. The light changes once, and subsequent Road B cars pass without another switch.

Example 2

Input

cars = [1,2,3,4,5]
directions = [2,4,3,3,1]
arrivalTimes = [10,20,30,40,40]

Initial state:

current_green_road = 1
Step Car Road Current Green Action New Green
1 1 1 1 Cross immediately 1
2 2 2 1 Switch light 2
3 3 2 2 Cross immediately 2
4 5 1 2 Switch light 1
5 4 2 1 Switch light 2

The exact order between cars 4 and 5 may vary due to concurrency. The important property is that only one road is active at a time and no deadlock occurs.

Complexity Analysis

Measure Complexity Explanation
Time O(1) Each call performs a constant number of operations
Space O(1) Only one lock and one integer state variable are stored

Each invocation of carArrived() performs only a few constant-time operations: lock acquisition, one comparison, an optional state update, and a function call. No loops or auxiliary data structures are used.

The memory usage is also constant because we store only the mutex and the currently green road identifier.

Test Cases

from threading import Thread

def test_same_road_no_switch():
    tl = TrafficLight()
    actions = []

    def green():
        actions.append("green")

    def cross():
        actions.append("cross")

    tl.carArrived(1, 1, 2, green, cross)
    tl.carArrived(2, 1, 1, green, cross)

    assert actions == ["cross", "cross"]  # same road, no switch needed

def test_switch_road():
    tl = TrafficLight()
    actions = []

    def green():
        actions.append("green")

    def cross():
        actions.append("cross")

    tl.carArrived(1, 2, 4, green, cross)

    assert actions == ["green", "cross"]  # road B requires switch

def test_multiple_switches():
    tl = TrafficLight()
    actions = []

    def green():
        actions.append("green")

    def cross():
        actions.append("cross")

    tl.carArrived(1, 2, 3, green, cross)
    tl.carArrived(2, 1, 2, green, cross)
    tl.carArrived(3, 2, 4, green, cross)

    assert actions == [
        "green", "cross",
        "green", "cross",
        "green", "cross"
    ]  # alternating roads

def test_single_car():
    tl = TrafficLight()
    crossed = []

    tl.carArrived(
        1,
        1,
        1,
        lambda: crossed.append("green"),
        lambda: crossed.append("cross"),
    )

    assert crossed == ["cross"]  # simplest boundary case

def test_concurrent_arrivals():
    tl = TrafficLight()
    crossed = []

    def make_car(road):
        tl.carArrived(
            1,
            road,
            1,
            lambda: crossed.append(f"green_{road}"),
            lambda: crossed.append(f"cross_{road}")
        )

    threads = [
        Thread(target=make_car, args=(1,)),
        Thread(target=make_car, args=(2,))
    ]

    for t in threads:
        t.start()

    for t in threads:
        t.join()

    assert len([x for x in crossed if "cross" in x]) == 2
    # both cars cross safely without deadlock

test_same_road_no_switch()
test_switch_road()
test_multiple_switches()
test_single_car()
test_concurrent_arrivals()
Test Why
Same road arrivals Verifies no unnecessary light switching
Road switch Confirms turnGreen() is called only when required
Alternating roads Validates repeated state transitions
Single car Tests smallest valid input
Concurrent arrivals Ensures synchronization prevents race conditions

Edge Cases

One important edge case occurs when many cars arrive consecutively on the same road. A buggy implementation might repeatedly call turnGreen() even though the light is already green, which the problem explicitly forbids. Our implementation prevents this by checking:

if self.current_green_road != roadId:

before changing the light.

Another important case happens when cars from opposite roads arrive simultaneously. Without synchronization, both threads could observe stale state and cross at the same time, violating the problem constraints. The mutex lock ensures only one thread executes the critical section at once, eliminating race conditions.

A third edge case involves rapid alternation between roads. For example, cars may arrive in the sequence A → B → A → B. A flawed implementation could forget to update the shared traffic light state after switching. Our solution immediately updates current_green_road after turnGreen(), guaranteeing future cars observe the correct state.

Finally, the smallest boundary case is a single arriving car. Since Road A is initially green, a Road A car crosses immediately without switching, while a Road B car performs exactly one valid switch before crossing. The implementation handles both correctly with no special branching logic.