# Building H2O
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/building-h2o)
Canonical: https://scaleengineer.com/dsa/problems/building-h2o
**Companies:** [Tesla](https://scaleengineer.com/companies/tesla), [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## Problem
There are two kinds of threads: `oxygen` and `hydrogen`. Your goal is to group these threads to form water molecules.

There is a barrier where each thread has to wait until a complete molecule can be formed. Hydrogen and oxygen threads will be given `releaseHydrogen` and `releaseOxygen` methods respectively, which will allow them to pass the barrier. These threads should pass the barrier in groups of three, and they must immediately bond with each other to form a water molecule. You must guarantee that all the threads from one molecule bond before any other threads from the next molecule do.

In other words:

* If an oxygen thread arrives at the barrier when no hydrogen threads are present, it must wait for two hydrogen threads.
* If a hydrogen thread arrives at the barrier when no other threads are present, it must wait for an oxygen thread and another hydrogen thread.

We do not have to worry about matching the threads up explicitly; the threads do not necessarily know which other threads they are paired up with. The key is that threads pass the barriers in complete sets; thus, if we examine the sequence of threads that bind and divide them into groups of three, each group should contain one oxygen and two hydrogen threads.

Write synchronization code for oxygen and hydrogen molecules that enforces these constraints.

**Example 1:**

**Input:** water = "HOH"
**Output:** "HHO"
**Explanation:** "HOH" and "OHH" are also valid answers.

**Example 2:**

**Input:** water = "OOHHHH"
**Output:** "HHOHHO"
**Explanation:** "HOHHHO", "OHHHHO", "HHOHOH", "HOHHOH", "OHHHOH", "HHOOHH", "HOHOHH" and "OHHOHH" are also valid answers.

**Constraints:**

* `3 * n == water.length`
* `1 <= n <= 20`
* `water[i]` is either `'H'` or `'O'`.
* There will be exactly `2 * n` `'H'` in `water`.
* There will be exactly `n` `'O'` in `water`.

# Approaches
## Using `synchronized`, `wait()`, and `notifyAll()`
This approach uses Java's fundamental monitor-style synchronization primitives: `synchronized` blocks for mutual exclusion, and the `wait()` and `notifyAll()` methods for thread coordination. A shared counter, `hydrogenCount`, is used to track the number of hydrogen threads that have arrived at the barrier, ensuring that an oxygen thread only proceeds when two hydrogen threads are ready.
**Time:** O(1) work per thread. Each thread performs a constant number of operations. The waiting time is inherent to the problem's synchronization requirements. · **Space:** O(1). Only a single integer counter and a lock object are used, requiring constant extra space.
**Pros:** Uses fundamental and widely understood Java concurrency primitives.; The logic is relatively straightforward for those familiar with monitor-style synchronization.
**Cons:** `notifyAll()` is inefficient as it wakes up all waiting threads (a 'thundering herd'), including those that cannot make progress, leading to unnecessary context switches and condition re-checks.
### Explanation
A counter `hydrogenCount` keeps track of hydrogen threads ready to form a molecule. Both `hydrogen()` and `oxygen()` methods are `synchronized` on a common lock object to ensure atomic updates to this counter.

**Hydrogen Thread Logic:**
A hydrogen thread first checks if two hydrogen atoms are already waiting (`hydrogenCount == 2`). If so, it means the current group is full and is waiting for an oxygen atom. The thread calls `wait()`, releasing the lock and pausing its execution. If it can proceed, it calls `releaseHydrogen()`, increments the counter, and then calls `notifyAll()`. The `notifyAll()` call is crucial to wake up any waiting oxygen thread that might now be able to form a molecule.

**Oxygen Thread Logic:**
An oxygen thread checks if fewer than two hydrogen atoms are available (`hydrogenCount < 2`). If the condition is true, it calls `wait()` and pauses until it's notified and the condition is met. Once two hydrogens are available, it proceeds to call `releaseOxygen()`, resets `hydrogenCount` to 0 to prepare for the next molecule, and calls `notifyAll()` to wake up hydrogen threads for the next cycle.

The use of a `while` loop to re-check the condition after waking up is essential to handle spurious wakeups and ensure the state is correct before proceeding.

```java
class H2O {
    private int hydrogenCount = 0;
    private final Object lock = new Object();

    public H2O() {}

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        synchronized (lock) {
            while (hydrogenCount == 2) {
                lock.wait();
            }
            // releaseHydrogen.run() outputs "H". Do not change or remove this line.
            releaseHydrogen.run();
            hydrogenCount++;
            lock.notifyAll();
        }
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        synchronized (lock) {
            while (hydrogenCount < 2) {
                lock.wait();
            }
            // releaseOxygen.run() outputs "O". Do not change or remove this line.
            releaseOxygen.run();
            hydrogenCount = 0;
            lock.notifyAll();
        }
    }
}
```
### Algorithm
- Initialize an integer `hydrogenCount` to 0.
- In the `hydrogen()` method:
    - Synchronize on a shared lock object.
    - Use a `while` loop to check if `hydrogenCount` is 2. If it is, call `wait()` to pause the thread and release the lock.
    - After the loop, call `releaseHydrogen()`.
    - Increment `hydrogenCount`.
    - Call `notifyAll()` to wake up any waiting threads.
- In the `oxygen()` method:
    - Synchronize on the same shared lock object.
    - Use a `while` loop to check if `hydrogenCount` is less than 2. If it is, call `wait()`.
    - After the loop, call `releaseOxygen()`.
    - Reset `hydrogenCount` to 0.
    - Call `notifyAll()` to wake up waiting threads for the next molecule.

## Using Semaphores for Signaling
This approach utilizes semaphores to directly manage the signaling and dependencies between the threads. Instead of a shared counter and locks, semaphores act as signals that threads can wait on or send. This method is generally more efficient than `wait/notifyAll` as it avoids waking up threads unnecessarily.
**Time:** O(1) work per thread. Each thread performs a constant number of semaphore operations. · **Space:** O(1). We use two `Semaphore` objects, which is constant space.
**Pros:** More efficient than `wait/notifyAll` by avoiding the 'thundering herd' problem; threads are signaled precisely.; The code directly models the dependencies: oxygen waits for two hydrogens, and each hydrogen waits for the oxygen.
**Cons:** The logic, while concise, might be slightly less intuitive than a barrier-based solution if one is not familiar with this specific semaphore signaling pattern.
### Explanation
We use two semaphores to orchestrate the molecule formation in a producer-consumer-like pattern.
- `hReady`: A semaphore initialized to 0. Hydrogen threads act as producers, calling `release()` to add a permit, signaling their arrival. The oxygen thread acts as a consumer, calling `acquire(2)` to wait for two such signals.
- `oReady`: A semaphore initialized to 0. The oxygen thread acts as a producer, calling `release(2)` to signal that the two hydrogen threads can complete their action. The hydrogen threads act as consumers, each calling `acquire()` to wait for this signal.

**Hydrogen Thread Logic:**
A hydrogen thread first signals its availability by calling `hReady.release()`. It then immediately tries to acquire a permit from `oReady` by calling `oReady.acquire()`. This call will block until an oxygen thread releases a permit on `oReady`. Once unblocked, it knows a molecule is being formed, and it calls `releaseHydrogen()`.

**Oxygen Thread Logic:**
An oxygen thread waits for two hydrogen threads by calling `hReady.acquire(2)`. This call blocks until two separate hydrogen threads have called `hReady.release()`. Once it proceeds, it calls `releaseOxygen()` and then `oReady.release(2)`, which unblocks the two hydrogen threads that are waiting on `oReady`.

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

class H2O {
    private Semaphore hReady = new Semaphore(0);
    private Semaphore oReady = new Semaphore(0);

    public H2O() {}

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        hReady.release();
        oReady.acquire();
        // releaseHydrogen.run() outputs "H". Do not change or remove this line.
        releaseHydrogen.run();
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        hReady.acquire(2);
        // releaseOxygen.run() outputs "O". Do not change or remove this line.
        releaseOxygen.run();
        oReady.release(2);
    }
}
```
### Algorithm
- Initialize a semaphore `hReady` with 0 permits.
- Initialize a semaphore `oReady` with 0 permits.
- In the `hydrogen()` method:
    - Call `hReady.release()` to signal that a hydrogen atom is available.
    - Call `oReady.acquire()` to wait for a signal from the oxygen atom.
    - Once acquired, call `releaseHydrogen()`.
- In the `oxygen()` method:
    - Call `hReady.acquire(2)` to wait for two hydrogen atoms to become available.
    - Once acquired, call `releaseOxygen()`.
    - Call `oReady.release(2)` to signal the two waiting hydrogen atoms that they can proceed.

## Using `CyclicBarrier` and Semaphores
This is arguably the most elegant and idiomatic solution, as it uses high-level concurrency utilities that directly map to the problem's description. A `CyclicBarrier` is used to make the group of three threads wait for each other, perfectly modeling the 'barrier' concept. Semaphores are used as gatekeepers to ensure that only the correct number of hydrogen (2) and oxygen (1) threads can attempt to enter the barrier for each molecule.
**Time:** O(1) work per thread. Each thread performs a constant number of synchronization operations. · **Space:** O(1). Uses a constant number of synchronization objects regardless of the number of threads.
**Pros:** Highly declarative code that directly models the problem's concepts of 'grouping' and a 'barrier'.; Very efficient and robust, using modern concurrency utilities designed for this synchronization pattern.; The barrier action provides a clean and thread-safe mechanism for resetting state.
**Cons:** Requires understanding of two different advanced concurrency primitives (`Semaphore` and `CyclicBarrier`).
### Explanation
This solution combines the strengths of two primitives:
- **Semaphores (`hSem`, `oSem`):** These act as gates. `hSem` is initialized to 2 and `oSem` to 1. A hydrogen thread must acquire a permit from `hSem`, and an oxygen thread from `oSem`. This ensures that for each cycle, a maximum of two hydrogens and one oxygen can proceed towards the barrier.
- **`CyclicBarrier`:** This is the meeting point. It's initialized to wait for 3 threads. When a thread arrives, it calls `barrier.await()` and blocks. Once the third thread calls `await()`, the barrier is 'tripped', and all three waiting threads are released simultaneously to proceed.

A key feature is the barrier's reset mechanism. The `CyclicBarrier` is constructed with a `Runnable` action that executes automatically when the barrier is tripped. This action simply releases the permits back to the semaphores (`hSem.release(2)`, `oSem.release(1)`), resetting the gates for the next set of threads to form the next molecule. This provides a clean, thread-safe way to manage the state between molecule formations.

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

class H2O {
    private Semaphore hSem = new Semaphore(2);
    private Semaphore oSem = new Semaphore(1);
    private CyclicBarrier barrier;

    public H2O() {
        this.barrier = new CyclicBarrier(3, () -> {
            // This action is executed by the last thread to enter the barrier
            // after all threads have arrived but before they are released.
            // We reset the semaphores for the next molecule.
            hSem.release(2);
            oSem.release(1);
        });
    }

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        hSem.acquire();
        try {
            barrier.await();
        } catch (BrokenBarrierException e) {
            e.printStackTrace();
        }
        // releaseHydrogen.run() outputs "H". Do not change or remove this line.
        releaseHydrogen.run();
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        oSem.acquire();
        try {
            barrier.await();
        } catch (BrokenBarrierException e) {
            e.printStackTrace();
        }
        // releaseOxygen.run() outputs "O". Do not change or remove this line.
        releaseOxygen.run();
    }
}
```
### Algorithm
- Initialize a semaphore `hSem` with 2 permits.
- Initialize a semaphore `oSem` with 1 permit.
- Initialize a `CyclicBarrier` for 3 parties. Configure it with a barrier action (a `Runnable`) that resets the semaphores by calling `hSem.release(2)` and `oSem.release(1)`.
- In the `hydrogen()` method:
    - `hSem.acquire()`.
    - `barrier.await()`.
    - `releaseHydrogen()`.
- In the `oxygen()` method:
    - `oSem.acquire()`.
    - `barrier.await()`.
    - `releaseOxygen()`.

# Solutions
### Java

```java
class H2O { private Semaphore h = new Semaphore ( 2 ); private Semaphore o = new Semaphore ( 0 ); public H2O () { } public void hydrogen ( Runnable releaseHydrogen ) throws InterruptedException { h . acquire (); // releaseHydrogen.run() outputs "H". Do not change or remove this line. releaseHydrogen . run (); o . release (); } public void oxygen ( Runnable releaseOxygen ) throws InterruptedException { o . acquire ( 2 ); // releaseOxygen.run() outputs "O". Do not change or remove this line. releaseOxygen . run (); h . release ( 2 ); } }
```

### CPP

```cpp
#include <semaphore.h> class H2O { private: sem_t h , o ; int st ; public: H2O () { sem_init ( & h , 0 , 2 ); sem_init ( & o , 0 , 0 ); st = 0 ; } void hydrogen ( function < void () > releaseHydrogen ) { sem_wait ( & h ); // releaseHydrogen() outputs "H". Do not change or remove this line. releaseHydrogen (); ++ st ; if ( st == 2 ) { sem_post ( & o ); } } void oxygen ( function < void () > releaseOxygen ) { sem_wait ( & o ); // releaseOxygen() outputs "O". Do not change or remove this line. releaseOxygen (); st = 0 ; sem_post ( & h ); sem_post ( & h ); } };
```

### Python

```python
from threading import Semaphore class H2O : def __init__ ( self ): self . h = Semaphore ( 2 ) self . o = Semaphore ( 0 ) def hydrogen ( self , releaseHydrogen : "Callable[[], None]" ) -> None : self . h . acquire () # releaseHydrogen() outputs "H". Do not change or remove this line. releaseHydrogen () if self . h . _value == 0 : # semaphore value checker api self . o . release () def oxygen ( self , releaseOxygen : "Callable[[], None]" ) -> None : self . o . acquire () # releaseOxygen() outputs "O". Do not change or remove this line. releaseOxygen () self . h . release ( 2 )
```