LeetCode 1195 - Fizz Buzz Multithreaded

LeetCode Problem 1195

Difficulty: 🟡 Medium
Topics: Concurrency

Solution

Problem Understanding

The problem asks us to coordinate four separate threads so they collectively print the correct Fizz Buzz sequence in order from 1 to n.

Unlike the classic single threaded Fizz Buzz problem, this version introduces concurrency. Each thread is responsible for only one category of output:

• The fizz() thread prints "fizz" for numbers divisible by 3 but not 5
• The buzz() thread prints "buzz" for numbers divisible by 5 but not 3
• The fizzbuzz() thread prints "fizzbuzz" for numbers divisible by both 3 and 5
• The number() thread prints ordinary integers

The challenge is not determining what to print, that logic is straightforward. The real challenge is synchronization. Since all four methods execute concurrently, we must guarantee:

1. Every number from 1 to n is processed exactly once
2. The correct thread handles each number
3. Outputs appear in the correct order
4. No race conditions occur
5. Threads do not deadlock or spin forever

The input is a single integer n, representing the length of the sequence. The expected output is the standard Fizz Buzz sequence up to n.

The constraints are small, 1 <= n <= 50, so performance is not the main concern. Correct synchronization is the core difficulty. Even though the input size is tiny, naive concurrent solutions can easily produce incorrect ordering, duplicate outputs, or deadlocks.

Several edge cases are important:

• n = 1, only the number thread should run
• n = 3, the fizz thread must activate exactly once
• n = 5, the buzz thread must activate exactly once
• n = 15, the fizzbuzz thread must take priority over fizz and buzz
• Numbers divisible by both 3 and 5 are especially important because incorrect condition ordering can cause "fizz" or "buzz" to print instead of "fizzbuzz"

A correct implementation must carefully coordinate access to the shared current number.

Approaches

Brute Force Approach

A brute force solution would continuously let all four threads check the current number in a loop until one of them can act.

For example, each thread could repeatedly:

• Check the shared counter
• Determine whether the current value belongs to it
• Print if appropriate
• Increment the counter

This works logically because eventually the correct thread will handle every number. However, it is inefficient and poorly synchronized.

The biggest issue is busy waiting. Threads continuously consume CPU cycles while repeatedly checking whether they should run. Even when it is not their turn, they remain active and polling.

Additionally, without proper synchronization primitives, race conditions become likely:

• Multiple threads may read the same value simultaneously
• Threads may increment the counter incorrectly
• Output ordering may break

Locks could partially solve these problems, but busy looping still wastes CPU time.

Optimal Approach

The better solution uses condition variables and a shared lock.

The key insight is that only one thread should proceed at a time, while the others sleep efficiently until they are needed.

We maintain:

• A shared integer current
• A mutex lock protecting shared state
• A condition variable for thread coordination

Each thread:

1. Acquires the lock
2. Waits until the current number belongs to it
3. Prints its output
4. Increments the shared counter
5. Notifies all waiting threads

Condition variables are ideal here because they allow threads to block without wasting CPU resources. When the current number changes, all threads wake up and recheck whether they should proceed.

This guarantees correctness and avoids busy waiting.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * t)	O(1)	Threads repeatedly poll the shared counter
Optimal	O(n)	O(1)	Uses condition variables for efficient synchronization

Here, t represents repeated polling iterations caused by busy waiting.

Algorithm Walkthrough

1. Initialize a shared counter called current with value 1.

This counter represents the next number that should be processed in the sequence. 2. Create a mutex lock.

Multiple threads will access and modify current, so all reads and writes must be protected to avoid race conditions. 3. Create a condition variable associated with the lock.

The condition variable allows threads to sleep until the state changes. 4. In the fizz() method, repeatedly wait until:

• current is divisible by 3
• current is not divisible by 5

Once the condition is true:

• Print "fizz"
• Increment current
• Notify all waiting threads

5. In the buzz() method, repeatedly wait until:

• current is divisible by 5
• current is not divisible by 3

Once valid:

• Print "buzz"
• Increment current
• Notify all waiting threads

6. In the fizzbuzz() method, repeatedly wait until:

• current is divisible by both 3 and 5

Then:

• Print "fizzbuzz"
• Increment current
• Notify all waiting threads

7. In the number() method, repeatedly wait until:

• current is not divisible by 3
• current is not divisible by 5

Then:

• Print the number
• Increment current
• Notify all waiting threads

8. Each thread exits once current > n.

Before exiting, notify all threads so no thread remains blocked forever.

Why it works

The key invariant is that exactly one thread is eligible to process any given value of current.

Because all accesses occur under a shared lock, only one thread can modify current at a time. After processing a number, the responsible thread increments current and wakes all waiting threads. The next correct thread then proceeds.

Since current increases exactly once per output, every number is processed exactly once and in order.

Python Solution

from threading import Condition
from typing import Callable

class FizzBuzz:
    def __init__(self, n: int):
        self.n = n
        self.current = 1
        self.condition = Condition()

    # printFizz() outputs "fizz"
    def fizz(self, printFizz: 'Callable[[], None]') -> None:
        while True:
            with self.condition:
                while (
                    self.current <= self.n and
                    not (
                        self.current % 3 == 0 and
                        self.current % 5 != 0
                    )
                ):
                    self.condition.wait()

                if self.current > self.n:
                    self.condition.notify_all()
                    return

                printFizz()
                self.current += 1
                self.condition.notify_all()

    # printBuzz() outputs "buzz"
    def buzz(self, printBuzz: 'Callable[[], None]') -> None:
        while True:
            with self.condition:
                while (
                    self.current <= self.n and
                    not (
                        self.current % 5 == 0 and
                        self.current % 3 != 0
                    )
                ):
                    self.condition.wait()

                if self.current > self.n:
                    self.condition.notify_all()
                    return

                printBuzz()
                self.current += 1
                self.condition.notify_all()

    # printFizzBuzz() outputs "fizzbuzz"
    def fizzbuzz(self, printFizzBuzz: 'Callable[[], None]') -> None:
        while True:
            with self.condition:
                while (
                    self.current <= self.n and
                    not (
                        self.current % 3 == 0 and
                        self.current % 5 == 0
                    )
                ):
                    self.condition.wait()

                if self.current > self.n:
                    self.condition.notify_all()
                    return

                printFizzBuzz()
                self.current += 1
                self.condition.notify_all()

    # printNumber(x) outputs "x", where x is an integer.
    def number(self, printNumber: 'Callable[[int], None]') -> None:
        while True:
            with self.condition:
                while (
                    self.current <= self.n and
                    not (
                        self.current % 3 != 0 and
                        self.current % 5 != 0
                    )
                ):
                    self.condition.wait()

                if self.current > self.n:
                    self.condition.notify_all()
                    return

                printNumber(self.current)
                self.current += 1
                self.condition.notify_all()

The implementation begins by initializing three shared components:

• n, the upper limit
• current, the next number to process
• condition, which combines a lock and waiting mechanism

Each method follows the same structure.

The outer while True loop keeps the thread alive until all numbers are processed.

Inside the condition block, the thread repeatedly checks whether the current number belongs to it. If not, it calls wait(), which releases the lock and suspends the thread efficiently.

Once awakened, the thread rechecks the condition because another thread may have modified the shared state first.

If current > n, the thread exits cleanly after notifying all waiting threads.

Otherwise, the thread performs its output operation, increments current, and wakes every waiting thread using notify_all().

Using notify_all() is important because the next valid thread depends on the new value of current, and we do not know which thread should run next.

Go Solution

package main

import (
	"sync"
)

type FizzBuzz struct {
	n       int
	current int
	cond    *sync.Cond
}

func Constructor(n int) *FizzBuzz {
	return &FizzBuzz{
		n:       n,
		current: 1,
		cond:    sync.NewCond(&sync.Mutex{}),
	}
}

// printFizz() outputs "fizz"
func (fb *FizzBuzz) Fizz(printFizz func()) {
	for {
		fb.cond.L.Lock()

		for fb.current <= fb.n &&
			!(fb.current%3 == 0 && fb.current%5 != 0) {
			fb.cond.Wait()
		}

		if fb.current > fb.n {
			fb.cond.Broadcast()
			fb.cond.L.Unlock()
			return
		}

		printFizz()
		fb.current++
		fb.cond.Broadcast()

		fb.cond.L.Unlock()
	}
}

// printBuzz() outputs "buzz"
func (fb *FizzBuzz) Buzz(printBuzz func()) {
	for {
		fb.cond.L.Lock()

		for fb.current <= fb.n &&
			!(fb.current%5 == 0 && fb.current%3 != 0) {
			fb.cond.Wait()
		}

		if fb.current > fb.n {
			fb.cond.Broadcast()
			fb.cond.L.Unlock()
			return
		}

		printBuzz()
		fb.current++
		fb.cond.Broadcast()

		fb.cond.L.Unlock()
	}
}

// printFizzBuzz() outputs "fizzbuzz"
func (fb *FizzBuzz) FizzBuzz(printFizzBuzz func()) {
	for {
		fb.cond.L.Lock()

		for fb.current <= fb.n &&
			!(fb.current%3 == 0 && fb.current%5 == 0) {
			fb.cond.Wait()
		}

		if fb.current > fb.n {
			fb.cond.Broadcast()
			fb.cond.L.Unlock()
			return
		}

		printFizzBuzz()
		fb.current++
		fb.cond.Broadcast()

		fb.cond.L.Unlock()
	}
}

