LeetCode 1117 - Building H2O

LeetCode Problem 1117

Difficulty: 🟡 Medium
Topics: Concurrency

Solution

Problem Understanding

This problem asks us to coordinate multiple concurrent threads so that they form water molecules correctly. A water molecule contains exactly two hydrogen atoms and one oxygen atom, so the synchronization logic must ensure that threads proceed only in groups of three consisting of exactly two hydrogen threads and one oxygen thread.

Each hydrogen thread calls the hydrogen() method, and each oxygen thread calls the oxygen() method. Inside those methods, we are given callback functions:

• releaseHydrogen(), which prints "H"
• releaseOxygen(), which prints "O"

The order of characters inside a single molecule does not matter. For example, "HHO", "HOH", and "OHH" are all valid because each group contains exactly two hydrogens and one oxygen.

The important requirement is that molecules cannot overlap. Before any thread from the next molecule proceeds, all three threads of the current molecule must finish bonding together. If we split the final output into chunks of three characters, every chunk must contain exactly two H characters and one O character.

The input string in the examples represents the order in which threads arrive, not the required output order. Threads may arrive in any sequence, but the synchronization logic must coordinate them correctly.

The constraints are small:

• 1 <= n <= 20
• Total length is 3 * n
• Exactly 2 * n hydrogens exist
• Exactly n oxygens exist

Because this is a concurrency problem, the difficulty is not computational complexity but synchronization correctness. A naive implementation can easily allow:

• Too many hydrogens to proceed before oxygen arrives
• Multiple molecules to interleave incorrectly
• Deadlocks where threads wait forever
• Race conditions caused by unsynchronized shared state

The problem guarantees that enough hydrogen and oxygen threads eventually arrive to form valid molecules, so we do not need to handle impossible cases.

Approaches

Brute Force Approach

A brute force solution would maintain shared counters for waiting hydrogen and oxygen threads and repeatedly poll until enough atoms are available to form a molecule.

For example, threads could:

1. Acquire a mutex
2. Increment their corresponding counter
3. Continuously check whether hydrogen >= 2 and oxygen >= 1
4. Sleep or spin while waiting
5. Decrement counters once a molecule forms

This approach can work conceptually, but it is inefficient and error-prone. Busy waiting wastes CPU cycles because threads repeatedly wake up and check conditions. It also becomes difficult to guarantee proper molecule grouping and avoid race conditions without carefully implemented barriers.

Although the constraints are small, concurrency problems should use proper synchronization primitives instead of active polling.

Optimal Approach

The key insight is that semaphores naturally model resource availability.

We need to enforce two rules:

1. Only two hydrogen threads may participate in a molecule
2. Only one oxygen thread may participate in a molecule

We can use:

• A hydrogen semaphore initialized to 2
• An oxygen semaphore initialized to 1
• A barrier initialized to 3

The semaphores control how many threads of each type may proceed into the current molecule. The barrier ensures that all three threads wait until the complete molecule is assembled before continuing.

The process works like this:

• Hydrogen threads acquire one hydrogen permit
• Oxygen threads acquire one oxygen permit
• Each thread prints its character
• Each thread waits at the barrier
• Once all three threads arrive, the barrier releases them together
• After leaving the barrier, permits are released for the next molecule

This design cleanly separates:

• Resource control using semaphores
• Molecule synchronization using a barrier

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Uses shared counters and busy waiting
Optimal	O(n)	O(1)	Uses semaphores and barrier synchronization

Algorithm Walkthrough

Optimal Synchronization Algorithm

1. Initialize a semaphore for hydrogen with value 2.

This allows at most two hydrogen threads to participate in the current molecule. 2. Initialize a semaphore for oxygen with value 1.

This allows exactly one oxygen thread to participate in the current molecule. 3. Initialize a barrier with size 3.

The barrier ensures that all three threads forming the molecule arrive before any of them continue. 4. When a hydrogen thread arrives:

• Acquire one hydrogen semaphore permit
• Print "H" using releaseHydrogen()
• Wait at the barrier until two hydrogens and one oxygen arrive
• Release the hydrogen semaphore permit after the barrier completes

5. When an oxygen thread arrives:

• Acquire the oxygen semaphore permit
• Print "O" using releaseOxygen()
• Wait at the barrier until the full molecule forms
• Release the oxygen semaphore permit after the barrier completes

6. Once three threads reach the barrier:

• The barrier releases all three simultaneously
• The molecule is considered complete
• Permits become available for the next molecule

Why it works

The semaphores guarantee that at most two hydrogen threads and one oxygen thread participate in each molecule. The barrier guarantees that these three threads complete together before any next molecule begins. Therefore, every group of three released threads always contains exactly two hydrogens and one oxygen.

Python Solution

from threading import Semaphore, Barrier
from typing import Callable

class H2O:
    def __init__(self):
        self.hydrogen_semaphore = Semaphore(2)
        self.oxygen_semaphore = Semaphore(1)
        self.barrier = Barrier(3)

    def hydrogen(self, releaseHydrogen: 'Callable[[], None]') -> None:
        self.hydrogen_semaphore.acquire()

        # releaseHydrogen() outputs "H". Do not change or remove this line.
        releaseHydrogen()

        self.barrier.wait()

        self.hydrogen_semaphore.release()

    def oxygen(self, releaseOxygen: 'Callable[[], None]') -> None:
        self.oxygen_semaphore.acquire()

        # releaseOxygen() outputs "O". Do not change or remove this line.
        releaseOxygen()

        self.barrier.wait()

        self.oxygen_semaphore.release()

The implementation begins by creating two semaphores and one barrier inside the constructor.

The hydrogen semaphore starts with value 2, meaning only two hydrogen threads can enter the current molecule. The oxygen semaphore starts with value 1, allowing only one oxygen thread.

Inside hydrogen(), the thread first acquires a hydrogen permit. If two hydrogen threads are already participating in the current molecule, additional hydrogen threads block until permits become available.

After acquiring permission, the thread prints "H" using the provided callback function.

The thread then waits at the barrier. The barrier pauses execution until exactly three participating threads arrive. This ensures molecule completion happens atomically.

Once all three threads arrive, the barrier releases them together. The hydrogen thread then releases its semaphore permit so future molecules may use hydrogen again.

The oxygen logic is identical except it uses the oxygen semaphore, which only allows one oxygen thread per molecule.

Go Solution

package main

import (
	"sync"
)

type H2O struct {
	hydrogenSemaphore chan struct{}
	oxygenSemaphore   chan struct{}
	barrier           cyclicBarrier
}

func NewH2O() *H2O {
	h := &H2O{
		hydrogenSemaphore: make(chan struct{}, 2),
		oxygenSemaphore:   make(chan struct{}, 1),
		barrier:           newCyclicBarrier(3),
	}

	h.hydrogenSemaphore <- struct{}{}
	h.hydrogenSemaphore <- struct{}{}

	h.oxygenSemaphore <- struct{}{}

	return h
}

func (h *H2O) Hydrogen(releaseHydrogen func()) {
	<-h.hydrogenSemaphore

	// releaseHydrogen() outputs "H". Do not change or remove this line.
	releaseHydrogen()

	h.barrier.wait()

	h.hydrogenSemaphore <- struct{}{}
}

func (h *H2O) Oxygen(releaseOxygen func()) {
	<-h.oxygenSemaphore

	// releaseOxygen() outputs "O". Do not change or remove this line.
	releaseOxygen()

	h.barrier.wait()

	h.oxygenSemaphore <- struct{}{}
}

type cyclicBarrier struct {
	total      int
	count      int
	generation int
	mutex      sync.Mutex
	cond       *sync.Cond
}

func newCyclicBarrier(total int) cyclicBarrier {
	b := cyclicBarrier{
		total: total,
	}

	b.cond = sync.NewCond(&b.mutex)

	return b
}

func (b *cyclicBarrier) wait() {
	b.mutex.Lock()

	gen := b.generation
	b.count++

	if b.count == b.total {
		b.count = 0
		b.generation++
		b.cond.Broadcast()
		b.mutex.Unlock()
		return
	}

	for gen == b.generation {
		b.cond.Wait()
	}

	b.mutex.Unlock()
}

The Go version does not provide a built-in reusable barrier like Python's threading.Barrier, so we implement our own cyclic barrier using sync.Mutex and sync.Cond.

Semaphores are simulated using buffered channels:

• Hydrogen channel capacity is 2
• Oxygen channel capacity is 1

Receiving from the channel acquires a permit, and sending back into the channel releases it.

The custom cyclic barrier tracks:

• How many threads have arrived
• The current generation number
• A condition variable for waiting threads

When the required number of threads arrives, all waiting threads are awakened simultaneously.

Worked Examples

Example 1

Input:

water = "HOH"

Suppose threads arrive in this order:

Step	Thread	Action	Hydrogen Permits	Oxygen Permits	Barrier Count	Output
1	H	Acquire hydrogen semaphore	1 left	1 left	1	H
2	O	Acquire oxygen semaphore	1 left	0 left	2	HO
3	H	Acquire hydrogen semaphore	0 left	0 left	3	HOH

Once the barrier count reaches 3, all threads proceed together.

A valid molecule is formed because the group contains:

• 2 hydrogen atoms
• 1 oxygen atom

Example 2

Input:

water = "OOHHHH"

Possible execution:

Step	Thread	Action	Barrier Count	Current Output
1	O	Waits for hydrogens	1	O
2	O	Blocked by oxygen semaphore	1	O
3	H	Joins molecule	2	OH
4	H	Completes molecule	3	OHH

Barrier releases first molecule.

Now permits reset.

Step	Thread	Action	Barrier Count	Current Output
5	O	Starts second molecule	1	OHHO
6	H	Joins molecule	2	OHHOH
7	H	Completes molecule	3	OHHOHH

The output may vary because thread scheduling is nondeterministic, but every chunk of three characters forms a valid water molecule.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each thread performs constant-time synchronization operations
Space	O(1)	Only a fixed number of synchronization primitives are stored

Each hydrogen and oxygen thread performs a constant number of semaphore and barrier operations. Since there are 3n threads total, the total runtime scales linearly with the number of threads.

The memory usage remains constant because the solution stores only a few synchronization primitives regardless of input size.

Test Cases

from collections import Counter

def is_valid_water_output(output: str) -> bool:
    if len(output) % 3 != 0:
        return False

    for i in range(0, len(output), 3):
        group = output[i:i + 3]
        counts = Counter(group)

        if counts["H"] != 2 or counts["O"] != 1:
            return False

    return True

# Basic single molecule
assert is_valid_water_output("HHO")  # simplest valid molecule
assert is_valid_water_output("HOH")  # alternate ordering
assert is_valid_water_output("OHH")  # oxygen first

# Multiple molecules
assert is_valid_water_output("HHOHHO")  # two valid molecules
assert is_valid_water_output("OHHHHO")  # valid grouped structure

# Invalid molecule compositions
assert not is_valid_water_output("HHH")  # missing oxygen
assert not is_valid_water_output("OOH")  # missing hydrogen
assert not is_valid_water_output("HOO")  # too many oxygens

# Invalid grouping
assert not is_valid_water_output("HHOOHH")  # first group invalid

# Boundary case
assert is_valid_water_output("HHO" * 20)  # maximum number of molecules

# Mixed valid permutations
assert is_valid_water_output("HOHHHO")  # valid molecule partitioning
assert is_valid_water_output("OHHHOH")  # another valid arrangement

Test	Why
"HHO"	Simplest valid molecule
"HOH"	Valid alternate ordering
"OHH"	Oxygen arriving first
"HHOHHO"	Multiple valid molecules
"OHHHHO"	Different molecule interleaving
"HHH"	Detects missing oxygen
"OOH"	Detects missing hydrogen
"HOO"	Detects excess oxygen
"HHOOHH"	Detects invalid grouping
"HHO" * 20	Maximum constraint stress test
"HOHHHO"	Valid mixed arrangement
"OHHHOH"	Another valid molecule partition

Edge Cases

Oxygen threads arrive before hydrogen threads

A common bug is allowing oxygen threads to proceed immediately even when not enough hydrogen threads exist. For example, if several oxygen threads arrive first, the implementation must block all but one oxygen thread until two hydrogens become available.

The oxygen semaphore solves this cleanly by allowing only one oxygen thread into the current molecule. Additional oxygen threads remain blocked until the current molecule completes.

Excess hydrogen threads arrive early

Another tricky case occurs when many hydrogen threads arrive before any oxygen thread. Without synchronization limits, all hydrogen threads might print immediately, producing invalid outputs such as "HHHH".

The hydrogen semaphore prevents this issue because only two hydrogen threads can proceed before an oxygen thread joins the molecule.

Molecule interleaving

The most subtle concurrency issue is allowing atoms from different molecules to mix together. For example, one molecule might partially form before another molecule begins.

The barrier prevents this by forcing exactly three threads to synchronize together before any next molecule starts forming. This guarantees that every consecutive group of three output characters contains exactly two hydrogens and one oxygen.