Watch 10 video solutions for Add Strings, a easy level problem involving Math, String, Simulation. This walkthrough by Ashish Pratap Singh has 1,002,125 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.
Example 1:
Input: num1 = "11", num2 = "123" Output: "134"
Example 2:
Input: num1 = "456", num2 = "77" Output: "533"
Example 3:
Input: num1 = "0", num2 = "0" Output: "0"
Constraints:
1 <= num1.length, num2.length <= 104num1 and num2 consist of only digits.num1 and num2 don't have any leading zeros except for the zero itself.Problem Overview: You are given two non‑negative integers stored as strings. The task is to return their sum, also as a string, without converting the entire string into an integer. The challenge is handling digit addition and carry manually, similar to how you add numbers on paper.
Approach 1: Reverse and Traverse (O(n) time, O(n) space)
This method reverses both strings so the least significant digits appear first. After reversing, iterate from index 0 while adding corresponding digits and maintaining a carry. Each step computes digitSum = d1 + d2 + carry, appends digitSum % 10 to the result, and updates carry = digitSum / 10. Continue until both strings are fully processed and the carry is handled. The result string is reversed again to restore correct order. Time complexity is O(n) because every digit is processed once, and space complexity is O(n) due to storing reversed strings and the output.
This approach is straightforward and mirrors manual addition closely. Reversing the strings simplifies index handling because digits align naturally from least significant to most significant.
Approach 2: Character by Character Addition Using Two Pointers (O(n) time, O(1) extra space)
This approach avoids reversing strings by using two pointers starting from the end of each string. Pointer i begins at num1.length() - 1 and pointer j at num2.length() - 1. At each step, convert characters to digits, compute their sum with the current carry, and append the resulting digit. Decrement pointers and repeat until both pointers are exhausted and no carry remains.
The digits are generated from least significant to most significant, so the result is typically built using a dynamic buffer and reversed once at the end. Time complexity remains O(n), where n is the maximum length of the two strings. Extra space is O(1) excluding the output string. This method is commonly preferred because it avoids modifying the input and keeps memory overhead minimal.
The problem mainly tests understanding of string manipulation, elementary math operations, and iterative simulation of digit-by-digit addition.
Recommended for interviews: The two‑pointer approach is the expected solution. Interviewers want to see that you can simulate addition from right to left while managing carry efficiently. The reverse‑and‑traverse method still demonstrates correct reasoning, but the pointer approach shows stronger control over string traversal and space optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse and Traverse | O(n) | O(n) | When simplicity matters and reversing strings is acceptable |
| Two Pointers from End | O(n) | O(1) extra | Best general solution; avoids reversing and minimizes memory usage |