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.
This approach involves reversing both input strings, then iterating through them to sum up each digit, similar to manual addition from the rightmost digit. This technique simplifies handling the carry over during addition.
The function addStrings adds two numbers represented as strings without converting them directly into integers. It accomplishes this by iterating over the digits in reverse, calculating the sum, and storing this in a result string. We keep the process efficient by using a simple loop to handle differing lengths of input strings, adding the carry and reversing the string at the end to present the final sum.
Time Complexity: O(n), where n is the maximum length of num1 or num2.
Space Complexity: O(n), for the result array.
This approach deploys two pointers, initially positioned at the end of each input string. We process each character one by one, moving the pointers from the rightmost end towards the start of each string. This allows us to readily manage the carry as we compute the sum step-by-step.
This C implementation utilizes dynamic memory allocation to handle the expected length of the result string. By manipulating pointers, the implementation skillfully confines carry operations within the loop. The function returns a pointer to the correct start of the result string after adjusting for any leading zeros produced by initial carry operations.
Time Complexity: O(n), where n is the maximum length of num1 or num2.
Space Complexity: O(n), necessary for the dynamically allocated result string.
We use two pointers i and j to point to the end of the two strings respectively, and start adding bit by bit from the end. Each time we take out the corresponding digits a and b, calculate their sum a + b + c, where c represents the carry from the last addition. Finally, we append the units digit of a + b + c to the end of the answer string, and then take the tens digit of a + b + c as the value of the carry c, and loop this process until the pointers of both strings have pointed to the beginning of the string and the value of the carry c is 0.
Finally, reverse the answer string and return it.
The time complexity is O(max(m, n)), where m and n are the lengths of the two strings respectively. Ignoring the space consumption of the answer string, the space complexity is O(1).
The following code also implements string subtraction, refer to the subStrings(num1, num2) function.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Kotlin
| Approach | Complexity |
|---|---|
| Reverse and Traverse | Time Complexity: |
| Character by Character Addition Using Two Pointers | Time Complexity: |
| Two Pointers | — |
| 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 |
Add Strings | Leetcode 415 Solution in Hindi • Pepcoding • 14,125 views views
Watch 9 more video solutions →Practice Add Strings with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor