Log inSign up
easyLeetCodeNot Started

Add Binary

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Strings
Solve on LeetCode
Lesson

Problem Statement

Given two binary strings a and b, return *their sum as a binary string*.

Example 1 · Example:

Input: a = "11", b = "1"
Output: "100"
Explanation: 11 (3 in decimal) + 1 (1 in decimal) = 4 in decimal ("100" in binary).

Example 2 · Example:

Input: a = "1010", b = "1011"
Output: "10101"
Explanation: 1010 (10 in decimal) + 1011 (11 in decimal) = 21 in decimal ("10101" in binary).

Constraints:

  • 1 <= a.length, b.length <= 10^4
  • a and b consist only of '0' or '1' characters.
  • Each string does not contain leading zeros except for the zero itself.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the core string patterns underlying Add Binary.
  • Optimize time and space tradeoffs for string manipulation.
  • Handle string boundary conditions and unicode/ASCII edge cases.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Simulating columnar addition on strings representing numbers.
  • Arbitrary length numerical inputs requiring carry propagation from least to most significant digit.

Algorithmic Decision Tree:

  • Right-to-Left Carry Propagation
  • Two Pointers from Tail

Connected Patterns:

Add StringsMultiply StringsAdd Two Numbers (Linked List)

1. Brute Force

Algorithm

  1. Iterate through string a, computing decimal value: valA = valA * 2 + (bit - '0').
  2. Iterate through string b, computing decimal value: valB = valB * 2 + (bit - '0').
  3. Compute direct integer sum: total = valA + valB.
  4. Convert total back to binary string using continuous division by 2 or .toString(2).
  5. Highlight overflow limitation: on binary inputs > 53 bits, floating-point IEEE-754 precision is lost.

Binary Radix Conversion & Direct Integer Addition Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 0, 1, 1]
Current operationSTEP 1 OF 6
Observation: Scanning a = "1011" from MSB to LSB
Visual state
Values and pointers at this exact step
array
S
1
0
1
1
0
↑ i=0 ('1')
1
2
3
Variables at this step
String
a
Bit
'1'
Index
0
Partial valA
1
Check / comparison
valA = 0 * 2 + 1 = 1
Decision / next transition
Parse leading bit '1'. Accumulated decimal is 1.
Why this step matters

Observation: Scanning a = "1011" from MSB to LSB. Process bit '1' at index 0.

Decision: Shift existing value by base 2: valA = 0 * 2 + 1 = 1.

Invariant: Numerical value of prefix "1" is 1_{10}.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5// Note: Standard C++ does not have arbitrary-precision BigInt natively,
6// so manual binary addition is standard.
7class Solution {
8public:
9 std::string addBinary(std::string a, std::string b) {
10 std::string res = "";
11 int i = a.size() - 1, j = b.size() - 1, carry = 0;
12 while (i >= 0 || j >= 0 || carry) {
13 int sum = carry;
14 if (i >= 0) sum += a[i--] - '0';
15 if (j >= 0) sum += b[j--] - '0';
16 res += std::to_string(sum % 2);
17 carry = sum / 2;
18 }
19 std::reverse(res.begin(), res.end());
20 return res;
21 }
22};
23
24int main() {
25 Solution sol;
26 std::cout << sol.addBinary("11", "1") << std::endl; // Output: 100
27 std::cout << sol.addBinary("1010", "1011") << std::endl; // Output: 10101
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(N + M) — Single pass over each binary string to compute its decimal value.
  • Space complexity: O(1) — O(1) auxiliary space beyond scalar variables.

Why Brute Force Doesn't Scale:

Naive brute force re-examines already processed substrings multiple times.

For N = 105, O(N2) requires 1010 operations (TLE), while O(N) finishes in < 10ms.

2. Better Approach

Algorithm

  1. Push all characters of string a onto stackA.
  2. Push all characters of string b onto stackB.
  3. Initialize carry = 0 and empty resultBuffer.
  4. While either stack is non-empty or carry > 0, pop bits, compute sum, append sum % 2, and update carry.
  5. Reverse the result buffer and return.

LIFO Stack-Based Right-to-Left Bit Processing

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 0, 1, 1]
Current operationSTEP 1 OF 6
Observation: Both strings pushed to stacks
Visual state
Values and pointers at this exact step
array
S
1
0
1
1
0
1
2
3
Variables at this step
Popped A
1
Popped B
1
Carry
1
Buffer
['0']
Check / comparison
Pop A: 1, Pop B: 1. sum = 1 + 1 + 0 = 2. Bit = 0, Carry = 1.
Decision / next transition
Pop units bits. Append '0' to buffer. Carry = 1.
Why this step matters

Observation: Both strings pushed to stacks. Pop top elements: bitA = 1, bitB = 1, carry = 0.

Decision: sum = 1 + 1 + 0 = 2. Current bit = 0, next carry = 1.

