Abstract / Summary

Generate a string representing the sequence to build one molecule of H2O using n times H and m times O.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 58% (100k+ submissions).

Typical patterns to solve this problem:

• Concurrency

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation models the classic synchronization problem of assembling water molecules from hydrogen and oxygen atoms. It uses a semaphore to count hydrogen arrivals and a lock to gate oxygen execution. The constructor initializes the synchronization primitives so that oxygen threads start in a blocked state while hydrogen threads can proceed up to two times before allowing oxygen to run. The hydrogen method acquires a permit from the semaphore, emits an “H”, and when the semaphore count reaches zero it releases the lock, unblocking a waiting oxygen thread. The oxygen method acquires the lock, emits an “O”, and then releases two permits back to the semaphore, resetting the system for the next molecule.

Key Steps

Initialization

def __init__(self):
    self.hydro = Semaphore(2)   # permits for two hydrogen atoms
    self.oxy   = Lock()         # lock used to block oxygen
    self.oxy.acquire()         # start with oxygen blocked

The semaphore is seeded with two permits, representing the two hydrogen atoms required for each water molecule. The lock is immediately acquired, ensuring that any oxygen thread will block until the appropriate number of hydrogen threads have arrived.

Hydrogen Thread Execution

def hydrogen(self, releaseHydrogen: 'Callable[[], None]') -> None:
    self.hydro.acquire()
    releaseHydrogen()
    if self.hydro._value == 0:
        self.oxy.release()

Each hydrogen thread obtains a permit from the semaphore. The call to releaseHydrogen() prints or otherwise signals the presence of a hydrogen atom. After the second hydrogen has acquired the last permit, the internal semaphore counter becomes zero; the conditional check detects this state and releases the lock, allowing a waiting oxygen thread to proceed.

Oxygen Thread Execution

def oxygen(self, releaseOxygen: 'Callable[[], None]') -> None:
    self.oxy.acquire()
    releaseOxygen()
    self.hydro.release(2)

The oxygen thread blocks on the lock until both hydrogen threads have arrived. Once the lock is acquired, releaseOxygen() signals the oxygen atom. Finally, the semaphore is replenished with two permits, resetting the count for the next pair of hydrogen threads.

Edge Cases Handled

When multiple hydrogen threads arrive concurrently, the semaphore ensures that only the first two succeed in acquiring permits; any additional hydrogen threads will block until the semaphore is refilled by an oxygen thread. The conditional check if self.hydro._value == 0 guarantees that the lock is released exactly once per pair of hydrogen arrivals, preventing premature or duplicate releases that could allow oxygen to run before both hydrogens are present.

If an oxygen thread arrives before any hydrogen threads, it will block on the initially acquired lock. The lock remains held until the second hydrogen thread triggers the release, ensuring the correct ordering of output “H”, “H”, “O”.

The use of self.hydro.release(2) after oxygen execution restores the semaphore to its full capacity, handling the scenario where multiple oxygen threads might be queued. Each oxygen release re-enables exactly two hydrogen acquisitions, preserving the 2:1 ratio required for water formation.

Performance Optimizations

The design leverages built-in synchronization primitives that are highly optimized at the interpreter level. The semaphore’s internal counter allows constant-time acquisition and release without the need for additional bookkeeping structures. By releasing two permits in a single call (self.hydro.release(2)), the code minimizes the number of system calls and context switches compared to releasing permits one at a time.

The lock is held only for the brief period needed to emit the oxygen signal, reducing contention among threads. Because the lock is acquired and released exactly once per molecule, the critical section remains minimal, allowing high concurrency for hydrogen threads that are only blocked when the semaphore count is exhausted.

Overall, the implementation achieves efficient coordination with low overhead, relying on the atomicity of semaphore and lock operations to maintain correct ordering without extra synchronization layers.

Imagine a little dance party where atoms want to join hands to build water. There are two tiny hydrogen friends and one oxygen friend who all have to work together to make a group.

Think of the tools here as gates that keep the friends waiting until the group is ready. The hydrogen gate is like a special doorway that only lets two hydrogen friends walk through at a time. The oxygen gate is a latch that keeps the oxygen friend waiting outside until two hydrogens have already arrived.

When a hydrogen friend comes to the party, the hydrogen gate checks if there is space. If there is, the hydrogen friend steps through to say hello. After two hydrogen friends have arrived, they unlock the oxygen latch. Then, the oxygen friend can finally step inside to join them and complete the group. Once the oxygen is in, the oxygen friend sends a message back to the hydrogen gate to make space for a brand new pair of hydrogen friends to join the fun. This way, everyone waits their turn and they never end up with the wrong mixture.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python		TS
	WalkCCC	C++
	leetcode.ca	C++	Java	Python
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	fsq	C++
	keineahnung2345	C++
	Krazune		Java
	lkwq007			Python
	suxrobGM				C#
	varunu28		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++
leetcode.ca	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
fsq	C++
keineahnung2345	C++
Krazune	Java
lkwq007	Python
suxrobGM	C#
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality