Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Binary addition follows the same column-by-column process as decimal addition, but each column stores its total modulo two and carries the quotient into the next column. Starting from the right keeps digits with the same place value aligned even when the strings have different lengths.

Approach

Place a pointer at the last character of each string and initialize a carry to zero.
Add each available digit to the carry. An exhausted string contributes zero.
Append the total modulo two to a result list, then divide the total by two using integer division to obtain the next carry.
Continue while either string has digits or the carry is nonzero. This final condition preserves a new leading bit.
Reverse and join the collected digits, which were generated from least to most significant.

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

        while i >= 0 or j >= 0 or carry:
            if i >= 0:
                carry += int(a[i])
                i -= 1
            if j >= 0:
                carry += int(b[j])
                j -= 1
            res.append(str(carry % 2))
            carry //= 2

        return "".join(res[::-1])

Complexity analysis

For string lengths n = a.length and m = b.length, the right-to-left addition takes O(n + m) time. Both implementations build an O(n + m) digit array and materialize an O(n + m) reversed copy before joining, so auxiliary space is O(n + m), excluding the final O(n + m) output string.