LeetCode 1114 - Print in Order

Difficulty: 🟢 Easy
Topics: Concurrency

Solution

Problem Understanding

This problem asks us to coordinate three independent threads so that they execute in a strict order, regardless of how the operating system schedules them. We are given a class with three methods, first(), second(), and third(). Each method is called by a different thread, and the threads may start in any order.

The goal is to guarantee the following execution sequence:

first() must complete before second() begins
second() must complete before third() begins

The important detail is that thread scheduling is nondeterministic. Even if the input appears as [1,2,3], the operating system may actually run thread 3 before thread 1. Without synchronization, the output could become "thirdfirstsecond" or any other incorrect ordering.

The input array shown in the examples is not actually passed into the solution methods. It only describes the order in which the threads are started during testing. The implementation itself must work correctly for every possible scheduling order.

The constraints are extremely small because there are always exactly three methods. This means the challenge is not about algorithmic scalability, but about correct synchronization and thread coordination. The key difficulty is ensuring that later methods wait until earlier methods have finished.

A naive implementation that simply calls the print functions immediately will fail whenever threads execute out of order. Another common mistake is using busy waiting, where one thread continuously checks a condition in a loop. That approach wastes CPU resources and is considered poor concurrency design.

The problem guarantees that:

Exactly one thread calls each method
The methods are called once each
The required order is always first -> second -> third

Because of these guarantees, we only need synchronization primitives for one directional dependency chain.

Approaches

Brute Force Approach

A brute force approach would use busy waiting with shared boolean flags. For example, second() could continuously check whether first() has completed, and third() could continuously check whether second() has completed.

In Python, this might look conceptually like:

while not first_done:
    pass

This works because the later methods refuse to proceed until the earlier methods set their completion flags.

However, this approach is inefficient because the waiting threads continuously consume CPU cycles while polling the condition. This is called spinning or busy waiting. In real concurrent systems, busy waiting is wasteful and can significantly hurt performance.

Although the problem size is tiny, proper synchronization primitives are the correct solution because they allow threads to sleep efficiently until they are notified.

Optimal Approach

The better solution uses synchronization primitives such as semaphores, locks, events, or condition variables.

The key insight is that we do not need to repeatedly check whether a previous task finished. Instead, we can block a thread until another thread explicitly signals that it may continue.

The dependency chain is simple:

second() depends on first()
third() depends on second()

We can represent these dependencies with two synchronization objects:

One object signals that first() is complete
Another object signals that second() is complete

In Python, threading.Event works very naturally for this problem. An event starts in an unset state. Threads calling wait() block until another thread calls set().

In Go, channels are an elegant concurrency primitive for signaling completion between goroutines.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(infinite polling in worst case)	O(1)	Uses busy waiting, wastes CPU cycles
Optimal	O(1)	O(1)	Uses proper synchronization primitives

Algorithm Walkthrough

Create two synchronization signals during initialization.

The first signal represents whether first() has completed. The second signal represents whether second() has completed.

Initially, both signals are blocked or unset because neither operation has finished yet. 2. Execute first() immediately.

Since first() has no dependencies, it can always run right away.

After printing "first", signal that the first stage is complete. This wakes any thread waiting inside second(). 3. Make second() wait for first().

Before printing "second", the second() method waits until the first completion signal becomes available.

Once first() finishes and signals completion, second() proceeds.

After printing "second", signal that the second stage is complete. This wakes any thread waiting inside third(). 4. Make third() wait for second().

Before printing "third", the third() method waits until the second completion signal becomes available.

Once second() finishes and signals completion, third() proceeds safely.

Why it works

The core invariant is that each method can only proceed after its dependency has completed.

second() cannot execute until first() signals completion
third() cannot execute until second() signals completion

Because the synchronization primitives enforce these dependencies, the ordering is guaranteed regardless of thread scheduling order.

Python Solution

from threading import Event
from typing import Callable

class Foo:
    def __init__(self):
        self.first_done = Event()
        self.second_done = Event()

    def first(self, printFirst: 'Callable[[], None]') -> None:

        # printFirst() outputs "first". Do not change or remove this line.
        printFirst()

        self.first_done.set()

    def second(self, printSecond: 'Callable[[], None]') -> None:

        self.first_done.wait()

        # printSecond() outputs "second". Do not change or remove this line.
        printSecond()

        self.second_done.set()

    def third(self, printThird: 'Callable[[], None]') -> None:

        self.second_done.wait()

        # printThird() outputs "third". Do not change or remove this line.
        printThird()

The implementation uses Python's threading.Event class, which provides a simple signaling mechanism between threads.

Inside __init__, we create two event objects:

first_done tracks completion of first()
second_done tracks completion of second()

The first() method executes immediately because it has no dependencies. After printing "first", it calls set() on first_done. This permanently marks the event as completed and wakes any thread waiting on it.

The second() method begins by calling wait() on first_done. If first() has not finished yet, the thread blocks efficiently without consuming CPU resources. Once the event is set, execution continues and "second" is printed.

Afterward, second() signals completion by setting second_done.

The third() method follows the same pattern. It waits for second_done before printing "third".

This structure directly mirrors the dependency chain required by the problem.

Go Solution

package main

type Foo struct {
	firstDone  chan struct{}
	secondDone chan struct{}
}

func NewFoo() *Foo {
	return &Foo{
		firstDone:  make(chan struct{}),
		secondDone: make(chan struct{}),
	}
}

func (f *Foo) First(printFirst func()) {
	// Do not change this line
	printFirst()

	close(f.firstDone)
}

func (f *Foo) Second(printSecond func()) {
	<-f.firstDone

	/// Do not change this line
	printSecond()

	close(f.secondDone)
}

func (f *Foo) Third(printThird func()) {
	<-f.secondDone

	// Do not change this line
	printThird()
}

The Go solution uses channels for synchronization.

Each channel acts as a completion signal:

firstDone signals completion of First()
secondDone signals completion of Second()

The expression:

<-f.firstDone

blocks until the channel is closed.

After First() completes, it closes firstDone, which unblocks Second(). Similarly, after Second() completes, it closes secondDone, which unblocks Third().

This approach is idiomatic Go because channels are designed specifically for goroutine coordination and synchronization.

Unlike Python, Go does not use event objects here. Instead, closed channels naturally serve as one-time broadcast signals.

Worked Examples

Example 1

Input:

nums = [1,2,3]

This means the threads start in the natural order.

Initial state:

Variable	State
`first_done`	unset
`second_done`	unset

Execution trace:

Step	Thread	Action	State After
1	first	prints `"first"`	`first_done = set`
2	second	waits on `first_done`, proceeds immediately	unchanged
3	second	prints `"second"`	`second_done = set`
4	third	waits on `second_done`, proceeds immediately	unchanged
5	third	prints `"third"`	finished

Final output:

"firstsecondthird"

Example 2

Input:

nums = [1,3,2]

This means thread execution starts in the order:

first()
third()
second()

Initial state:

Variable	State
`first_done`	unset
`second_done`	unset

Execution trace:

Step	Thread	Action	State After
1	first	prints `"first"`	`first_done = set`
2	third	waits on `second_done`	blocked
3	second	waits on `first_done`, proceeds	unchanged
4	second	prints `"second"`	`second_done = set`
5	third	unblocks and proceeds	unchanged
6	third	prints `"third"`	finished

Final output:

"firstsecondthird"

Even though third() started before second(), synchronization prevented incorrect execution order.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Each method performs a constant number of synchronization operations
Space	O(1)	Only two synchronization objects are stored

The complexity remains constant because there are always exactly three methods and two synchronization signals. Waiting time caused by thread scheduling is not counted in algorithmic complexity analysis.

Test Cases

from threading import Thread
from queue import Queue

def run_test(order):
    foo = Foo()
    output = Queue()

    def print_first():
        output.put("first")

    def print_second():
        output.put("second")

    def print_third():
        output.put("third")

    methods = {
        1: lambda: foo.first(print_first),
        2: lambda: foo.second(print_second),
        3: lambda: foo.third(print_third),
    }

    threads = [Thread(target=methods[x]) for x in order]

    for thread in threads:
        thread.start()

    for thread in threads:
        thread.join()

    result = "".join(list(output.queue))
    return result

# Provided example 1
assert run_test([1, 2, 3]) == "firstsecondthird"

# Provided example 2
assert run_test([1, 3, 2]) == "firstsecondthird"

# Completely reversed order
assert run_test([3, 2, 1]) == "firstsecondthird"

# Second starts first
assert run_test([2, 1, 3]) == "firstsecondthird"

# Third starts first
assert run_test([3, 1, 2]) == "firstsecondthird"

# Random valid permutation
assert run_test([2, 3, 1]) == "firstsecondthird"

print("All tests passed!")

Test	Why
`[1,2,3]`	Verifies normal ordered execution
`[1,3,2]`	Ensures `third()` waits correctly
`[3,2,1]`	Tests worst possible scheduling order
`[2,1,3]`	Ensures `second()` blocks until `first()` completes
`[3,1,2]`	Ensures `third()` blocks before `second()` finishes
`[2,3,1]`	Validates synchronization under arbitrary ordering

Edge Cases

One important edge case occurs when third() starts before both first() and second(). A naive implementation might allow third() to print immediately, producing invalid output. In our implementation, third() blocks on second_done.wait(), so it cannot proceed until second() explicitly signals completion.

Another important edge case occurs when second() starts before first(). Without synchronization, the output could become "secondfirstthird". Our solution handles this by forcing second() to wait on the first_done event before continuing.

A subtle edge case involves thread scheduling delays. For example, first() may finish long before second() even starts. The synchronization mechanism must still work correctly in this case. Event objects and closed channels retain their signaled state permanently, so even if the waiting thread arrives later, it immediately proceeds without deadlocking.

A final edge case involves CPU efficiency. Busy waiting solutions may technically produce correct results, but they continuously consume processor time while waiting. Our implementation avoids this problem entirely because blocked threads sleep efficiently until notified by the synchronization primitive.