What is the time complexity of Print in Order?

The optimal solution has a time complexity of O(1).

What data structures are used to solve Print in Order?

This problem uses Concurrency. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Print in Order?

**Direct Dependency Signaling with `Event` Objects:** The most potent insight here is using `threading.Event` as a straightforward, one-time signal for task completion. It's perfectly suited for "task A must finish before task B can start" scenarios where you just need a binary state (done/not done) without complex resource sharing or mutual exclusion. **Chaining Completion Flags for Sequential Pipelines:** The solution constructs a simple pipeline by chaining these `Event` objects. `first` signals `second`, and `second` in turn signals `third`. This elegant cascading mechanism ensures that each step only proceeds once its direct predecessor has fully completed its critical action, perfectly satisfying the strict "print in order" requirement.

Which companies ask LeetCode 1114. Print in Order in interviews?

This problem is frequently asked at Nvidia.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Print in Order - LeetCode 1114 Solution

Print in Order - Complete Solution Guide

Print in Order is LeetCode problem 1114, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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

Detailed Explanation

This problem throws a curveball often seen in concurrent programming: enforcing a strict order on operations that might otherwise run in arbitrary sequences due to thread scheduling. We're given three methods, `first()`, `second()`, and `third()`, each intended to print a specific word. The catch is that three distinct threads will call these methods concurrently, and we have absolutely no control over when the operating system decides to run Thread A's `first()`, Thread B's `second()`, or Thread C's `third()`. Our task is to modify the `Foo` class so that despite this concurrent invocation, the output *always* reads "first", then "second", then "third".

Solution Approach

The provided solution brilliantly leverages Python's `threading.Event` objects (or similar condition variables/semaphores in other languages) to establish a clear, sequential dependency chain. We initialize two `Event` objects: `first_done` and `second_done`. Think of these as two distinct flags. When `first()` completes its `printFirst()` call, it immediately "raises" the `first_done` flag by calling `set()`. Now, consider `second()`. Before it proceeds to call `printSecond()`, it first attempts to `wait()` on the `first_done` flag. If `first_done` hasn't been `set()` yet (meaning `first()` is still running or hasn't started), `second()`'s thread will simply block and pause execution, patiently waiting. Once `first_done` is `set()`, `second()` unblocks, prints, and then, crucially, `set()`s its own `second_done` flag. This exact pattern repeats for `third()`, which waits for `second_done` before printing. This approach works because it directly translates the "A before B" rule into a "B waits for A's signal" mechanism, ensuring strict ordering without complex locking schemes.

Step-by-Step Algorithm

1. **Initialization:** The constructor of the `Foo` class initializes the synchronization primitives (events, semaphores, or mutex/condition variables).
2. **`first()` execution:** The `first()` method executes the `printFirst` function and signals that it's finished (sets the event, releases the semaphore, or notifies the condition variable).
3. **`second()` execution:** The `second()` method waits for the signal from `first()` (waits for the event to be set, acquires the semaphore, or waits on the condition variable). After the wait, it executes `printSecond` and signals its completion.
4. **`third()` execution:** The `third()` method waits for the signal from `second()`, executes `printThird`, and completes.

Key Insights

**Direct Dependency Signaling with `Event` Objects:** The most potent insight here is using `threading.Event` as a straightforward, one-time signal for task completion. It's perfectly suited for "task A must finish before task B can start" scenarios where you just need a binary state (done/not done) without complex resource sharing or mutual exclusion.
**Chaining Completion Flags for Sequential Pipelines:** The solution constructs a simple pipeline by chaining these `Event` objects. `first` signals `second`, and `second` in turn signals `third`. This elegant cascading mechanism ensures that each step only proceeds once its direct predecessor has fully completed its critical action, perfectly satisfying the strict "print in order" requirement.
**Efficiency of Blocking `wait()` Operations:** The `wait()` method of `Event` is highly efficient because it causes the calling thread to enter a dormant state, consuming minimal CPU resources until the event is `set()`. This avoids wasteful "busy-waiting" where a thread repeatedly checks a condition in a loop, making the synchronization mechanism both correct and performant.

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(1)

Topics

This problem involves: Concurrency.

Companies

Asked at: Nvidia.

Print in Order | LeetCode 1114

Easy

Concurrency

Time: O(1)Space: O(1)

Solution Code

Available in:

import java.util.concurrent.Semaphore;

class Foo {

    private Semaphore s1;
    private Semaphore s2;

    public Foo() {
        s1 = new Semaphore(0);
        s2 = new Semaphore(0);
    }

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

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

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

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1114: Print in Order - Detailed explanation and solution approaches.

Topics

Concurrency

Companies

Nvidia

Stats

Difficulty:Easy

Languages:4

Companies:1

Problem #:1114

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
1. **Initialization:** The constructor of the `Foo` class initializes the synchronization primitives (events, semaphores, or mutex/condition variables).
2
2. **`first()` execution:** The `first()` method executes the `printFirst` function and signals that it's finished (sets the event, releases the semaphore, or notifies the condition variable).
3
3. **`second()` execution:** The `second()` method waits for the signal from `first()` (waits for the event to be set, acquires the semaphore, or waits on the condition variable). After the wait, it executes `printSecond` and signals its completion.
4
4. **`third()` execution:** The `third()` method waits for the signal from `second()`, executes `printThird`, and completes.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(1)

⚡ Constant time - Super fast! Same speed regardless of input size.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is O(1) because each method performs a constant number of operations (setting/waiting on events, acquiring/releasing semaphores, or locking/unlocking mutexes and waiting on condition variables). The space complexity is O(1) because a constant amount of extra space is used for the synchronization primitives, regardless of the input size. Note that this excludes the space required by the threads themselves, which is dependent on the operating system.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using Locks and Condition Variables (C++ style in other languages)

Instead of semaphores or events, a mutex can be used to protect a shared variable indicating the current stage of execution. Condition variables would be used to signal threads to wait until the previous stage is complete. This provides finer-grained control but adds complexity.

Time: O(1)Space: O(1)

Trade-offs: This approach is more complex to implement but offers more flexibility if the problem were expanded to include more stages or more sophisticated synchronization requirements.

✨

Key Insights

1**Direct Dependency Signaling with `Event` Objects:** The most potent insight here is using `threading.Event` as a straightforward, one-time signal for task completion. It's perfectly suited for "task A must finish before task B can start" scenarios where you just need a binary state (done/not done) without complex resource sharing or mutual exclusion.
2**Chaining Completion Flags for Sequential Pipelines:** The solution constructs a simple pipeline by chaining these `Event` objects. `first` signals `second`, and `second` in turn signals `third`. This elegant cascading mechanism ensures that each step only proceeds once its direct predecessor has fully completed its critical action, perfectly satisfying the strict "print in order" requirement.
3**Efficiency of Blocking `wait()` Operations:** The `wait()` method of `Event` is highly efficient because it causes the calling thread to enter a dormant state, consuming minimal CPU resources until the event is `set()`. This avoids wasteful "busy-waiting" where a thread repeatedly checks a condition in a loop, making the synchronization mechanism both correct and performant.

📚

Key Terms Explained

For Students

Edge Cases

None: The problem statement specifies that `nums` is a permutation of `[1, 2, 3]`. There are no edge cases related to input validation because the input only affects the thread order, not the correctness of the synchronization mechanism.

⚠️

Common Mistakes to Avoid

✗Forgetting to signal after completing a stage: This can lead to deadlocks where threads are waiting indefinitely.

✗Incorrectly using synchronization primitives: Misusing semaphores, events, or condition variables can cause race conditions or deadlocks. For instance, forgetting to release a semaphore after acquiring it or not waiting for a condition variable's signal properly.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Sequential execution of tasks in a multithreaded application: This pattern is widely used in applications where tasks need to be executed in a specific order, such as processing data in a pipeline or coordinating multiple stages in a workflow.

🏦Managing shared resources in concurrent systems: The principles of synchronization shown here are essential for handling shared resources safely and efficiently in concurrent systems, such as databases or file systems, to prevent data corruption or race conditions.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 5, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Print in Order"?

For this easy-level Concurrency problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether standard techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?