Scale Engineer

Fizz Buzz

Easy
#0399Time: O(n * k), where n is the input number and k is the number of divisibility rules. Since k is a small constant, this is effectively O(n), but it has more overhead than hardcoded solutions.Space: O(n) to store the output array. An additional O(k) space is used for the map, where k is the number of rules.11 companies
Patterns
Math
Data structures
String
Companies
CiscoCognizantIBMJ.P. Morgan

Prompt

Given an integer n, return a string array answer (1-indexed) where:

  • answer[i] == "FizzBuzz" if i is divisible by 3 and 5.
  • answer[i] == "Fizz" if i is divisible by 3.
  • answer[i] == "Buzz" if i is divisible by 5.
  • answer[i] == i (as a string) if none of the above conditions are true.

 

Example 1:

Input: n = 3
Output: ["1","2","Fizz"]

Example 2:

Input: n = 5
Output: ["1","2","Fizz","4","Buzz"]

Example 3:

Input: n = 15
Output: ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

 

Constraints:

  • 1 <= n <= 104

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a hash map to store the divisibility rules. It's the most flexible and scalable solution, as new rules can be added just by modifying the map. The code iterates through the numbers from 1 to n, and for each number, it checks against all the rules in the map to build the corresponding string.

Algorithm

  • Create a map (e.g., LinkedHashMap to preserve order) to store divisor-string pairs (e.g., 3 -> "Fizz", 5 -> "Buzz").
  • Initialize an empty list for the results.
  • Loop from i = 1 to n.
  • For each i, initialize an empty StringBuilder.
  • Iterate through the map's entries. If i is divisible by the entry's key, append the entry's value to the StringBuilder.
  • If the StringBuilder is empty after checking all rules, append the number i.
  • Add the StringBuilder's content to the result list.
  • Return the result list.

Walkthrough

This is the most scalable and generic approach. We store the divisibility rules in a data structure, like a hash map. The main loop then iterates through these rules to build the output string. This decouples the rules from the processing logic, making the code very clean and easy to extend without modification.

import java.util.ArrayList;import java.util.LinkedHashMap;import java.util.List;import java.util.Map; class Solution {    public List<String> fizzBuzz(int n) {        List<String> answer = new ArrayList<>();        // Using LinkedHashMap to maintain insertion order ("Fizz" before "Buzz")        Map<Integer, String> fizzBuzzMap = new LinkedHashMap<>();        fizzBuzzMap.put(3, "Fizz");        fizzBuzzMap.put(5, "Buzz");         for (int i = 1; i <= n; i++) {            StringBuilder currentString = new StringBuilder();            for (Integer key : fizzBuzzMap.keySet()) {                if (i % key == 0) {                    currentString.append(fizzBuzzMap.get(key));                }            }             if (currentString.length() == 0) {                currentString.append(i);            }                        answer.add(currentString.toString());        }        return answer;    }}

Complexity

Time

O(n * k), where n is the input number and k is the number of divisibility rules. Since k is a small constant, this is effectively O(n), but it has more overhead than hardcoded solutions.

Space

O(n) to store the output array. An additional O(k) space is used for the map, where k is the number of rules.

Trade-offs

Pros

  • Highly flexible and scalable.

  • Follows the Open/Closed Principle, as new rules can be added without modifying the core logic.

Cons

  • Slightly more complex to implement than simpler approaches.

  • Has a higher constant factor for time complexity, making it potentially slower for this specific problem with few rules.

Solutions

const fizzBuzz = function ( n ) { let arr = []; for ( let i = 1 ; i <= n ; i ++ ) { if ( i % 15 === 0 ) arr . push ( ' FizzBuzz ' ); else if ( i % 3 === 0 ) arr . push ( ' Fizz ' ); else if ( i % 5 === 0 ) arr . push ( ' Buzz ' ); else arr . push ( ` ${ i } ` ); } return arr ; };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem