Print in Order - Solution & Explanation
Problem Statement
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:
numsis 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.
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).
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.
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.
Code
Python
JavaScript
Complexity
Time Complexity: O(1) for each method call. Space Complexity: O(1).
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).
Approach 4: Default Approach
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 | — |
Detailed 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 |
Video Solution
LeetCode #1114 - Print in Order (concurrency) • Eugene Suleimanov • 6,281 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Print in Order easy or hard?
How to solve Print in Order in O(1)?
Print in Order Python or Java solution
What is the best approach for Print in Order?
What data structure is used in Print in Order?
What is the time complexity of Print in Order?
Is Print in Order asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Print in Order with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor