1117. Building H2O Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

The problem

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.

Python

from threading import Semaphore, Thread

class H2O:
    def __init__(self):
        self.hSem = Semaphore(2)
        self.oSem = Semaphore(0)

    def hydrogen(self, releaseHydrogen):
        self.hSem.acquire()
        releaseHydrogen()
        if self.hSem._value == 0:
            self.oSem.release()

    def oxygen(self, releaseOxygen):
        self.oSem.acquire()
        releaseOxygen()
        self.hSem.release(2)

# Example usage:
# h2o = H2O()
# threads = []
# for _ in range(20):  # replace with actual water formation logic
#     threads.append(Thread(target=h2o.hydrogen, args=(lambda: print('H'),)))
#     threads.append(Thread(target=h2o.hydrogen, args=(lambda: print('H'),)))
#     threads.append(Thread(target=h2o.oxygen, args=(lambda: print('O'),)))
# [t.start() for t in threads]
# [t.join() for t in threads]

Java

import java.util.concurrent.Semaphore;

class H2O {
    private Semaphore hSem = new Semaphore(2);
    private Semaphore oSem = new Semaphore(0);
    
    public H2O() {}

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        hSem.acquire();
        releaseHydrogen.run();
        if (hSem.availablePermits() == 0) {
            oSem.release();
        }
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        oSem.acquire();
        releaseOxygen.run();
        hSem.release(2);
    }
}

C++

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>

std::mutex mtx;
std::condition_variable cv;
int hydrogenCount = 0;

void releaseHydrogen() {
    std::cout << "H";
}

void releaseOxygen() {
    std::cout << "O";
}

void hydrogen() {
    std::unique_lock<std::mutex> lock(mtx);
    hydrogenCount++;
    cv.wait(lock, [] { return hydrogenCount == 2; });
    releaseHydrogen();
    hydrogenCount--;
    cv.notify_all();
}

void oxygen() {
    std::unique_lock<std::mutex> lock(mtx);
    cv.wait(lock, [] { return hydrogenCount == 2; });
    releaseOxygen();
    hydrogenCount -= 2;
    cv.notify_all();
}

int main() {
    int n = 20; // example value
    std::thread threads[3 * n];

    for (int i = 0; i < n; i++) {
        threads[3 * i] = std::thread(hydrogen);
        threads[3 * i + 1] = std::thread(hydrogen);
        threads[3 * i + 2] = std::thread(oxygen);
    }

    for (int i = 0; i < 3 * n; i++) {
        threads[i].join();
    }

    return 0;
}

JavaScript

class H2O {
    constructor() {
        this.hydrogenSem = new Semaphore(2);
        this.oxygenSem = new Semaphore(0);
    }

    hydrogen(releaseHydrogen) {
        return this.hydrogenSem.acquire().then(() => {
            releaseHydrogen();
            if (this.hydrogenSem.available() === 0) {
                this.oxygenSem.release();
            }
        });
    }

    oxygen(releaseOxygen) {
        return this.oxygenSem.acquire().then(() => {
            releaseOxygen();
            this.hydrogenSem.release(2);
        });
    }
}

class Semaphore {
    constructor(count) {
        this.count = count;
        this.queue = [];
    }

    acquire() {
        if (this.count > 0) {
            this.count -= 1;
            return Promise.resolve();
        }
        return new Promise(resolve => this.queue.push(resolve));
    }

    release(n = 1) {
        this.count += n;
        while (this.count > 0 && this.queue.length > 0) {
            this.count -= 1;
            this.queue.shift()();
        }
    }

    available() {
        return this.count;
    }
}

#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>

sem_t hSem, oSem;
int hydrogenCount = 0;

void releaseHydrogen() {
    printf("H");
}

void releaseOxygen() {
    printf("O");
}

void *hydrogen(void *arg) {
    sem_wait(&hSem);
    hydrogenCount++;
    if (hydrogenCount == 2) {
        sem_post(&oSem);
    }
    sem_post(&hSem);
    releaseHydrogen();
    return NULL;
}

void *oxygen(void *arg) {
    sem_wait(&oSem);
    releaseOxygen();
    hydrogenCount -= 2;
    sem_post(&hSem);
    sem_post(&hSem);
    return NULL;
}

int main() {
    int n = 20; // example value
    pthread_t threads[3 * n];
    sem_init(&hSem, 0, 2);
    sem_init(&oSem, 0, 0);

    for (int i = 0; i < n; i++) {
        pthread_create(&threads[3 * i], NULL, hydrogen, NULL);
        pthread_create(&threads[3 * i + 1], NULL, hydrogen, NULL);
        pthread_create(&threads[3 * i + 2], NULL, oxygen, NULL);
    }

    for (int i = 0; i < 3 * n; i++) {
        pthread_join(threads[i], NULL);
    }

    sem_destroy(&hSem);
    sem_destroy(&oSem);
    return 0;
}

using System;
using System.Threading;

class H2O {
    private SemaphoreSlim hSem = new SemaphoreSlim(2);
    private SemaphoreSlim oSem = new SemaphoreSlim(0);

    public H2O() {}

    public void Hydrogen(Action releaseHydrogen) {
        hSem.Wait();
        releaseHydrogen();
        if (hSem.CurrentCount == 0) 
        {
            oSem.Release();
        }
    }

    public void Oxygen(Action releaseOxygen) {
        oSem.Wait();
        releaseOxygen();
        hSem.Release(2);
    }
}

This Python solution uses threading and semaphores to coordinate the execution of multiple threads representing hydrogen and oxygen atoms such that they combine to form a single water molecule every time. Hydrogen thread waits until the semaphore allows it and then releases oxygen semaphore when two hydrogens are present.

Complexity

Time Complexity: O(1) for each thread operation as semaphore actions are O(1).
Space Complexity: O(1).

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.

Python

from threading import Lock, Condition

class H2O:
    def __init__(self):
        self.lock = Lock()
        self.cond = Condition(self.lock)
        self.hydrogenCount = 0

    def hydrogen(self, releaseHydrogen):
        with self.cond:
            self.hydrogenCount += 1
            while self.hydrogenCount < 2:
                self.cond.wait()
            releaseHydrogen()
            self.hydrogenCount -= 1
            self.cond.notify_all()

    def oxygen(self, releaseOxygen):
        with self.cond:
            while self.hydrogenCount < 2:
                self.cond.wait()
            releaseOxygen()
            self.hydrogenCount -= 2
            self.cond.notify_all()

# Example usage:
# h2o = H2O()
# threads = []
# for _ in range(20):  # replace with actual water formation logic
#     threads.append(Thread(target=h2o.hydrogen, args=(lambda: print('H'),)))
#     threads.append(Thread(target=h2o.hydrogen, args=(lambda: print('H'),)))
#     threads.append(Thread(target=h2o.oxygen, args=(lambda: print('O'),)))
# [t.start() for t in threads]
# [t.join() for t in threads]

Java

import java.util.concurrent.locks.*;

class H2O {
    // Using ReentrantLock and Condition variables
    private final Lock lock = new ReentrantLock();
    private final Condition cond = lock.newCondition();
    private int hydrogenCount = 0;
    
    public H2O() {}

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
        lock.lock();
        try {
            hydrogenCount++;
            while (hydrogenCount < 2) {
                cond.await();
            }
            releaseHydrogen.run();
            hydrogenCount--;
            cond.signalAll();
        } finally {
            lock.unlock();
        }
    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        lock.lock();
        try {
            while (hydrogenCount < 2) {
                cond.await();
            }
            releaseOxygen.run();
            hydrogenCount -= 2;
            cond.signalAll();
        } finally {
            lock.unlock();
        }
    }
}

C++

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>

std::mutex mtx;
std::condition_variable cv;
int hydrogenCount = 0;

void releaseHydrogen() {
    std::cout << "H";
}

void releaseOxygen() {
    std::cout << "O";
}

void hydrogen() {
    std::unique_lock<std::mutex> lock(mtx);
    hydrogenCount++;
    while (hydrogenCount < 2) {
        cv.wait(lock);
    }
    releaseHydrogen();
    hydrogenCount--;
    cv.notify_all();
}

void oxygen() {
    std::unique_lock<std::mutex> lock(mtx);
    while (hydrogenCount < 2) {
        cv.wait(lock);
    }
    releaseOxygen();
    hydrogenCount -= 2;
    cv.notify_all();
}

int main() {
    int n = 20; // example value
    std::thread threads[3 * n];

    for (int i = 0; i < n; i++) {
        threads[3 * i] = std::thread(hydrogen);
        threads[3 * i + 1] = std::thread(hydrogen);
        threads[3 * i + 2] = std::thread(oxygen);
    }

    for (int i = 0; i < 3 * n; i++) {
        threads[i].join();
    }

    return 0;
}

#include <stdio.h>
#include <pthread.h>

pthread_mutex_t mutex;
pthread_cond_t cond;
int hydrogenCount = 0;

void releaseHydrogen() {
    printf("H");
}

void releaseOxygen() {
    printf("O");
}

void *hydrogen(void *arg) {
    pthread_mutex_lock(&mutex);
    hydrogenCount++;
    while (hydrogenCount < 2) {
        pthread_cond_wait(&cond, &mutex);
    }
    releaseHydrogen();
    hydrogenCount--;
    pthread_cond_broadcast(&cond);
    pthread_mutex_unlock(&mutex);
    return NULL;
}

void *oxygen(void *arg) {
    pthread_mutex_lock(&mutex);
    while (hydrogenCount < 2) {
        pthread_cond_wait(&cond, &mutex);
    }
    releaseOxygen();
    hydrogenCount -= 2;
    pthread_cond_broadcast(&cond);
    pthread_mutex_unlock(&mutex);
    return NULL;
}

int main() {
    int n = 20; // example value
    pthread_t threads[3 * n];
    pthread_cond_init(&cond, NULL);
    pthread_mutex_init(&mutex, NULL);

    for (int i = 0; i < n; i++) {
        pthread_create(&threads[3 * i], NULL, hydrogen, NULL);
        pthread_create(&threads[3 * i + 1], NULL, hydrogen, NULL);
        pthread_create(&threads[3 * i + 2], NULL, oxygen, NULL);
    }

    for (int i = 0; i < 3 * n; i++) {
        pthread_join(threads[i], NULL);
    }

    pthread_mutex_destroy(&mutex);
    pthread_cond_destroy(&cond);
    return 0;
}

using System;
using System.Threading;

class H2O {
    private object lockObj = new object();
    private int hydrogenCount = 0;
    private AutoResetEvent hReady = new AutoResetEvent(false);
    private AutoResetEvent oReady = new AutoResetEvent(false);

    public H2O() {}

    public void Hydrogen(Action releaseHydrogen) {
        lock (lockObj) {
            hydrogenCount++;
            if (hydrogenCount == 2) {
                oReady.Set(); // signal that oxygen can proceed
            }
            hReady.WaitOne(); // wait until the oxygen thread finishes
            releaseHydrogen();
            hydrogenCount--;
            if (hydrogenCount == 0) {
                hReady.Set(); // signal next hydrogen thread
            }
        }
    }

    public void Oxygen(Action releaseOxygen) {
        oReady.WaitOne(); // wait until two hydrogen threads are ready
        lock (lockObj) {
            releaseOxygen();
            hReady.Set(); // let one hydrogen run
            hReady.Set(); // let the other hydrogen run
        }
    }
}

This Python implementation uses the Lock and Condition objects from threading to provide a monitor for synchronizing thread execution. It blocks threads within a lock, waiting for the necessary conditions to release hydrogen or oxygen.

Complexity

Time Complexity: O(1) for lock and condition management.
Space Complexity: O(1).

Try this approach in the editor

Complexity comparison

Approach	Complexity
Semaphore Synchronization	Time Complexity: O(1) for each thread operation as semaphore actions are O(1). Space Complexity: O(1).
Monitor Synchronization Using Mutex and Condition Variables	Time Complexity: O(1) for lock and condition management. Space Complexity: O(1).

Complexity analysis

Approach	Time	Space	When to Use
Semaphore Synchronization	O(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.

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.

Building H2O solution and explanation

The problem

Approach overview

Approach 1: Semaphore Synchronization

Approach 2: Monitor Synchronization Using Mutex and Condition Variables

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Building H2O solution and explanation

The problem

Approach overview

Approach 1: Semaphore Synchronization

Approach 2: Monitor Synchronization Using Mutex and Condition Variables

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems