Generate Binary Numbers

JavaView on GFG

Time: O(n)

Space: O(n)

Intuition

BFS: start with "1". For each number, append "0" and "1" to get next numbers. Queue-based generation.

Algorithm

1Queue with "1".
2For i from 1 to n: dequeue s, add to result, enqueue s+"0" and s+"1".

Common Pitfalls

•This generates binary representations in order 1,10,11,100,101,...

Generate Binary Numbers.java

Java

// Approach: BFS queue. Start with '1', for each dequeued string enqueue it + '0' and it + '1'.
// Time: O(n) Space: O(n)
import java.util.*;

class Solution {
    public ArrayList<String> generateBinary(int n) {
        Queue<String> q = new LinkedList<>();
        ArrayList<String> ans = new ArrayList<>();

        q.add("1");

        while (n-- != 0) {
            String curr = q.peek();
            ans.add(q.poll());
            q.add(curr + "0");
            q.add(curr + "1");
        }

        return ans;
    }
}

Was this solution helpful?