# Print in Order
**Difficulty:** EASY
[External](https://leetcode.com/problems/print-in-order)
Canonical: https://scaleengineer.com/dsa/problems/print-in-order
**Companies:** [Nvidia](https://scaleengineer.com/companies/nvidia)
---
## 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]`.

# Approaches
## Busy Waiting with Volatile Flag
This approach uses a shared `volatile` integer to act as a flag, indicating which method's turn it is. Waiting threads continuously check this flag in a tight loop, a technique known as busy-waiting or a spinlock.
**Time:** The execution time is dependent on thread scheduling. The main drawback is not algorithmic complexity but the high CPU usage from busy-waiting, which is very inefficient. · **Space:** O(1) extra space for the volatile integer flag.
**Pros:** Conceptually simple to understand and implement.
**Cons:** Extremely inefficient as it consumes CPU cycles while waiting (busy-waiting).; Does not scale well with more threads or more complex conditions.; Can lead to performance issues like priority inversion on some systems.
### Explanation
This approach uses a shared `volatile` integer variable to act as a flag indicating which method's turn it is to execute. The `volatile` keyword ensures that changes to the flag are immediately visible to all threads. The `second()` and `third()` methods enter a tight loop (a spinlock) where they continuously check the value of this flag. They only proceed with their execution once the flag indicates that the preceding method has finished.

*   Initialize a `volatile int` variable, say `turn`, to 1.
*   The `first()` method executes its logic and then sets `turn` to 2.
*   The `second()` method enters a `while` loop that continuously checks if `turn` is equal to 2. This is known as busy-waiting or spinning. Once the condition is met, it executes its logic and sets `turn` to 3.
*   The `third()` method similarly spins in a `while` loop, waiting for `turn` to become 3 before executing its logic.

```java
class Foo {
    private volatile int turn = 1;

    public Foo() {

    }

    public void first(Runnable printFirst) throws InterruptedException {
        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
        turn = 2;
    }

    public void second(Runnable printSecond) throws InterruptedException {
        while (turn != 2) {
            // Busy-wait, consuming CPU
        }
        // printSecond.run() outputs "second". Do not change or remove this line.
        printSecond.run();
        turn = 3;
    }

    public void third(Runnable printThird) throws InterruptedException {
        while (turn != 3) {
            // Busy-wait, consuming CPU
        }
        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
    }
}
```
### Algorithm
*   Initialize a `volatile int` variable, say `turn`, to 1.
*   The `first()` method executes its logic and then sets `turn` to 2.
*   The `second()` method enters a `while` loop that continuously checks if `turn` is equal to 2. This is known as busy-waiting or spinning. Once the condition is met, it executes its logic and sets `turn` to 3.
*   The `third()` method similarly spins in a `while` loop, waiting for `turn` to become 3 before executing its logic.

## Using `synchronized`, `wait()`, and `notifyAll()`
This approach uses Java's built-in monitor locks (`synchronized` blocks) along with the `wait()` and `notifyAll()` methods. Threads that are not ready to run call `wait()` to efficiently suspend themselves, releasing the CPU. When a thread completes its task, it calls `notifyAll()` to wake up the waiting threads so they can re-check if it's their turn.
**Time:** Efficient in terms of CPU usage. The actual time depends on thread scheduling by the OS. · **Space:** O(1) extra space for the counter and the lock object.
**Pros:** CPU efficient, as waiting threads are blocked by the OS instead of spinning.; A fundamental and widely understood concurrency pattern in Java.
**Cons:** More verbose and complex than higher-level concurrency utilities.; Prone to common errors like forgetting to use a `while` loop for `wait()` (to guard against spurious wakeups) or calling `wait()`/`notifyAll()` outside a synchronized block.; `notifyAll()` can be inefficient as it wakes up all waiting threads, even those whose conditions are not yet met.
### Explanation
This approach uses Java's built-in monitor locks (`synchronized` blocks) along with the `wait()` and `notifyAll()` methods. This is a classic and more efficient alternative to busy-waiting. Threads that are not ready to run call `wait()` to efficiently suspend themselves, releasing the CPU and the lock. When a thread completes its task, it changes the state and calls `notifyAll()` to wake up any waiting threads so they can re-check if it's their turn to proceed.

*   Initialize an integer counter to 1 and a shared lock object.
*   All three methods are synchronized on the shared lock object.
*   `first()`: Executes its logic, increments the counter to 2, and calls `notifyAll()` to wake up any waiting threads.
*   `second()`: Enters a `while` loop checking if the counter is not 2. If it's not its turn, it calls `wait()`, which releases the lock and puts the thread to sleep. When woken, it re-checks the condition. If the condition is met, it executes, increments the counter to 3, and calls `notifyAll()`.
*   `third()`: Follows the same pattern as `second()`, waiting for the counter to be 3.

```java
class Foo {
    private int turn = 1;
    private final Object lock = new Object();

    public Foo() {

    }

    public void first(Runnable printFirst) throws InterruptedException {
        synchronized (lock) {
            // printFirst.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            turn = 2;
            lock.notifyAll();
        }
    }

    public void second(Runnable printSecond) throws InterruptedException {
        synchronized (lock) {
            while (turn != 2) {
                lock.wait();
            }
            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            turn = 3;
            lock.notifyAll();
        }
    }

    public void third(Runnable printThird) throws InterruptedException {
        synchronized (lock) {
            while (turn != 3) {
                lock.wait();
            }
            // printThird.run() outputs "third". Do not change or remove this line.
            printThird.run();
        }
    }
}
```
### Algorithm
*   Initialize an integer counter to 1 and a shared lock object.
*   All three methods are synchronized on the shared lock object.
*   `first()`: Executes its logic, increments the counter to 2, and calls `notifyAll()` to wake up any waiting threads.
*   `second()`: Enters a `while` loop checking if the counter is not 2. If it's not its turn, it calls `wait()`, which releases the lock and puts the thread to sleep. When woken, it re-checks the condition. If the condition is met, it executes, increments the counter to 3, and calls `notifyAll()`.
*   `third()`: Follows the same pattern as `second()`, waiting for the counter to be 3.

## Using `CountDownLatch`
This approach utilizes `java.util.concurrent.CountDownLatch`, a high-level synchronization aid. A latch acts as a gate that remains closed until its internal count reaches zero. We use two latches to create a dependency chain: `second()` waits for the first latch, and `third()` waits for the second latch.
**Time:** Highly efficient. Waiting threads are parked by the OS, consuming minimal resources. · **Space:** O(1) extra space for the two `CountDownLatch` objects.
**Pros:** Highly efficient and uses very little CPU while waiting.; The code is clean, readable, and clearly expresses the intent of waiting for a preceding task to complete.; Less error-prone than manual locking with `wait()`/`notify()`.
**Cons:** A `CountDownLatch` cannot be reset once its count reaches zero, making it unsuitable for problems requiring cyclical or reusable barriers (though this is not a limitation for the current problem).
### Explanation
This approach utilizes `java.util.concurrent.CountDownLatch`, a high-level synchronization aid that allows one or more threads to wait until a set of operations being performed in other threads completes. A latch is initialized with a given count. Threads can wait on the latch using `await()`, and they will block until the count is decremented to zero by other threads calling `countDown()`. We use two latches to create a dependency chain: `second()` waits for the first latch (released by `first()`), and `third()` waits for the second latch (released by `second()`).

*   Initialize two `CountDownLatch` objects, `latch1` and `latch2`, both with a count of 1.
*   `first()`: Executes its logic, then calls `latch1.countDown()`. This decrements the latch's count to 0, releasing any threads waiting on it.
*   `second()`: First, it calls `latch1.await()`, which blocks the thread until `latch1`'s count becomes 0. After being released, it executes its logic and then calls `latch2.countDown()`.
*   `third()`: Calls `latch2.await()`, which blocks until `second()` has completed and counted down `latch2`. Then, it executes its logic.

```java
import java.util.concurrent.CountDownLatch;

class Foo {
    private CountDownLatch latchForSecond;
    private CountDownLatch latchForThird;

    public Foo() {
        latchForSecond = new CountDownLatch(1);
        latchForThird = new CountDownLatch(1);
    }

    public void first(Runnable printFirst) throws InterruptedException {
        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
        latchForSecond.countDown();
    }

    public void second(Runnable printSecond) throws InterruptedException {
        latchForSecond.await();
        // printSecond.run() outputs "second". Do not change or remove this line.
        printSecond.run();
        latchForThird.countDown();
    }

    public void third(Runnable printThird) throws InterruptedException {
        latchForThird.await();
        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
    }
}
```
### Algorithm
*   Initialize two `CountDownLatch` objects, `latch1` and `latch2`, both with a count of 1.
*   `first()`: Executes its logic, then calls `latch1.countDown()`. This decrements the latch's count to 0, releasing any threads waiting on it.
*   `second()`: First, it calls `latch1.await()`, which blocks the thread until `latch1`'s count becomes 0. After being released, it executes its logic and then calls `latch2.countDown()`.
*   `third()`: Calls `latch2.await()`, which blocks until `second()` has completed and counted down `latch2`. Then, it executes its logic.

## Using Semaphores
This solution uses `java.util.concurrent.Semaphore`, another high-level concurrency utility. A semaphore maintains a set of permits. A thread must acquire a permit to proceed and can release a permit when done. By initializing semaphores with zero permits, we can force threads to wait until another thread explicitly releases a permit for them.
**Time:** Highly efficient. Waiting threads are parked by the OS, consuming minimal resources. · **Space:** O(1) extra space for the two `Semaphore` objects.
**Pros:** Very efficient, with waiting threads consuming minimal CPU.; The code is extremely concise and elegant for this 'pass the baton' style of synchronization.; Robust and less error-prone due to being a high-level abstraction.
**Cons:** The concept of permits might be slightly less intuitive for this specific problem than a `CountDownLatch`, which directly models 'waiting for an event to happen'.
### Explanation
This solution uses `java.util.concurrent.Semaphore`, another high-level concurrency utility. A semaphore maintains a set of permits. A thread calls `acquire()` to get a permit (blocking if none are available) and `release()` to return a permit. This mechanism is perfect for signaling between threads. We use two semaphores, both initialized with zero permits, to act as gates. `first()` opens the gate for `second()`, and `second()` opens the gate for `third()`.

*   Initialize two `Semaphore` objects, `semSecond` and `semThird`, both with 0 permits.
*   `first()`: Executes its logic, then calls `semSecond.release()`. This adds one permit to `semSecond`, effectively signaling that the second task can proceed.
*   `second()`: Calls `semSecond.acquire()`. This will block until a permit is available. Once it acquires the permit, it executes its logic and then calls `semThird.release()` to signal the third task.
*   `third()`: Calls `semThird.acquire()`, blocking until the second task releases a permit. Once acquired, it executes its logic.

```java
import java.util.concurrent.Semaphore;

class Foo {
    private Semaphore semSecond;
    private Semaphore semThird;

    public Foo() {
        semSecond = new Semaphore(0);
        semThird = new Semaphore(0);
    }

    public void first(Runnable printFirst) throws InterruptedException {
        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
        semSecond.release();
    }

    public void second(Runnable printSecond) throws InterruptedException {
        semSecond.acquire();
        // printSecond.run() outputs "second". Do not change or remove this line.
        printSecond.run();
        semThird.release();
    }

    public void third(Runnable printThird) throws InterruptedException {
        semThird.acquire();
        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
    }
}
```
### Algorithm
*   Initialize two `Semaphore` objects, `semSecond` and `semThird`, both with 0 permits.
*   `first()`: Executes its logic, then calls `semSecond.release()`. This adds one permit to `semSecond`, effectively signaling that the second task can proceed.
*   `second()`: Calls `semSecond.acquire()`. This will block until a permit is available. Once it acquires the permit, it executes its logic and then calls `semThird.release()` to signal the third task.
*   `third()`: Calls `semThird.acquire()`, blocking until the second task releases a permit. Once acquired, it executes its logic.

# Solutions
### Java

```java
class Foo { private Semaphore a = new Semaphore ( 1 ); private Semaphore b = new Semaphore ( 0 ); private Semaphore c = new Semaphore ( 0 ); public Foo () { } public void first ( Runnable printFirst ) throws InterruptedException { a . acquire ( 1 ); // printFirst.run() outputs "first". Do not change or remove this line. printFirst . run (); b . release ( 1 ); } public void second ( Runnable printSecond ) throws InterruptedException { b . acquire ( 1 ); // printSecond.run() outputs "second". Do not change or remove this line. printSecond . run (); c . release ( 1 ); } public void third ( Runnable printThird ) throws InterruptedException { c . acquire ( 1 ); // printThird.run() outputs "third". Do not change or remove this line. printThird . run (); a . release ( 1 ); } }
```

### Python

```python
import threading # Shared resource counter = 0 # Create a lock lock = threading . Lock () # A function to increment global counter def increment (): global counter for _ in range ( 100000 ): # Acquire the lock lock . acquire () counter += 1 # Release the lock lock . release () # Create threads thread1 = threading . Thread ( target = increment ) thread2 = threading . Thread ( target = increment ) # Start threads thread1 . start () thread2 . start () # Wait for both threads to finish thread1 . join () thread2 . join () print ( f "The final counter value is { counter } " )
```

### CPP

```cpp
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 (); } };
```