Log inSign up
easyLeetCodeNot Started

Add Strings

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

Strings
Solve on LeetCode
Lesson

Problem Statement

Given two non-negative integers, num1 and num2 represented as string, return *the sum of num1 and num2 as a string*.

You must solve the problem without using any built-in BigInteger library or converting the inputs to integer directly.

Example 1 · Example:

Input: num1 = "11", num2 = "123"
Output: "134"
Explanation: 11 + 123 = 134.

Example 2 · Example:

Input: num1 = "456", num2 = "77"
Output: "533"
Explanation: 456 + 77 = 533.

Example 3 · Example:

Input: num1 = "0", num2 = "0"
Output: "0"
Explanation: 0 + 0 = 0.

Constraints:

  • 1 <= num1.length, num2.length <= 10^4
  • num1 and num2 consist of only digits.
  • num1 and num2 don't have any 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 Strings.
  • 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:

  • Arbitrary-precision arithmetic on numeric strings without converting to primitive integers.
  • Digit-by-digit columnar calculation with carry propagation.

Algorithmic Decision Tree:

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

Connected Patterns:

Add BinaryMultiply StringsPlus One

1. Brute Force

Algorithm

  1. Scan num1 from left to right, accumulating numeric value: val1 = val1 * 10 + (c - '0').
  2. Scan num2 from left to right, accumulating numeric value: val2 = val2 * 10 + (c - '0').
  3. Compute direct integer sum: sum = val1 + val2.
  4. Format the resulting integer into a string representation.
  5. Highlight catastrophic limitation: in languages with fixed-width integers, inputs exceeding 18 digits cause immediate integer overflow.

Naive String-to-Integer Parsing & Direct Addition Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [4, 5, 6]
Current operationSTEP 1 OF 6
Observation: Scanning num1 = "456" from left to right
Visual state
Values and pointers at this exact step
array
S
4
5
6
0
↑ i=0 ('4')
1
2
Variables at this step
String
num1
Char
'4'
Index i
0
Partial val1
4
Status
PARSING
Check / comparison
val1 = 0 * 10 + 4 = 4
Decision / next transition
Parse leading digit '4'. Initial accumulated integer val1 is 4.
Why this step matters

Observation: Scanning num1 = "456" from left to right. Parse character '4' at index 0.

Decision: Convert char code ('4' - '0') = 4. Accumulator val1 = 0 * 10 + 4 = 4.

Invariant: Partial integer value of prefix "4" is 4.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5// Fallback BigInt simulation for standard C++
6class Solution {
7public:
8 std::string addStrings(std::string num1, std::string num2) {
9 std::string res = "";
10 int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
11 while (i >= 0 || j >= 0 || carry) {
12 int sum = carry;
13 if (i >= 0) sum += num1[i--] - '0';
14 if (j >= 0) sum += num2[j--] - '0';
15 res.push_back((sum % 10) + '0');
16 carry = sum / 10;
17 }
18 std::reverse(res.begin(), res.end());
19 return res;
20 }
21};
22
23int main() {
24 Solution sol;
25 std::cout << sol.addStrings("11", "123") << std::endl; // "134"
26 std::cout << sol.addStrings("456", "77") << std::endl; // "533"
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N + M) — Scanning each character of num1 and num2 takes O(N + M) time.
  • Space complexity: O(1) — Direct integer conversion operates with O(1) auxiliary space.

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. Determine maximum length L = Math.max(num1.length, num2.length).
  2. Pad shorter string with leading 0 characters until its length equals L.
  3. Iterate backwards from k = L - 1 down to 0, adding (num1[k] - '0') + (num2[k] - '0') + carry.
  4. Append sum % 10 to result buffer and update carry = Math.floor(sum / 10).
  5. If carry remains after loop, prepend 1.
  6. Reverse buffer and return. Note trade-off: allocating the padded string wastes O(max(N, M)) memory.

Zero-Padded String Equalization & Synchronous Scan

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [4, 5, 6]
Current operationSTEP 1 OF 6
Observation: Pre-pad num2 with leading '0' to equalize string lengths to $L=3$: num1 = "456", num2 = "077"
Visual state
Values and pointers at this exact step
array
S
4
5
6
0
1
2
Variables at this step
Index k
2
Padded num2
"077"
Carry
1
Appended
3
Buffer
['3']
Check / comparison
6 + 7 + carry(0) = 13. Digit = 3, Carry = 1.
Decision / next transition
Pre-pad num2 with leading zero so both lengths = 3. Compute column k=2.
Why this step matters

Observation: Pre-pad num2 with leading '0' to equalize string lengths to L=3: num1 = "456", num2 = "077". Both can now be scanned synchronously using a single index k = L - 1 = 2.

Decision: Units column k=2: num1[2]='6', num2[2]='7'. sum = 6 + 7 + 0 = 13. Append '3', carry = 1.

Invariant: Lengths aligned; units column finalized.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5class Solution {
6public:
7 std::string addStrings(std::string num1, std::string num2) {
8 int len1 = num1.size(), len2 = num2.size();
9 int maxLen = std::max(len1, len2);
10
11 if (len1 < maxLen) num1 = std::string(maxLen - len1, '0') + num1;
12 if (len2 < maxLen) num2 = std::string(maxLen - len2, '0') + num2;
13
14 std::string res = "";
15 int carry = 0;
16
17 for (int i = maxLen - 1; i >= 0; --i) {
18 int sum = (num1[i] - '0') + (num2[i] - '0') + carry;
19 res.push_back((sum % 10) + '0');
20 carry = sum / 10;
21 }
22
23 if (carry) res.push_back(carry + '0');
24 std::reverse(res.begin(), res.end());
25 return res;
26 }
27};
28
29int main() {
30 Solution sol;
31 std::cout << sol.addStrings("11", "123") << std::endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(max(N, M)) — Pre-padding takes O(max(N, M)) and single backwards loop takes O(max(N, M)).
  • Space complexity: O(max(N, M)) — Pre-allocates a padded string copy of the shorter input, taking O(max(N, M)) auxiliary space.

3. Optimal Approach

Algorithm

  1. Initialize p1 = num1.length - 1, p2 = num2.length - 1, and carry = 0.
  2. Iterate while p1 >= 0 || p2 >= 0 || carry > 0.
  3. Extract d1 = p1 >= 0 ? num1[p1] - '0' : 0 and d2 = p2 >= 0 ? num2[p2] - '0' : 0.
  4. Compute sum = d1 + d2 + carry. Append sum % 10 to buffer, update carry = Math.floor(sum / 10).
  5. Decrement p1 and p2.
  6. Reverse the buffer and return joined string.

Two Pointers Right-to-Left Carry Accumulator (Optimal)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [4, 5, 6]
Current operationSTEP 1 OF 6
Observation: Pointers start at units column: num1[2]='6' and num2[1]='7', carry=0
Visual state
Values and pointers at this exact step
array
S
4
5
6
0
1
2
Variables at this step
p1 (num1)
2 ('6')
p2 (num2)
1 ('7')
Carry
0
Sum
13
Digit
3
Buffer
['3']
Check / comparison
d1 (6) + d2 (7) + carry (0) = 13. Digit = 13 % 10 = 3, Carry = 1.
Decision / next transition
Append 3 to digit buffer. Carry becomes 1.
Why this step matters

Observation: Pointers start at units column: num1[2]='6' and num2[1]='7', carry=0.

Decision: Compute sum = 6 + 7 + 0 = 13. Append digit 13 % 10 = 3 and update carry = Math.floor(13 / 10) = 1.

Invariant: Units position finalized to 3; carry 1 propagates to tens.

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

Time & Space Complexity

  • Time complexity: O(max(N, M)) — Single linear pass over both strings backwards. Max iterations = max(N, M) + 1.
  • Space complexity: O(max(N, M)) — O(1) auxiliary space beyond the output string buffer.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Built-In BigInt / BigInteger Radix AdditionO(N + M)O(N + M)Use arbitrary precision BigInt primitives to add the numbers (note: restricted by interview constraints, but valid for benchmarking).Time / space complexity limits.
2.Zero-Padded Align and Column AdditionO(max(N, M))O(max(N, M))Pad the shorter string with leading zeros so both strings have equal length, then iterate column-by-column from right to left.Time / space complexity limits.
3.Two Pointers Right-to-Left Carry AccumulatorOptimalO(max(N, M))O(1) auxiliarySimulate manual columnar addition using two pointers starting from the rightmost digits, accumulating digits into a single output buffer in O(1) auxiliary space.Time / space complexity limits.

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using built-in integer parsing (parseInt, Integer.parseInt), which causes Integer Overflow when input length exceeds 19 digits.

Pitfall 2:

Forgetting to subtract ASCII '0' (48) when reading character digits.

Pitfall 3:

Omitting the carry condition in the while loop header (while (i >= 0 || j >= 0 || carry)).

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 Strings?

Back to DSA Sheet