LeetCode 415 - Add Strings

LeetCode Problem 415

Difficulty: 🟢 Easy
Topics: Math, String, Simulation

Solution

Problem Understanding

The problem asks us to add two non-negative integers where each integer is given as a string instead of a numeric type. The goal is to return the resulting sum as another string.

For example, if the inputs are "11" and "123", we should return "134".

The important restriction is that we are not allowed to convert the entire strings into integers directly. That means approaches such as int(num1) + int(num2) in Python or using large integer libraries are forbidden. The problem is specifically testing whether we can simulate manual addition digit by digit.

The input strings contain only numeric characters from '0' to '9', and the strings can be very large, up to length 10^4. This size is significant because many programming languages cannot safely store integers of that magnitude in built-in numeric types. Even if a language technically supports arbitrary precision integers, the problem explicitly forbids using them.

The output should be the exact decimal representation of the sum, also as a string.

Several edge cases are important to consider:

• The numbers can have different lengths, such as "1" and "9999".
• One or both numbers can be "0".
• The final addition may produce an extra carry digit, such as "999" + "1" = "1000".
• Since the inputs have no leading zeros except "0" itself, we do not need to handle malformed formatting cases.

The problem is essentially asking us to simulate the same process humans use when adding numbers on paper, starting from the least significant digit and moving leftward while carrying overflow values forward.

Approaches

Brute Force Approach

The most obvious solution is to convert both strings into integers, add them, and then convert the result back into a string.

Conceptually, this works because integer arithmetic already handles carrying internally. The implementation would be extremely short and easy to understand.

However, this approach violates the problem constraints because the problem explicitly forbids converting the inputs directly into integers or using built-in large integer support.

Additionally, for very large inputs, standard integer types in many languages would overflow.

Optimal Approach

The correct approach is to simulate elementary school addition manually.

The key observation is that addition only requires processing one digit at a time from right to left. At each position:

• Add the current digit from num1
• Add the current digit from num2
• Add any carry from the previous step
• Store the resulting digit
• Carry forward the overflow

Since characters representing digits can easily be converted into their numeric values individually, we can process the strings without ever converting the full numbers into integers.

This approach works efficiently because each digit is processed exactly once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Converts entire strings into integers, violates constraints
Optimal	O(n)	O(n)	Simulates digit-by-digit addition manually

Algorithm Walkthrough

1. Initialize two pointers at the end of each string.

The rightmost digit represents the least significant place value, so addition must begin there. We use one pointer for num1 and another for num2. 2. Initialize a carry variable.

The carry stores overflow from the previous digit addition. Initially, there is no overflow, so the carry starts at 0. 3. Create a result container.

Since strings are immutable in many languages, repeatedly concatenating strings can be inefficient. Instead, we store digits in a list or slice and join them later. 4. Process digits while either pointer is still valid or a carry remains.

Even if one string is shorter than the other, we must continue processing the remaining digits of the longer string. We also must continue if there is a leftover carry after all digits are processed. 5. Extract the current digits.

If a pointer is still within bounds, convert the character digit into its integer value. Otherwise, use 0. 6. Compute the total for the current position.

Add:

• digit from num1
• digit from num2
• current carry

7. Determine the new digit and carry.

The ones place becomes the output digit:

$\text{digit} = \text{total} \bmod 10$

The tens place becomes the new carry:

$\text{carry} = \left\lfloor \frac{\text{total}}{10} \right\rfloor$ 8. Append the resulting digit to the result container.

Since we are processing from right to left, digits are produced in reverse order. 9. Move both pointers leftward.

This advances the addition process to the next more significant digit. 10. Reverse the result and convert it into a string.

Because digits were collected from least significant to most significant, reversing restores the correct order.

Why it works

At every iteration, the algorithm correctly computes the sum for one decimal place while preserving overflow in the carry variable. This exactly matches the rules of base-10 arithmetic. Since every digit is processed once and carries are propagated correctly, the final result is guaranteed to equal the mathematical sum of the two input numbers.

Python Solution

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i = len(num1) - 1
        j = len(num2) - 1
        
        carry = 0
        result = []
        
        while i >= 0 or j >= 0 or carry:
            digit1 = ord(num1[i]) - ord('0') if i >= 0 else 0
            digit2 = ord(num2[j]) - ord('0') if j >= 0 else 0
            
            total = digit1 + digit2 + carry
            
            result.append(str(total % 10))
            carry = total // 10
            
            i -= 1
            j -= 1
        
        result.reverse()
        
        return ''.join(result)

The implementation begins by placing two pointers at the ends of the input strings. These positions correspond to the least significant digits.

The carry variable stores overflow from the previous addition step. The result list collects digits as they are computed.

Inside the loop, the current digits are extracted if the pointers are valid. If one pointer has already moved past the beginning of its string, the corresponding digit is treated as 0. This allows the algorithm to naturally handle numbers of different lengths.

The total for the current position is computed by adding both digits and the carry. The current output digit is obtained using modulo 10, while integer division by 10 produces the new carry.

Each generated digit is appended to the result list. Because digits are processed from right to left, the list is reversed at the end before joining into the final string.

This implementation never converts the entire input into an integer, so it satisfies all problem constraints.

Go Solution

func addStrings(num1 string, num2 string) string {
	i := len(num1) - 1
	j := len(num2) - 1

	carry := 0
	result := []byte{}

	for i >= 0 || j >= 0 || carry > 0 {
		digit1 := 0
		digit2 := 0

		if i >= 0 {
			digit1 = int(num1[i] - '0')
		}

		if j >= 0 {
			digit2 = int(num2[j] - '0')
		}

		total := digit1 + digit2 + carry

		result = append(result, byte(total%10)+'0')
		carry = total / 10

		i--
		j--
	}

	left := 0
	right := len(result) - 1

	for left < right {
		result[left], result[right] = result[right], result[left]
		left++
		right--
	}

	return string(result)
}

The Go solution follows the same algorithmic structure as the Python implementation, but there are a few language-specific details.

Go strings are byte slices internally, so digit extraction can be done directly with num1[i] - '0'.

The result is stored as a []byte instead of a string because repeatedly concatenating strings in Go is inefficient. After all digits are collected and reversed, the byte slice is converted into a string.

Unlike Python, Go does not provide built-in arbitrary precision integers for normal integer types, so this manual addition method is especially important for very large inputs.

Worked Examples

Example 1

Input:

num1 = "11"
num2 = "123"

Step	i	j	digit1	digit2	carry before	total	result
1	1	2	1	3	0	4	["4"]
2	0	1	1	2	0	3	["4", "3"]
3	-1	0	0	1	0	1	["4", "3", "1"]

After reversing:

"134"

Example 2

Input:

num1 = "456"
num2 = "77"

Step	i	j	digit1	digit2	carry before	total	result
1	2	1	6	7	0	13	["3"]
2	1	0	5	7	1	13	["3", "3"]
3	0	-1	4	0	1	5	["3", "3", "5"]

After reversing:

"533"

Example 3

Input:

num1 = "0"
num2 = "0"

Step	i	j	digit1	digit2	carry before	total	result
1	0	0	0	0	0	0	["0"]

After reversing:

"0"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each digit is processed exactly once
Space	O(n)	The result storage may contain up to n + 1 digits

Here, n represents the length of the longer input string.

The algorithm performs a single pass from right to left across both strings. Every operation inside the loop takes constant time, so the total runtime grows linearly with input size.

The extra space comes primarily from the result container, which stores the digits of the final sum.

Test Cases

solution = Solution()

assert solution.addStrings("11", "123") == "134"      # basic example
assert solution.addStrings("456", "77") == "533"      # different lengths
assert solution.addStrings("0", "0") == "0"           # both zero

assert solution.addStrings("1", "9") == "10"          # single-digit carry
assert solution.addStrings("99", "1") == "100"        # carry creates new digit
assert solution.addStrings("9999", "9999") == "19998" # repeated carries

assert solution.addStrings("123", "0") == "123"       # adding zero
assert solution.addStrings("0", "456") == "456"       # zero as first operand

assert solution.addStrings("1", "999999") == "1000000" # very uneven lengths
assert solution.addStrings("500", "500") == "1000"     # carry at highest digit

large1 = "9" * 10000
large2 = "1"
expected = "1" + ("0" * 10000)

assert solution.addStrings(large1, large2) == expected # maximum size stress test

Test	Why
"11", "123"	Verifies normal addition
"456", "77"	Verifies different-length inputs
"0", "0"	Verifies zero handling
"1", "9"	Verifies single carry
"99", "1"	Verifies extra digit creation
"9999", "9999"	Verifies repeated carry propagation
"123", "0"	Verifies adding zero
"0", "456"	Verifies zero as first operand
"1", "999999"	Verifies uneven input lengths
"500", "500"	Verifies carry at highest position
Very large input	Verifies scalability and constraint handling

Edge Cases

Different Length Inputs

One number may contain significantly more digits than the other, such as "1" and "999999".

A naive implementation might stop too early when the shorter string is exhausted. This implementation avoids that issue by continuing the loop while either pointer is still valid. Missing digits are treated as 0, which correctly mirrors manual addition.

Final Carry After All Digits

Cases like "999" and "1" produce an additional digit in the result.

This is a common source of bugs because the carry remains after all original digits have been processed. The loop condition explicitly includes or carry, ensuring the leftover carry is appended correctly.

Inputs Equal to Zero

When both inputs are "0", the correct output should also be "0".

Some implementations accidentally produce an empty string or mishandle leading zeros. Since this algorithm always processes at least one iteration when digits exist, the result correctly becomes "0".