Problem Description

The "Building H2O" problem on Leetcode is a classic concurrency challenge. The goal is to simulate the formation of water molecules (H2O) by synchronizing threads representing hydrogen and oxygen atoms. Each water molecule requires exactly two hydrogen atoms and one oxygen atom.

• There are multiple threads, each representing either a hydrogen or an oxygen atom.
• Each thread will call either the hydrogen() or oxygen() method.
• You must ensure that for every group of three threads (two hydrogens and one oxygen), the output forms a valid water molecule.
• No atom can be used in more than one molecule.
• The order of atoms within a molecule does not matter, but you must not produce an invalid molecule (e.g., HHO is okay, but HHH or OOH is not).

Thought Process

At first glance, you might think to simply let threads print their atom type as they arrive. However, this would not guarantee that exactly two hydrogens and one oxygen are grouped together for each water molecule.

The challenge is to synchronize the threads so that:

• Exactly two hydrogen threads and one oxygen thread proceed together to form a molecule.
• Other threads must wait until a valid group can be formed.

This problem is fundamentally about thread synchronization. Brute-force approaches (like busy waiting or using global counters without proper locking) can cause race conditions or deadlocks. Instead, we need tools like semaphores, mutexes, or condition variables to manage access and coordinate threads efficiently.

Solution Approach

To solve this problem, we'll use semaphores (or similar synchronization primitives) to control the number of hydrogen and oxygen threads that can proceed. Here's the step-by-step approach:

1. Semaphores for Atom Control:
   • Initialize a semaphore for hydrogen with 2 permits and for oxygen with 1 permit.
   • Each hydrogen thread must acquire a hydrogen permit before proceeding; each oxygen thread must acquire an oxygen permit.
2. Barrier for Grouping:
   • Use a barrier (or a counter with a condition variable) to make sure that exactly three threads (two hydrogens and one oxygen) are grouped before any can proceed to print.
3. Releasing Permits:
   • After a molecule is formed, release the permits so the next group of threads can proceed.

This design ensures that no group of threads can print unless it forms a valid water molecule, and no atom is reused.

Example Walkthrough

Suppose the input sequence of threads is: H H O H H O.

1. First, two hydrogen threads and one oxygen thread arrive. They acquire the necessary permits and proceed together, printing something like HHO (order may vary).
2. The next group (two hydrogens and one oxygen) waits until all three are present, then proceeds to print another valid molecule.
3. At no point can three hydrogens or two oxygens proceed together, because the semaphores prevent it.

This ensures that every output corresponds to a valid water molecule, and no atom is reused.

Time and Space Complexity

• Brute-force Approach: If you tried to use polling or busy-waiting, time complexity would be poor due to wasted CPU cycles, and space complexity could grow with the number of waiting threads.
• Optimized Semaphore Approach: Each thread waits at most once for the barrier and semaphores, so time complexity is O(1) per thread (excluding scheduling). Space complexity is O(1), as we only use a few synchronization primitives and counters.

The solution is efficient and scalable, as it does not waste resources or allow race conditions.

Summary

The "Building H2O" problem is a synchronization challenge that requires careful coordination of threads to form valid water molecules. By using semaphores and barriers, we ensure that exactly two hydrogens and one oxygen are grouped together each time, without race conditions or resource wastage. This approach is elegant because it leverages classic concurrency constructs to enforce the problem's constraints naturally and efficiently.

Code Implementation

import threading

class H2O:
    def __init__(self):
        self.h_semaphore = threading.Semaphore(2)
        self.o_semaphore = threading.Semaphore(1)
        self.barrier = threading.Barrier(3)

    def hydrogen(self, releaseHydrogen: 'Callable[[], None]') -> None:
        self.h_semaphore.acquire()
        self.barrier.wait()
        releaseHydrogen()
        self.h_semaphore.release()

    def oxygen(self, releaseOxygen: 'Callable[[], None]') -> None:
        self.o_semaphore.acquire()
        self.barrier.wait()
        releaseOxygen()
        self.o_semaphore.release()
    

#include <semaphore.h>
#include <thread>
#include <functional>

class H2O {
private:
    std::counting_semaphore<2> h_sem{2};
    std::counting_semaphore<1> o_sem{1};
    std::barrier<> barrier{3};

public:
    H2O() {}

    void hydrogen(std::function<void()> releaseHydrogen) {
        h_sem.acquire();
        barrier.arrive_and_wait();
        releaseHydrogen();
        h_sem.release();
    }

    void oxygen(std::function<void()> releaseOxygen) {
        o_sem.acquire();
        barrier.arrive_and_wait();
        releaseOxygen();
        o_sem.release();
    }
};
    

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

class H2O {
    private Semaphore hSemaphore = new Semaphore(2);
    private Semaphore oSemaphore = new Semaphore(1);
    private CyclicBarrier barrier = new CyclicBarrier(3);

    public H2O() {}

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        hSemaphore.acquire();
        try {
            barrier.await();
            releaseHydrogen.run();
        } catch (Exception e) {
            e.printStackTrace();
        }
        hSemaphore.release();
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        oSemaphore.acquire();
        try {
            barrier.await();
            releaseOxygen.run();
        } catch (Exception e) {
            e.printStackTrace();
        }
        oSemaphore.release();
    }
}
    

class Semaphore {
    constructor(count) {
        this.count = count;
        this.queue = [];
    }
    async acquire() {
        if (this.count > 0) {
            this.count--;
        } else {
            await new Promise(resolve => this.queue.push(resolve));
        }
    }
    release() {
        this.count++;
        if (this.queue.length > 0 && this.count > 0) {
            this.count--;
            this.queue.shift()();
        }
    }
}

class Barrier {
    constructor(n) {
        this.n = n;
        this.count = 0;
        this.resolves = [];
    }
    async wait() {
        this.count++;
        if (this.count === this.n) {
            this.resolves.forEach(res => res());
            this.resolves = [];
            this.count = 0;
        } else {
            await new Promise(resolve => this.resolves.push(resolve));
        }
    }
}

class H2O {
    constructor() {
        this.hSemaphore = new Semaphore(2);
        this.oSemaphore = new Semaphore(1);
        this.barrier = new Barrier(3);
    }

    async hydrogen(releaseHydrogen) {
        await this.hSemaphore.acquire();
        await this.barrier.wait();
        releaseHydrogen();
        this.hSemaphore.release();
    }

    async oxygen(releaseOxygen) {
        await this.oSemaphore.acquire();
        await this.barrier.wait();
        releaseOxygen();
        this.oSemaphore.release();
    }
}