Invariant: Units bit is 0; carry propagates.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <stack>
4
5class Solution {
6public:
7 std::string addBinary(std::string a, std::string b) {
8 std::stack<char> s1, s2;
9 for (char c : a) s1.push(c);
10 for (char c : b) s2.push(c);
11
12 std::string res = "";
13 int carry = 0;
14
15 while (!s1.empty() || !s2.empty() || carry) {
16 int sum = carry;
17 if (!s1.empty()) {
18 sum += s1.top() - '0';
19 s1.pop();
20 }
21 if (!s2.empty()) {
22 sum += s2.top() - '0';
23 s2.pop();
24 }
25 res.push_back((sum % 2) + '0');
26 carry = sum / 2;
27 }
28
29 std::reverse(res.begin(), res.end());
30 return res;
31 }
32};
33
34int main() {
35 Solution sol;
36 std::cout << sol.addBinary("11", "1") << std::endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N + M) — Pushing all characters to two stacks and popping column-by-column takes linear time.
  • Space complexity: O(N + M) — Allocates O(N + M) auxiliary space for the two stacks.

3. Two Pointers Right-to-Left Carry Accumulator

Intuition

1. Initialize pointer i = a.length - 1, j = b.length - 1, and carry = 0. 2. While i >= 0 || j >= 0 || carry > 0: - sum = carry - If i >= 0, sum += a[i] - '0', i-- - If j >= 0, sum += b[j] - '0', j-- - Append sum % 2 to result buffer. - carry = sum / 2 3. Reverse the accumulated buffer and return the string.

When to apply: The definitive, optimal industry solution for string arithmetic (handles up to 104 characters easily).

Algorithm

  1. Initialize two tail pointers i and j and carry = 0.
  2. Loop while either pointer is valid or carry remains.
  3. Accumulate digit values and update carry.
  4. Append sum % 2 to output buffer.
  5. Reverse and return final binary string.

Column-by-Column Binary Addition with Ripple Carry

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 0, 1, 1]
Current operationSTEP 1 OF 6
Observation: Initialize pointers at least significant bits: a[3]='1', b[2]='1', and carry=0
Visual state
Values and pointers at this exact step
array
S
1
0
1
1
0
1
2
3
Variables at this step
i Pointer
3 (a[3]='1')
j Pointer
2 (b[2]='1')
Carry
0
Sum
2
Emitted Bit
0
Result
0
Check / comparison
bitA (1) + bitB (1) + carry (0) = 2. Digit = 2 % 2 = 0, Carry = 1.
Decision / next transition
Prepend '0' to result. Carry becomes 1 for next column.
Why this step matters

Observation: Initialize pointers at least significant bits: a[3]='1', b[2]='1', and carry=0.

Decision: Calculate sum: 1 + 1 + 0 = 2. The current bit is 2 % 2 = 0, and new carry is Math.floor(2 / 2) = 1.

Invariant: Prepend '0' to result; carry becomes 1 for the next column.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5class Solution {
6public:
7 std::string addBinary(std::string a, std::string b) {
8 std::string result;
9 int i = a.size() - 1;
10 int j = b.size() - 1;
11 int carry = 0;
12
13 while (i >= 0 || j >= 0 || carry) {
14 int sum = carry;
15 if (i >= 0) sum += a[i--] - '0';
16 if (j >= 0) sum += b[j--] - '0';
17 result.push_back((sum % 2) + '0');
18 carry = sum / 2;
19 }
20
21 std::reverse(result.begin(), result.end());
22 return result;
23 }
24};
25
26int main() {
27 Solution sol;
28 std::cout << sol.addBinary("11", "1") << std::endl; // Output: "100"
29 std::cout << sol.addBinary("1010", "1011") << std::endl; // Output: "10101"
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(max(N, M)) — We perform a single simultaneous pass over the maximum length max(N, M) of the two strings.
  • Space complexity: O(1) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.BigInt / Direct Radix ParsingO(N + M)O(N + M)Convert both binary strings to arbitrary-precision integers, calculate their sum, and format the sum back to a binary string.Time / space complexity limits.
2.Stack-Based Character ProcessingO(max(N, M))O(N + M)Push characters of both strings onto stacks, and pop them together while computing bit sums and carries.Time / space complexity limits.
3.Two Pointers Right-to-Left Carry AccumulatorOptimalO(max(N, M))O(1) auxiliaryTraverse both strings simultaneously from right to left using two index pointers. Compute the bit sum and carry, appending each digit directly to a dynamic string builder in O(1) auxiliary space.Time / space complexity limits.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting the final carry: loop must continue while carry > 0 even when both i < 0 and j < 0.

Pitfall 2:

Integer overflow when parsing string directly into primitive 32/64-bit integer types (1 <= length <= 10^4).

Pitfall 3:

Forgetting to reverse the string buffer before returning (digits are appended in least-significant to most-significant order).

Crucial Edge Cases to Validate:

  • Empty string or single character string.
  • String with duplicate or repeating characters.
  • Strings with different lengths or extreme character bounds.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify character constraints (lowercase English only vs full Unicode/ASCII).
  2. Explain your choice of data structure (array frequency map vs hash table) before coding.
  3. Walk through a concrete small example during the dry run.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time complexity for Add Binary?

Back to DSA Sheet