1114. Print in Order

Question

I was solving Leetcode problem 1114. I was using wait( ) and notify( ) concept. Using wait() giving time limit exceed but using notifyAll() is giving correct answer.

Why using notify() giving TLE and with notifyAll() it is working fine ??

class Foo {
    private boolean oneDone;
    private boolean twoDone;
    
    public Foo() {
        oneDone = false;
        twoDone = false;
    }

    public synchronized void first(Runnable printFirst) throws InterruptedException {
        printFirst.run();
        oneDone = true;
        //notify();
        notifyAll();
    }

    public synchronized void second(Runnable printSecond) throws InterruptedException {
        while (!oneDone) {
            wait();
        }
        printSecond.run();
        twoDone = true;
        //notify();
        notifyAll();
    }

    public synchronized void third(Runnable printThird) throws InterruptedException {
        while (!twoDone) {
            wait();
        }
        printThird.run();
    }
}

Why notify() giving TLE but notifyAll() not giving TLE ?

Answer 1

The notifyAll() wakes up all threads that are waiting on this object’s monitor. A thread waits on an object’s monitor by calling one of the wait methods. The awakened threads will not be able to proceed until the current thread relinquishes the lock on this object.

The notify() is used to wake up only one randomly chosen thread that’s waiting for an object, and that thread then begins execution. This randomly chosen thread will give up the lock and go back to the waiting state if it is not the next thread, which can lead to deadlocks.

Using notify() in your code can cause a thread to miss the signal and return to a waiting state, which can result in a TLE if the waiting thread does not wake up within the timeout period.

Using notifyAll() wakes up all waiting threads, eliminating the possibility of missing signals and potential deadlocks, allowing your code to run normally.