1114. Print in Order - Solution & Explanation

The problem

Suppose we have a class:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().

Note:

We do not know how the threads will be scheduled in the operating system, even though the numbers in the input seem to imply the ordering. The input format you see is mainly to ensure our tests' comprehensiveness.

Example 1:

Input: nums = [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

Example 2:

Input: nums = [1,3,2]
Output: "firstsecondthird"
Explanation: The input [1,3,2] means thread A calls first(), thread B calls third(), and thread C calls second(). "firstsecondthird" is the correct output.

Constraints:

nums is a permutation of [1, 2, 3].

Approach overview

Problem Overview: Three methods first(), second(), and third() are executed by separate threads. The threads can start in any order, but the output must always be "first", then "second", then "third". The challenge is coordinating threads so later steps wait until earlier ones finish.

This problem tests basic synchronization patterns from concurrency. You must enforce ordering without relying on thread start order. The core idea: block a thread until the previous step signals completion.

Approach 1: Using Semaphores (O(1) time, O(1) space)

This solution uses two semaphores to control execution order. Initialize both semaphores with value 0. The first() method prints and then releases the first semaphore, allowing second() to proceed. The second() method waits on the first semaphore, prints, then releases the second semaphore so third() can run.

The key insight: a semaphore acts as a gate. Threads calling acquire() block until another thread calls release(). This makes it easy to chain execution order across threads. Each method performs constant operations—one acquire or release—so runtime is O(1) and extra space is O(1). This pattern is common when learning semaphores and basic thread signaling.

Approach 2: Using Locks and Conditions (O(1) time, O(1) space)

This approach uses a shared state variable protected by a lock and condition variables. Maintain an integer flag representing progress: 1 means first finished, 2 means second finished. The second() method waits on the condition until the flag indicates that first() completed. The third() method waits until the flag shows that second() completed.

The lock guarantees mutual exclusion while checking or updating the state. Condition variables allow threads to sleep efficiently instead of busy waiting. When a step finishes, it updates the flag and signals waiting threads. Each method performs a constant number of lock operations and checks, giving O(1) time and O(1) space. This pattern appears frequently in systems programming and problems involving locks and thread coordination.

Recommended for interviews: The semaphore solution is usually the clearest. It directly models dependency between steps using simple acquire/release operations. Showing the lock + condition approach demonstrates deeper understanding of thread coordination primitives. Both run in O(1) time and O(1) space, but semaphores require less boilerplate and are easier to reason about under interview pressure.

Approach 1: Using Semaphores

This approach employs semaphores to control the execution order of methods. Since semaphores are synchronization constructs that can be used to control access to a common resource in a concurrent system, we can use them to gate the execution of 'second' and 'third' methods until 'first' and 'second' have completed, respectively. The semaphore for 'second' starts at 0 and is incremented by 'first', allowing 'second' to run. Similarly, 'third' can proceed only after 'second' increments its semaphore.

Python

from threading import Semaphore

class Foo:
    def __init__(self):
        self.second_semaphore = Semaphore(0)
        self.third_semaphore = Semaphore(0)

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

    def second(self, printSecond: 'Callable[[], None]') -> None:
        self.second_semaphore.acquire()
        printSecond()
        self.third_semaphore.release()

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

Java

import java.util.concurrent.Semaphore;

public class Foo {
    private Semaphore secondSemaphore = new Semaphore(0);
    private Semaphore thirdSemaphore = new Semaphore(0);

    public void first(Runnable printFirst) throws InterruptedException {
        printFirst.run();
        secondSemaphore.release();
    }

    public void second(Runnable printSecond) throws InterruptedException {
        secondSemaphore.acquire();
        printSecond.run();
        thirdSemaphore.release();
    }

    public void third(Runnable printThird) throws InterruptedException {
        thirdSemaphore.acquire();
        printThird.run();
    }
}

using System;
using System.Threading;

public class Foo {
    private SemaphoreSlim secondSemaphore = new SemaphoreSlim(0, 1);
    private SemaphoreSlim thirdSemaphore = new SemaphoreSlim(0, 1);

    public void First(Action printFirst) {
        printFirst();
        secondSemaphore.Release();
    }

    public void Second(Action printSecond) {
        secondSemaphore.Wait();
        printSecond();
        thirdSemaphore.Release();
    }

    public void Third(Action printThird) {
        thirdSemaphore.Wait();
        printThird();
    }
}

In Python, we utilize the Semaphore class from the threading module. We initiate two semaphores, each initialized to 0. The first method prints 'first' and then releases the semaphore for second. The second method waits (acquires) on the semaphore before printing 'second' and then releases the semaphore for third. The third method waits (acquires) on its semaphore before printing 'third'.

Complexity

Time Complexity: O(1) for each method call. Space Complexity: O(1).

Try this approach in the editor

Approach 2: Using Locks and Conditions

This approach leverages locks and condition variables to achieve the desired execution order. By associating each method with a condition variable, the appropriate method waits (and releases lock) until the previous condition is signaled, facilitating the required sequence.

Python

from threading import Lock, Condition

class Foo:
    def __init__(self):
        self.lock = Lock()
        self.first_done = False
        self.second_done = False

    def first(self, printFirst):
        with self.lock:
            printFirst()
            self.first_done = True
            self.lock.notify_all()

    def second(self, printSecond):
        with self.lock:
            while not self.first_done:
                self.lock.wait()
            printSecond()
            self.second_done = True
            self.lock.notify_all()

    def third(self, printThird):
        with self.lock:
            while not self.second_done:
                self.lock.wait()
            printThird()

JavaScript

class Foo {
  constructor() {
    this.firstDone = false;
    this.secondDone = false;
    this.lock = Promise.resolve();
  }

  first(printFirst) {
    this.lock = this.lock.then(() => {
      printFirst();
      this.firstDone = true;
    });
  }

  second(printSecond) {
    this.lock = this.lock.then(() => {
      if (!this.firstDone) return this.lock.finally(() => this.second(printSecond));
      printSecond();
      this.secondDone = true;
    });
  }

  third(printThird) {
    this.lock = this.lock.then(() => {
      if (!this.secondDone) return this.lock.finally(() => this.third(printThird));
      printThird();
    });
  }
}

In Python, we use a lock with condition variables to ensure proper sequencing. The first method sets a flag and notifies other methods once it completes. Second waits until the first_done is True and proceeds similarly for third, which waits for second_done.

Complexity

Time Complexity: O(1) for each method call. Space Complexity: O(1).

Try this approach in the editor

Approach 3: Multithreading + Lock or Semaphore

We can use three semaphores a, b, and c to control the execution order of the three threads. Initially, the count of semaphore a is 1, and the counts of b and c are 0.

When thread A executes the first() method, it first needs to acquire semaphore a. After acquiring successfully, it executes the first() method, and then releases semaphore b. This allows thread B to acquire semaphore b and execute the second() method.

When thread B executes the second() method, it first needs to acquire semaphore b. After acquiring successfully, it executes the second() method, and then releases semaphore c. This allows thread C to acquire semaphore c and execute the third() method.

When thread C executes the third() method, it first needs to acquire semaphore c. After acquiring successfully, it executes the third() method, and then releases semaphore a. This allows thread A to acquire semaphore a and execute the first() method.

The time complexity is O(1), and the space complexity is O(1).

C++

class Foo {
private:
    mutex m2, m3;

public:
    Foo() {
        m2.lock();
        m3.lock();
    }

    void first(function<void()> printFirst) {
        printFirst();
        m2.unlock();
    }

    void second(function<void()> printSecond) {
        m2.lock();
        printSecond();
        m3.unlock();
    }

    void third(function<void()> printThird) {
        m3.lock();
        printThird();
    }
};

Try this approach in the editor

Approach 4: Default Approach

C++

#include <semaphore.h>

class Foo {
private:
    sem_t a, b, c;

public:
    Foo() {
        sem_init(&a, 0, 1);
        sem_init(&b, 0, 0);
        sem_init(&c, 0, 0);
    }

    void first(function<void()> printFirst) {
        sem_wait(&a);
        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        sem_post(&b);
    }

    void second(function<void()> printSecond) {
        sem_wait(&b);
        // printSecond() outputs "second". Do not change or remove this line.
        printSecond();
        sem_post(&c);
    }

    void third(function<void()> printThird) {
        sem_wait(&c);
        // printThird() outputs "third". Do not change or remove this line.
        printThird();
        sem_post(&a);
    }
};

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Semaphores	Time Complexity: O(1) for each method call. Space Complexity: O(1).
Using Locks and Conditions	Time Complexity: O(1) for each method call. Space Complexity: O(1).
Multithreading + Lock or Semaphore	–
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Semaphores	O(1)	O(1)	Best for enforcing execution order between threads with minimal code
Locks and Conditions	O(1)	O(1)	Useful when managing shared state with explicit locking and condition signaling

Frequently asked questions

Is Print in Order easy or hard?

Print in Order is rated Easy on LeetCode but introduces core concurrency concepts. The algorithmic logic is simple, but understanding how threads block and signal each other is the key skill being tested.

How to solve Print in Order in O(1)?

Use synchronization primitives to enforce execution order. With semaphores, initialize two semaphores to 0 so later threads block until earlier threads release them. With locks and condition variables, maintain a shared state flag and signal waiting threads when the previous step completes.

Print in Order Python or Java solution

Python solutions typically use threading.Semaphore or threading.Condition. Java implementations use Semaphore from java.util.concurrent or synchronized blocks with Condition objects from ReentrantLock. Both enforce that second() runs after first() and third() runs after second().

What is the best approach for Print in Order?

The semaphore approach is typically the best solution. Two semaphores enforce ordering so the second thread waits for the first and the third waits for the second. Each method performs a constant number of acquire or release operations, giving O(1) time and O(1) space.

What data structure is used in Print in Order?

The problem relies on concurrency primitives rather than traditional data structures. Typical implementations use semaphores, mutex locks, and condition variables to coordinate thread execution order.

What is the time complexity of Print in Order?

Both common solutions run in O(1) time and O(1) space. Each thread performs a constant number of synchronization operations such as semaphore acquire/release or condition waits and notifications.

Is Print in Order asked at Google, Amazon, or Meta?

Print in Order is a common concurrency warm‑up problem and has appeared in interview preparation lists associated with companies like Google, Amazon, and Meta. It checks understanding of thread synchronization primitives rather than complex algorithms.

Print in Order solution and explanation

The problem

Approach overview

Approach 1: Using Semaphores

Approach 2: Using Locks and Conditions

Approach 3: Multithreading + Lock or Semaphore

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Print in Order solution and explanation

The problem

Approach overview

Approach 1: Using Semaphores

Approach 2: Using Locks and Conditions

Approach 3: Multithreading + Lock or Semaphore

Approach 4: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems