LeetCode Problem 412

Difficulty: 🟢 Easy
Topics: Math, String, Simulation

Solution

LeetCode 412, Fizz Buzz

Problem Understanding

The problem asks us to generate a list of strings for all integers from 1 to n. For each number, we apply a set of divisibility rules:

• If the number is divisible by both 3 and 5, we append "FizzBuzz".
• If the number is divisible only by 3, we append "Fizz".
• If the number is divisible only by 5, we append "Buzz".
• Otherwise, we append the number itself as a string.

The result must be returned as a string array, where the index conceptually corresponds to the numbers from 1 through n.

For example, if n = 5, the sequence becomes:

• 1 → "1"
• 2 → "2"
• 3 → "Fizz"
• 4 → "4"
• 5 → "Buzz"

So the final output is:

["1","2","Fizz","4","Buzz"]

The constraint 1 <= n <= 10^4 tells us that the input size is relatively small. Even a straightforward linear scan from 1 to n is completely acceptable. There is no need for advanced optimization techniques or complex data structures.

One important detail is the ordering of conditions. A naive implementation might check divisibility by 3 first and then divisibility by 5. That would incorrectly classify numbers like 15 as "Fizz" instead of "FizzBuzz". The combined condition must therefore be checked before the individual conditions.

The problem guarantees that n is always at least 1, so we never need to handle empty ranges or invalid inputs.

Approaches

Brute Force Approach

The brute-force approach is to iterate through every number from 1 to n and determine which string should be added to the result.

For each integer:

• Check whether it is divisible by both 3 and 5
• Otherwise check divisibility by 3
• Otherwise check divisibility by 5
• Otherwise convert the integer to a string

This approach works because every number independently falls into exactly one of these categories. By evaluating each condition directly, we guarantee the correct output for every position in the array.

Since we process each number exactly once and each divisibility check takes constant time, this solution is already efficient enough for the problem constraints.

Key Insight for the Optimal Solution

The key observation is that the problem does not require any repeated computation, nested iteration, or auxiliary search structure. Each number can be classified independently in constant time.

Because divisibility checks are extremely cheap operations, the optimal solution is simply a single linear traversal from 1 to n.

A small implementation improvement is to build the output string incrementally:

• Start with an empty string
• Append "Fizz" if divisible by 3
• Append "Buzz" if divisible by 5
• If the string remains empty, use the numeric value instead

This avoids explicitly checking the combined 15 condition and keeps the implementation clean and extensible.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Directly checks all divisibility conditions for every number
Optimal	O(n)	O(n)	Single pass using incremental string construction

Algorithm Walkthrough

1. Initialize an empty result list that will store the final strings.
2. Iterate through all integers from 1 to n, inclusive. Each iteration determines the correct representation for one number.
3. For the current number, create an empty temporary string.
4. Check whether the number is divisible by 3. If it is, append "Fizz" to the temporary string. This works because any multiple of 3 must contribute the "Fizz" portion of the output.
5. Check whether the number is divisible by 5. If it is, append "Buzz" to the temporary string. If the number is divisible by both 3 and 5, the string automatically becomes "FizzBuzz".
6. After both checks, determine whether the temporary string is still empty. If it is empty, the number was divisible by neither 3 nor 5, so convert the number itself to a string.
7. Append the final string for this number into the result list.
8. Continue until all numbers from 1 through n have been processed.
9. Return the completed result list.

Why it works

Every integer from 1 to n belongs to exactly one of four categories:

• Divisible by both 3 and 5
• Divisible only by 3
• Divisible only by 5
• Divisible by neither

The algorithm checks divisibility systematically and constructs the correct string representation for each category. Since every number is processed exactly once and appended exactly once, the returned array is complete and correctly ordered.

Python Solution

from typing import List

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        result = []

        for number in range(1, n + 1):
            current = ""

            if number % 3 == 0:
                current += "Fizz"

            if number % 5 == 0:
                current += "Buzz"

            if current == "":
                current = str(number)

            result.append(current)

        return result

The implementation begins by creating an empty list called result, which stores the final output.

The loop iterates from 1 through n. For each number, a temporary string named current is initialized as empty.

The first condition checks divisibility by 3. If true, "Fizz" is appended. The second condition checks divisibility by 5. If both conditions are true, the concatenation naturally forms "FizzBuzz".

After the divisibility checks, the code determines whether anything was added to current. If the string is still empty, the number itself is converted to a string.

Finally, the computed value is appended to the result list. Once all numbers are processed, the list is returned.

Go Solution

func fizzBuzz(n int) []string {
    result := make([]string, 0, n)

    for number := 1; number <= n; number++ {
        current := ""

        if number%3 == 0 {
            current += "Fizz"
        }

        if number%5 == 0 {
            current += "Buzz"
        }

        if current == "" {
            current = fmt.Sprintf("%d", number)
        }

        result = append(result, current)
    }

    return result
}