// printNumber(x) outputs "x", where x is an integer.
func (fb *FizzBuzz) Number(printNumber func(int)) {
	for {
		fb.cond.L.Lock()

		for fb.current <= fb.n &&
			!(fb.current%3 != 0 && fb.current%5 != 0) {
			fb.cond.Wait()
		}

		if fb.current > fb.n {
			fb.cond.Broadcast()
			fb.cond.L.Unlock()
			return
		}

		printNumber(fb.current)
		fb.current++
		fb.cond.Broadcast()

		fb.cond.L.Unlock()
	}
}

The Go solution closely mirrors the Python version, but uses Go's sync.Cond type for synchronization.

One important difference is explicit lock management. In Go, we manually call:

fb.cond.L.Lock()
fb.cond.L.Unlock()

whereas Python handles lock acquisition automatically with the with statement.

Go also uses Broadcast() instead of notify_all().

Because the constraints are very small, integer overflow is not a concern in either implementation.

Worked Examples

Example 1

Input:

n = 15

Expected output:

[1,2,"fizz",4,"buzz","fizz",7,8,"fizz","buzz",11,"fizz",13,14,"fizzbuzz"]

State progression:

Current	Responsible Thread	Output	Next Current
1	number	1	2
2	number	2	3
3	fizz	fizz	4
4	number	4	5
5	buzz	buzz	6
6	fizz	fizz	7
7	number	7	8
8	number	8	9
9	fizz	fizz	10
10	buzz	buzz	11
11	number	11	12
12	fizz	fizz	13
13	number	13	14
14	number	14	15
15	fizzbuzz	fizzbuzz	16

At current = 15, only the fizzbuzz thread satisfies the condition:

current % 3 == 0 and current % 5 == 0

So it exclusively handles that value.

Example 2

Input:

n = 5

Expected output:

[1,2,"fizz",4,"buzz"]

Execution trace:

Current	Responsible Thread	Output
1	number	1
2	number	2
3	fizz	fizz
4	number	4
5	buzz	buzz

After processing 5, current becomes 6, which exceeds n, causing all threads to terminate.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each number from 1 to n is processed exactly once
Space	O(1)	Only shared counters and synchronization primitives are stored

Although multiple threads exist, the total amount of useful work remains linear in n. Every number causes exactly one successful print operation and one increment of the shared counter.

The synchronization primitives introduce constant overhead, but they do not change the asymptotic complexity.

Test Cases

# Helper simulation for verification purposes

def expected_fizzbuzz(n):
    result = []

    for i in range(1, n + 1):
        if i % 15 == 0:
            result.append("fizzbuzz")
        elif i % 3 == 0:
            result.append("fizz")
        elif i % 5 == 0:
            result.append("buzz")
        else:
            result.append(i)

    return result

assert expected_fizzbuzz(5) == [1, 2, "fizz", 4, "buzz"]  # basic example
assert expected_fizzbuzz(15) == [
    1, 2, "fizz", 4, "buzz",
    "fizz", 7, 8, "fizz", "buzz",
    11, "fizz", 13, 14, "fizzbuzz"
]  # includes fizzbuzz case

assert expected_fizzbuzz(1) == [1]  # minimum boundary
assert expected_fizzbuzz(2) == [1, 2]  # no fizz or buzz yet
assert expected_fizzbuzz(3) == [1, 2, "fizz"]  # first fizz
assert expected_fizzbuzz(5) == [1, 2, "fizz", 4, "buzz"]  # first buzz
assert expected_fizzbuzz(15)[-1] == "fizzbuzz"  # divisible by both 3 and 5
assert expected_fizzbuzz(30).count("fizzbuzz") == 2  # multiple fizzbuzz values
assert expected_fizzbuzz(50)[49] == "buzz"  # upper constraint boundary

Test	Why
n = 1	Validates minimum input size
n = 2	Ensures ordinary numbers print correctly
n = 3	Verifies fizz handling
n = 5	Verifies buzz handling
n = 15	Verifies fizzbuzz precedence
n = 30	Ensures repeated fizzbuzz handling
n = 50	Tests upper constraint boundary

Edge Cases

Numbers divisible by both 3 and 5

This is the most important correctness edge case. A naive implementation may check divisibility by 3 before checking divisibility by both 3 and 5. That would incorrectly print "fizz" instead of "fizzbuzz" for values like 15 and 30.

The implementation avoids this by giving the fizzbuzz() thread its own exclusive condition:

current % 3 == 0 and current % 5 == 0

No other thread accepts those values.

Small values of n

When n is very small, some threads may never execute their printing function at all.

For example:

• n = 1, only the number thread prints
• n = 2, fizz, buzz, and fizzbuzz never activate

Incorrect implementations may leave inactive threads blocked forever. This solution handles termination correctly by broadcasting notifications before every return.

Thread wakeup ordering

Condition variables may wake threads in arbitrary order. A thread that wakes first is not necessarily the correct thread for the current number.

This implementation safely handles that scenario by always rechecking the condition inside a while loop:

while condition_not_met:
    wait()

This pattern prevents incorrect execution caused by spurious wakeups or scheduling races.