Add Strings

Easy

#0402Time: `O(max(N, M)^2)`, where `N` and `M` are the lengths of `num1` and `num2`. Prepending a character to a string of length `k` takes `O(k)` time. Since this is done in a loop `max(N, M)` times, the total time complexity becomes quadratic.Space: `O(max(N, M)^2)`. In each iteration, a new string is created for the result. The sum of the lengths of all these intermediate strings is `1 + 2 + ... + max(N, M)`, which results in quadratic space complexity.5 companies

Patterns

Math

Data structures

String

Companies

Airbnb Avito Capital One Wayfair

Prompt

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 <= 10⁴
num1 and num2 consist of only digits.
num1 and num2 don't have any leading zeros except for the zero itself.

Approaches

2 approaches with complexity analysis and trade-offs.

This method mimics the way humans add numbers on paper, starting from the least significant digit (the rightmost one). It iteratively calculates the sum of digits at each position, manages a carry-over, and builds the result string. However, it uses an inefficient way to build the string by prepending digits, which degrades performance significantly.

Algorithm

Initialize result = "", i = num1.length() - 1, j = num2.length() - 1, carry = 0.
Loop while i >= 0 or j >= 0 or carry > 0.
Extract digit1 from num1 at i (or 0 if i < 0).
Extract digit2 from num2 at j (or 0 if j < 0).
Calculate sum = digit1 + digit2 + carry.
Update carry = sum / 10.
Prepend sum % 10 to the result string.
Decrement i and j.
Return result.

Walkthrough

The algorithm proceeds as follows:

Initialize two pointers, i and j, to point to the last character of num1 and num2, respectively.
Initialize a carry variable to 0.
Initialize an empty string, result, to store the sum.
Loop as long as i or j are valid indices, or if there is a carry left over.
Inside the loop:
- Get the integer value of the digit from num1 at index i. If i is out of bounds, use 0.
- Get the integer value of the digit from num2 at index j. If j is out of bounds, use 0.
- Calculate the currentSum = digit1 + digit2 + carry.
- The new carry for the next iteration is currentSum / 10.
- The digit for the current position is currentSum % 10.
- Prepend this digit to the result string. In Java, result = (currentSum % 10) + result;. This is an O(L) operation where L is the current length of result, as strings are immutable.
- Decrement i and j to move to the next digits to the left.
After the loop, result holds the final sum. A special case is if both input strings are "0", the result should be "0". The algorithm handles this correctly.

1class Solution {2    public String addStrings(String num1, String num2) {3        String result = "";4        int i = num1.length() - 1;5        int j = num2.length() - 1;6        int carry = 0;7 8        while (i >= 0 || j >= 0 || carry > 0) {9            int digit1 = (i >= 0) ? num1.charAt(i) - '0' : 0;10            int digit2 = (j >= 0) ? num2.charAt(j) - '0' : 0;11 12            int sum = digit1 + digit2 + carry;13            carry = sum / 10;14            int currentDigit = sum % 10;15 16            // Inefficient string concatenation17            result = currentDigit + result;18 19            i--;20            j--;21        }22 23        return result;24    }25}

Complexity

Time

`O(max(N, M)^2)`, where `N` and `M` are the lengths of `num1` and `num2`. Prepending a character to a string of length `k` takes `O(k)` time. Since this is done in a loop `max(N, M)` times, the total time complexity becomes quadratic.

Space

`O(max(N, M)^2)`. In each iteration, a new string is created for the result. The sum of the lengths of all these intermediate strings is `1 + 2 + ... + max(N, M)`, which results in quadratic space complexity.

Trade-offs

Pros

The logic is very straightforward and easy to understand as it directly simulates manual addition.

Cons

Extremely inefficient for long input strings due to quadratic time and space complexity from repeated string concatenations.
Will likely result in a "Time Limit Exceeded" or "Memory Limit Exceeded" error on platforms with strict constraints.

This approach also simulates manual, right-to-left addition but uses a StringBuilder for efficient string construction. By appending digits to a StringBuilder and reversing it once at the end, we avoid the costly re-creation of strings in a loop.

Algorithm

Initialize StringBuilder result, i = num1.length() - 1, j = num2.length() - 1, carry = 0.
Loop while i >= 0 or j >= 0 or carry > 0.
Extract digit1 from num1 at i (or 0 if i < 0) and decrement i.
Extract digit2 from num2 at j (or 0 if j < 0) and decrement j.
Calculate sum = digit1 + digit2 + carry.
Append sum % 10 to the result StringBuilder.
Update carry = sum / 10.
After the loop, reverse the result StringBuilder.
Return the string representation of the reversed result.

Walkthrough

This method is an optimized version of the previous one. The core idea of simulating grade-school addition remains the same.

Initialize a StringBuilder to build the result string.
Initialize pointers i and j to the last characters of num1 and num2.
Initialize carry to 0.
Loop as long as there are digits in either num1 or num2 to process, or if a carry exists.
Inside the loop:
- Get the integer values of the digits from num1 and num2 at the current pointers. If a pointer is out of bounds, its corresponding digit is 0.
- Calculate sum = digit1 + digit2 + carry.
- The digit for the current position is sum % 10. Append this to the StringBuilder. Appending to a StringBuilder is an amortized O(1) operation.
- The new carry for the next position is sum / 10.
- Decrement the pointers i and j.
After the loop, the StringBuilder contains the digits of the sum, but in reverse order (from least significant to most significant).
Reverse the StringBuilder and convert it to a string to get the final correct result.

1class Solution {2    public String addStrings(String num1, String num2) {3        StringBuilder result = new StringBuilder();4        int i = num1.length() - 1;5        int j = num2.length() - 1;6        int carry = 0;7 8        while (i >= 0 || j >= 0 || carry > 0) {9            int digit1 = (i >= 0) ? num1.charAt(i--) - '0' : 0;10            int digit2 = (j >= 0) ? num2.charAt(j--) - '0' : 0;11 12            int sum = digit1 + digit2 + carry;13            carry = sum / 10;14            result.append(sum % 10);15        }16 17        return result.reverse().toString();18    }19}

Complexity

Time

`O(max(N, M))`, where `N` and `M` are the lengths of `num1` and `num2`. The algorithm iterates through the digits of the strings once. Appending to a `StringBuilder` is amortized `O(1)`, and the final reversal takes `O(max(N, M))` time.

Space

`O(max(N, M))`. The `StringBuilder` used to store the result will have a length of at most `max(N, M) + 1`.

Trade-offs

Pros

Optimal time and space complexity for this problem.
Efficiently handles very large numbers within the given constraints.
The logic is still relatively simple and follows the natural process of addition.

Cons

Requires an extra step to reverse the string at the end, which adds a small constant factor overhead but doesn't change the overall complexity.

Solutions

Solution

1class Solution {2public3  String addStrings(String num1, String num2) {4    int i = num1.length() - 1, j = num2.length() - 1;5    StringBuilder ans = new StringBuilder();6    for (int c = 0; i >= 0 || j >= 0 || c > 0; --i, --j) {7      int a = i < 0 ? 0 : num1.charAt(i) - '0';8      int b = j < 0 ? 0 : num2.charAt(j) - '0';9      c += a + b;10      ans.append(c % 10);11      c /= 10;12    }13    return ans.reverse().toString();14  }15public16  String subStrings(String num1, String num2) {17    int m = num1.length(), n = num2.length();18    boolean neg = m < n || (m == n && num1.compareTo(num2) < 0);19    if (neg) {20      String t = num1;21      num1 = num2;22      num2 = t;23    }24    int i = num1.length() - 1, j = num2.length() - 1;25    StringBuilder ans = new StringBuilder();26    for (int c = 0; i >= 0; --i, --j) {27      c = (num1.charAt(i) - '0') - c - (j < 0 ? 0 : num2.charAt(j) - '0');28      ans.append((c + 10) % 10);29      c = c < 0 ? 1 : 0;30    }31    while (ans.length() > 1 && ans.charAt(ans.length() - 1) == '0') {32      ans.deleteCharAt(ans.length() - 1);33    }34    if (neg) {35      ans.append('-');36    }37    return ans.reverse().toString();38  }39}

1/** * @param {string} num1 * @param {string} num2 * @return {string} */ var addStrings =2  function (num1, num2) {3    let i = num1.length - 1;4    let j = num2.length - 1;5    const ans = [];6    for (let c = 0; i >= 0 || j >= 0 || c; --i, --j) {7      c += i < 0 ? 0 : +num1[i];8      c += j < 0 ? 0 : +num2[j];9      ans.push(c % 10);10      c = Math.floor(c / 10);11    }12    return ans.reverse().join("");13  };14/** * @param {string} num1 * @param {string} num2 * @return {string} */ var subStrings =15  function (num1, num2) {16    const m = num1.length;17    const n = num2.length;18    const neg = m < n || (m == n && num1 < num2);19    if (neg) {20      const t = num1;21      num1 = num2;22      num2 = t;23    }24    let i = num1.length - 1;25    let j = num2.length - 1;26    const ans = [];27    for (let c = 0; i >= 0; --i, --j) {28      c = +num1[i] - c;29      if (j >= 0) {30        c -= +num2[j];31      }32      ans.push((c + 10) % 10);33      c = c < 0 ? 1 : 0;34    }35    while (ans.length > 1 && ans.at(-1) === 0) {36      ans.pop();37    }38    return (neg ? " - " : "") + ans.reverse().join("");39  };

1class Solution {2public:3  string addStrings(string num1, string num2) {4    int i = num1.size() - 1, j = num2.size() - 1;5    string ans;6    for (int c = 0; i >= 0 || j >= 0 || c; --i, --j) {7      int a = i < 0 ? 0 : num1[i] - '0';8      int b = j < 0 ? 0 : num2[j] - '0';9      c += a + b;10      ans += to_string(c % 10);11      c /= 10;12    }13    reverse(ans.begin(), ans.end());14    return ans;15  }16  string subStrings(string num1, string num2) {17    int m = num1.size(), n = num2.size();18    bool neg = m < n || (m == n && num1 < num2);19    if (neg) {20      swap(num1, num2);21    }22    int i = num1.size() - 1, j = num2.size() - 1;23    string ans;24    for (int c = 0; i >= 0; --i, --j) {25      c = (num1[i] - '0') - c - (j < 0 ? 0 : num2[j] - '0');26      ans += to_string((c + 10) % 10);27      c = c < 0 ? 1 : 0;28    }29    while (ans.size() > 1 && ans.back() == '0') {30      ans.pop_back();31    }32    if (neg) {33      ans.push_back('-');34    }35    reverse(ans.begin(), ans.end());36    return ans;37  }38};

1class Solution:2    def addStrings(self, num1: str, num2: str) -> str: i, j = len(num1) - 1, len(num2) - 1 ans = [] c = 0 while i >= 0 or j >= 0 or c: a = 0 if i < 0 else int(num1[i]) b = 0 if j < 0 else int(num2[j]) c, v = divmod(a + b + c, 10)  # nice ans . append ( str ( v )) i , j = i - 1 , j - 1 return "" . join ( ans [:: - 1 ]) # follow-up, substract def subStrings ( self , num1 : str , num2 : str ) -> str : m , n = len ( num1 ), len ( num2 ) neg = m < n or ( m == n and num1 < num2 ) if neg : num1 , num2 = num2 , num1 i , j = len ( num1 ) - 1 , len ( num2 ) - 1 ans = [] c = 0 while i >= 0 : c = int ( num1 [ i ]) - c - ( 0 if j < 0 else int ( num2 [ j ])) ans . append ( str (( c + 10 ) % 10 )) c = 1 if c < 0 else 0 i , j = i - 1 , j - 1 # eg. 99199 - 99198 = 1, ans here is "10000" while len ( ans ) > 1 and ans [ - 1 ] == "0" : ans . pop () if neg : # will not be "-0", neg only when <0 ans . append ( "-" ) return "" . join ( ans [:: - 1 ]) ############ class Solution : def addStrings ( self , num1 : str , num2 : str ) -> str : i , j = len ( num1 ) - 1 , len ( num2 ) - 1 ans = [] c = 0 while i >= 0 or j >= 0 or c : a = 0 if i < 0 else int ( num1 [ i ]) b = 0 if j < 0 else int ( num2 [ j ]) c , v = divmod ( a + b + c , 10 ) ans . append ( str ( v )) i , j = i - 1 , j - 1 return "" . join ( ans [:: - 1 ]) def subStrings ( self , num1 : str , num2 : str ) -> str : m , n = len ( num1 ), len ( num2 ) neg = m < n or ( m == n and num1 < num2 ) if neg : num1 , num2 = num2 , num1 i , j = len ( num1 ) - 1 , len ( num2 ) - 1 ans = [] c = 0 while i >= 0 : c = int ( num1 [ i ]) - c - ( 0 if j < 0 else int ( num2 [ j ])) ans . append ( str (( c + 10 ) % 10 )) c = 1 if c < 0 else 0 i , j = i - 1 , j - 1 while len ( ans ) > 1 and ans [ - 1 ] == "0" : ans . pop () if neg : ans . append ( "-" ) return "" . join ( ans [:: - 1 ])

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem