Problem 12 Building H2O

The invariant, and why a permit leak breaks it

Hydrogen and oxygen threads arrive in any order; you must let them through only in complete molecules — two H and one O bond together, and no extra hydrogen may slip ahead. Two mechanisms compose to enforce this: counting semaphores cap how many of each element can stage (2 H, 1 O), and a barrier of 3 makes the staged 2H+1O wait for each other before any of them "bonds" (prints). The old version released more permits than it took (oxygen did hSem.release(2) while each hydrogen also released), so the hydrogen permit count drifted upward and more than two H could pass between oxygens — the invariant silently broke.

Correct Java

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

class H2O {
    private final Semaphore hSem = new Semaphore(2);   // at most 2 H staged
    private final Semaphore oSem = new Semaphore(1);   // at most 1 O staged
    private final CyclicBarrier barrier = new CyclicBarrier(3); // 2H + 1O assemble

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        hSem.acquire();
        await();                       // wait for the full molecule
        releaseHydrogen.run();
        hSem.release();                // release ONLY my own permit
    }
    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        oSem.acquire();
        await();
        releaseOxygen.run();
        oSem.release();
    }
    private void await() {
        try { barrier.await(); }
        catch (Exception e) { Thread.currentThread().interrupt(); }
    }
}

The barrier auto-resets after every group of 3, so molecule after molecule forms correctly, and each thread releases exactly the one permit it acquired — the counts never drift.

Correct Go (buffered channels as semaphores + a reusable barrier)

Go has no built-in CyclicBarrier, so we build a tiny reusable one from a mutex + condition; the semaphores are buffered channels (a slot = a permit).

type H2O struct {
    h chan struct{} // cap 2
    o chan struct{} // cap 1
    mu sync.Mutex; cond *sync.Cond; count int
}
func New() *H2O { x := &H2O{h: make(chan struct{},2), o: make(chan struct{},1)}; x.cond = sync.NewCond(&x.mu); return x }

func (x *H2O) barrier() {            // releases in groups of 3
    x.mu.Lock(); x.count++
    if x.count%3 == 0 { x.cond.Broadcast() } else { for x.count%3 != 0 { x.cond.Wait() } }
    x.mu.Unlock()
}
func (x *H2O) Hydrogen(release func()) { x.h <- struct{}{}; x.barrier(); release(); <-x.h }
func (x *H2O) Oxygen(release func())   { x.o <- struct{}{}; x.barrier(); release(); <-x.o }

Pitfalls

• Release only the permit you acquired. Cross-releasing (O releasing H's permits) inflates the count and lets the invariant break — the original defect.
• Without the barrier, the semaphores alone would let 2 H bond with no oxygen present; the barrier is what ties the triple together.

Takeaways

• Compose two primitives: semaphores bound how many stage; the 3-party barrier bonds the complete molecule.
• A self-resetting barrier (Java CyclicBarrier) handles molecule-after-molecule for free.
• Every acquire pairs with exactly one matching release — permit conservation is the whole game.

---

Re-authored for correctness for this guide (the prior version leaked semaphore permits, breaking the 2:1 ratio). Pattern: LeetCode 1117 "Building H2O". See also: Semaphore, Barriers, Condition Variables.

I'm working on the problem **Problem 12 Building H2O** (Concurrency). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Problem 12 Building H2O** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Problem 12 Building H2O**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Problem 12 Building H2O**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.