📖 6 min read
Last updated on

Add Binary — Coding Interview Walkthrough

By intervu.dev

Hero Image for Add Binary — Coding Interview Walkthrough

The core approach: Add Binary is solved by simulating bit-by-bit addition from right to left in O(max(m,n)) time and O(max(m,n)) space. Iterate from the least significant bit, summing digits and a carry. Append any remaining carry, then reverse the accumulated result to get the final binary sum string.

You’re in a coding interview. The interviewer says: “Given two binary strings, return their sum as a binary string.” You know the algorithm: simulate digit-by-digit addition from right to left, maintaining a carry. But the implementation details trip people up: carry handling, unequal-length strings, and how to traverse from the end without reversing. This is LeetCode #67, and getting every edge case right on the first try is what separates a clean solve from a messy one.

This walkthrough covers the pointer-based simulation approach, the Pythonic shortcut, and the common traps candidates fall into.

Already know how to solve Add Binary? Try a Add Binary mock interview on Intervu →

The Problem

Given two binary strings a and b, return their sum as a binary string. (LeetCode #67)

Example 1

Input: a = "11", b = "1" Output: "100"

Example 2

Input: a = "1010", b = "1011" Output: "10101"

What Interviewers Are Actually Testing

SkillWhat Interviewers Observe
Right-to-left pointer traversalDo you use indices from the end instead of reversing?
Carry propagationDo you handle the final carry after the loop?
Unequal length stringsDoes your code handle strings of different lengths correctly?
String buildingDo you use a list and join at the end instead of string concatenation?

Step 1: Clarifying Questions

1. Can the strings be empty? Assume at least one character per constraints.

2. Leading zeros in input? Problem guarantees no leading zeros (except “0” itself).

3. Should the output have leading zeros? No. Match standard binary representation.

Step 2: A First (Non-Optimal) Idea

Convert both binary strings to integers, add them, and convert back to binary. This works, but interviewers typically want the simulation approach since it demonstrates low-level addition mechanics.

ApproachTimeSpace
SimulationO(max(m, n))O(max(m, n))
Python built-insO(max(m, n))O(max(m, n))

Step 3: The Key Insight

Simulate binary addition right-to-left, maintaining a carry. Use two pointers starting from the end of each string (no reversal needed). At each step: digit_sum = a[i] + b[j] + carry. The result bit is digit_sum % 2, and the new carry is digit_sum // 2. After the loop, handle any remaining carry.

Result array [1,0,0] from adding '11' + '1'. Carry pointer shown above, demonstrating right-to-left carry-based addition. ---

Step 4: Algorithm

  1. Initialize two pointers i and j at the ends of a and b.
  2. Initialize carry = 0 and a result list.
  3. While either pointer is valid or carry is non-zero:
    • Add a[i], b[j] (if valid), and carry.
    • Append digit_sum % 2 to result.
    • Update carry to digit_sum // 2.
  4. Reverse and join the result list.

Python Implementation

Simulation approach:

def addBinary(a: str, b: str) -> str:
    i, j = len(a) - 1, len(b) - 1
    carry = 0
    result = []

    while i >= 0 or j >= 0 or carry:
        digit_sum = carry
        if i >= 0:
            digit_sum += int(a[i])
            i -= 1
        if j >= 0:
            digit_sum += int(b[j])
            j -= 1

        result.append(str(digit_sum % 2))  # Current bit
        carry = digit_sum // 2             # New carry

    return ''.join(reversed(result))

Pythonic shortcut (acceptable, but discuss trade-offs):

def addBinary(a: str, b: str) -> str:
    return bin(int(a, 2) + int(b, 2))[2:]

int(a, 2) converts a binary string to an integer, bin() converts back, and [2:] strips the "0b" prefix. Clean but uses built-in conversion. Ask the interviewer if this is acceptable.

Time and Space Complexity

AspectComplexity
TimeO(max(m, n))
SpaceO(max(m, n)), for the result list

Common Interview Mistakes

  • Using + to build a string in a loop. String concatenation in a loop is O(n²) in Python. Use a list and join at the end.

  • Forgetting the final carry. If both strings are exhausted but carry == 1, you must append it. The or carry condition in the while loop handles this.

  • Reversing the input strings. You can traverse from the end using indices. No need to reverse.

  • Not mentioning the built-in approach. Show both and let the interviewer decide. If they want the simulation, the built-in shows you know the language.

What a Strong Candidate Sounds Like

“I’ll simulate binary addition right-to-left with two pointers and a carry variable. At each step, digit_sum = a[i] + b[j] + carry. The result bit is digit_sum % 2, carry is digit_sum // 2. I continue while either index is valid or carry is nonzero. I collect digits in a list (not string concatenation, to avoid O(n²) cost), then join and reverse. There’s also a Pythonic one-liner using int(a, 2) and bin() if built-ins are acceptable.”

Example Interview Dialogue

Interviewer: What happens when the strings have different lengths?

Candidate: The while loop condition uses or, so it continues as long as at least one pointer is valid. When a shorter string is exhausted, only the other string’s digits are added to the carry. This naturally handles unequal lengths without special cases.

From the Intervu walkthrough collection:

Frequently Asked Questions

What is the optimal time complexity for the Add Binary problem?

The optimal approach achieves O(max(N, M)) time complexity, where N and M are the lengths of the two binary strings. This single-pass method iteratively processes both strings from right to left while managing the carry step mathematically. Learn how to elegantly manage strings of different lengths in the walkthrough above.

Is converting binary strings to integers an acceptable solution for Add Binary?

Generally, no. While languages like Python implicitly handle arbitrarily large integers, converting to base-10 bypasses the core string manipulation skills interviewers are actually testing for. True mastery is demonstrated by keeping the entire operation within bit manipulation or explicit character mathematics.

Practice This in a Mock Interview

Add Binary is fast to code but exposes sloppy habits like string concatenation in loops and forgotten carry bits. A clean, bug-free first attempt is what interviewers are looking for.

Start a mock interview for Add Binary on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →