Skip to main content
Talentd

Building H2O - Solution & Explanation

MediumConcurrency14 min readAsked at: Tesla, Google, LinkedIn
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You are given multiple threads representing hydrogen and oxygen atoms. The goal is to synchronize them so exactly two hydrogen threads and one oxygen thread print in the correct grouping to form a water molecule (H2O). The challenge is not computation but coordination—threads must wait until the right combination is available before proceeding.

Approach 1: Semaphore Synchronization (O(n) time, O(1) space)

This approach uses concurrency primitives called semaphores to control how many hydrogen and oxygen threads can proceed at a time. Initialize a hydrogen semaphore with value 2 and an oxygen semaphore with value 1. Each hydrogen thread acquires the hydrogen semaphore before printing H, and each oxygen thread acquires the oxygen semaphore before printing O. After three atoms participate, the semaphores reset so the next molecule can form. The key idea is limiting the number of threads entering the critical section so only two hydrogen and one oxygen are allowed per cycle. Each thread performs constant-time synchronization operations (acquire, release), giving overall O(n) time across all threads and O(1) auxiliary space.

Approach 2: Monitor Synchronization Using Mutex and Condition Variables (O(n) time, O(1) space)

This solution models the problem using a monitor with a mutex lock and condition variables. Shared counters track how many hydrogen and oxygen threads are currently ready. When a thread arrives, it locks the mutex and checks whether adding itself would violate the 2H + 1O constraint. If the molecule is incomplete or too many of one atom have arrived, the thread waits on a condition variable. Once exactly two hydrogen and one oxygen threads are available, all three are signaled to proceed and print their characters. After printing, the counters reset for the next molecule. The monitor guarantees mutual exclusion and correct grouping, while condition variables handle waiting and signaling efficiently.

Recommended for interviews: Semaphore synchronization is usually the expected answer. It demonstrates strong understanding of thread coordination and resource limiting using simple primitives. The monitor approach is also valid and shows deeper familiarity with classic synchronization patterns like mutex locks and condition variables. Showing both indicates you understand how low-level thread coordination works beyond basic locking.

Approach 1: Semaphore Synchronization

This approach leverages semaphores to synchronize the hydrogen and oxygen threads. The idea is to have semaphores interrupt the thread execution until the necessary conditions (2 hydrogen threads and 1 oxygen thread) are met to form a water molecule.

This C program creates hydrogen and oxygen threads using the pthread library and controls their synchronization using semaphores. The semaphores ensure that exactly two hydrogen and one oxygen thread proceed at a time to release their respective elements according to the formation of water.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(1) for each thread operation as the semaphore operations are constant time.
Space Complexity: O(1), excluding thread stack space.

Try this approach in the editor →

Approach 2: Monitor Synchronization Using Mutex and Condition Variables

This alternative approach uses a monitor-style synchronization, generally with mutex and condition variables, to control the sequence in which hydrogen and oxygen threads are executed to form molecules.

This C solution implements monitor-based synchronization using pthread_mutex and pthread_cond constructs to effectively manage access to shared resources. The condition signals ensure that threads are only released when they can successfully form a water molecule.

Code

CC++JavaPythonC#

C

C++

Java

Python

C#

Complexity

Time Complexity: O(1) per lock, unlock, and condition operations, being constant time.
Space Complexity: O(1) excluding thread stack space.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++

Python

Java

C++

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Semaphore Synchronization

Time Complexity: O(1) for each thread operation as the semaphore operations are constant time.
Space Complexity: O(1), excluding thread stack space.

Monitor Synchronization Using Mutex and Condition Variables

Time Complexity: O(1) per lock, unlock, and condition operations, being constant time.
Space Complexity: O(1) excluding thread stack space.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Semaphore SynchronizationO(n)O(1)Preferred approach for interview settings and systems using semaphore primitives for thread coordination.
Monitor (Mutex + Condition Variables)O(n)O(1)Useful when implementing synchronization using locks and condition variables instead of semaphores.

Video Solution

Building H2O • Suraj Mehta • 2,028 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Building H2O easy or hard?
Building H2O is considered a Medium difficulty problem on LeetCode. The challenge comes from reasoning about thread synchronization rather than algorithmic complexity. Candidates comfortable with semaphores and condition variables usually solve it quickly.
Building H2O Python/Java solution
Python and Java implementations typically use semaphores from their concurrency libraries. In Python, the threading.Semaphore class controls how many hydrogen and oxygen threads run. In Java, java.util.concurrent.Semaphore or synchronized blocks with condition variables achieve the same coordination.
How to solve Building H2O in O(n)?
Use synchronization primitives such as semaphores or condition variables to control how many hydrogen and oxygen threads proceed at once. Limit hydrogen to two concurrent threads and oxygen to one, allowing them to print only when the molecule composition is satisfied. Each thread performs constant-time operations, leading to O(n) total work.
What is the best approach for Building H2O?
Semaphore synchronization is the most common solution. Two permits are assigned to hydrogen and one permit to oxygen, ensuring only two H threads and one O thread proceed per molecule. Each thread acquires and releases permits in constant time, giving O(n) total operations across all threads with O(1) extra space.
Is Building H2O asked at Google/Amazon/Meta?
Building H2O is a classic concurrency interview question and has appeared in interviews at companies that evaluate multithreading knowledge, including large tech companies. It tests understanding of synchronization primitives like semaphores, mutex locks, and condition variables.
What data structure is used in Building H2O?
The problem mainly relies on concurrency primitives rather than traditional data structures. Common implementations use semaphores, mutex locks, and condition variables to coordinate thread execution and enforce the 2:1 hydrogen-to-oxygen constraint.
What is the time complexity of Building H2O?
The time complexity is O(n), where n is the total number of hydrogen and oxygen threads. Each thread performs a constant number of synchronization operations such as acquiring or releasing a semaphore or waiting on a condition variable.

Ready to solve this problem?

Practice Building H2O with our built-in code editor and test cases.

Practice on FleetCode
Previous

Print in Order

Next

Print FooBar Alternately