The Go implementation follows the same logic as the Python version. The primary difference is that Go slices are explicitly initialized with capacity using make.

String conversion is handled using fmt.Sprintf("%d", number). Another common alternative would be strconv.Itoa(number), which is slightly more efficient for integer conversion.

Unlike Python lists, Go slices benefit from preallocated capacity because it reduces internal resizing during append operations.

Worked Examples

Example 1

Input:

n = 3

Processing steps:

Number	Divisible by 3	Divisible by 5	Output Added	Result
1	No	No	"1"	["1"]
2	No	No	"2"	["1","2"]
3	Yes	No	"Fizz"	["1","2","Fizz"]

Final output:

["1","2","Fizz"]

Example 2

Input:

n = 5

Processing steps:

Number	Divisible by 3	Divisible by 5	Output Added	Result
1	No	No	"1"	["1"]
2	No	No	"2"	["1","2"]
3	Yes	No	"Fizz"	["1","2","Fizz"]
4	No	No	"4"	["1","2","Fizz","4"]
5	No	Yes	"Buzz"	["1","2","Fizz","4","Buzz"]

Final output:

["1","2","Fizz","4","Buzz"]

Example 3

Input:

n = 15

Key iterations:

Number	Generated String
1	"1"
2	"2"
3	"Fizz"
5	"Buzz"
6	"Fizz"
9	"Fizz"
10	"Buzz"
12	"Fizz"
15	"FizzBuzz"

Final output:

["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each number from 1 through n is processed once
Space	O(n)	The output list stores n strings

The algorithm performs a constant amount of work for each integer in the range. Divisibility checks and string concatenations are constant-time operations for these small fixed strings.

The space complexity is linear because the returned output itself contains n elements. Aside from the output array, the algorithm uses only a few temporary variables.

Test Cases

from typing import List

class Solution:
    def fizzBuzz(self, n: int) -> List[str]:
        result = []

        for number in range(1, n + 1):
            current = ""

            if number % 3 == 0:
                current += "Fizz"

            if number % 5 == 0:
                current += "Buzz"

            if current == "":
                current = str(number)

            result.append(current)

        return result

solution = Solution()

assert solution.fizzBuzz(1) == ["1"]  # Minimum valid input

assert solution.fizzBuzz(3) == [
    "1", "2", "Fizz"
]  # Multiple of 3

assert solution.fizzBuzz(5) == [
    "1", "2", "Fizz", "4", "Buzz"
]  # Multiple of 5

assert solution.fizzBuzz(15) == [
    "1", "2", "Fizz", "4", "Buzz",
    "Fizz", "7", "8", "Fizz", "Buzz",
    "11", "Fizz", "13", "14", "FizzBuzz"
]  # Multiple of both 3 and 5

assert solution.fizzBuzz(6) == [
    "1", "2", "Fizz", "4", "Buzz", "Fizz"
]  # Repeated Fizz values

assert solution.fizzBuzz(10) == [
    "1", "2", "Fizz", "4", "Buzz",
    "Fizz", "7", "8", "Fizz", "Buzz"
]  # Mixed sequence

assert solution.fizzBuzz(30)[14] == "FizzBuzz"  # 15th element

assert solution.fizzBuzz(30)[29] == "FizzBuzz"  # 30th element

assert len(solution.fizzBuzz(100)) == 100  # Large input size

Test	Why
n = 1	Validates the minimum boundary value
n = 3	Ensures multiples of 3 become "Fizz"
n = 5	Ensures multiples of 5 become "Buzz"
n = 15	Ensures multiples of both 3 and 5 become "FizzBuzz"
n = 6	Verifies repeated "Fizz" generation
n = 10	Validates mixed outputs across multiple conditions
n = 30 index 14	Confirms correct handling of 15
n = 30 index 29	Confirms correct handling of 30
n = 100	Verifies behavior on larger valid inputs

Edge Cases

One important edge case is the minimum input value, n = 1. A buggy implementation might incorrectly assume at least one divisibility match exists. In this case, the algorithm correctly returns ["1"] because neither divisibility condition is satisfied.

Another critical edge case involves numbers divisible by both 3 and 5, such as 15 or 30. A common mistake is checking divisibility by 3 first and immediately returning "Fizz", which prevents "FizzBuzz" from ever being produced. The implementation avoids this issue by independently appending "Fizz" and "Buzz" into the same string.

A third edge case is handling consecutive special values. For example, around the range 14, 15, and 16, the output transitions from a normal number to "FizzBuzz" and back to a normal number. The implementation correctly resets the temporary string during every iteration, preventing leftover values from previous iterations from affecting future outputs.