Add two big integers from digit lists
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two non-empty singly linked lists (or arrays) representing two non-negative integers. The digits are stored in **reverse order**, and each node contains a single digit from 0 to 9.
Your task is to add the two numbers and return the sum as a new linked list, also in reverse order.
You may assume:
- Each list has at least one node.
- The integers do not contain leading zeros, except the number 0 itself.
### Example
Input:
- List 1: 2 → 4 → 3 (represents the integer 342)
- List 2: 5 → 6 → 4 (represents the integer 465)
Output:
- 7 → 0 → 8 (represents the integer 807, since 342 + 465 = 807)
### Another example
Input:
- List 1: 9 → 9 → 9 (represents 999)
- List 2: 1 (represents 1)
Output:
- 0 → 0 → 0 → 1 (represents 1000)
### Constraints
- Let n be the length of the first list and m be the length of the second list.
- 1 ≤ n, m ≤ 10^5.
- Each node value is an integer in the range [0, 9].
**Task:** Describe an algorithm to perform this addition and construct the resulting linked list in O(n + m) time and O(1) additional space (excluding the space for the output list).
Quick Answer: This question evaluates algorithmic skills in manipulating linked lists or arrays to perform addition of large integers, focusing on carry propagation, handling differing lengths, and analysis of time and space complexity.
You are given two non-empty arrays of digits representing two non-negative integers. The digits are stored in **reverse order** (least significant digit first), and each element is a single digit from 0 to 9.
Add the two numbers and return the sum as a new array of digits, also in reverse order.
**Assumptions**
- Each array has at least one element.
- The integers do not contain leading zeros, except the number 0 itself.
**Example 1**
```
Input: l1 = [2, 4, 3], l2 = [5, 6, 4] (342 + 465)
Output: [7, 0, 8] (807)
```
**Example 2**
```
Input: l1 = [9, 9, 9], l2 = [1] (999 + 1)
Output: [0, 0, 0, 1] (1000)
```
Implement `add_two_numbers(l1, l2)` (camelCase `addTwoNumbers` in Java/C++/JS) returning the digit array of the sum in reverse order. Aim for O(n + m) time and O(1) extra space beyond the output.
Constraints
- 1 <= n, m <= 10^5 where n = len(l1), m = len(l2)
- Each element is an integer in the range [0, 9]
- Digits are stored in reverse order (least significant digit first)
- No leading zeros except for the number 0 itself
Examples
Input: ([2, 4, 3], [5, 6, 4])
Expected Output: [7, 0, 8]
Explanation: 342 + 465 = 807, stored reversed as [7, 0, 8].
Input: ([9, 9, 9], [1])
Expected Output: [0, 0, 0, 1]
Explanation: 999 + 1 = 1000; carry propagates through all three digits and creates a new leading digit.
Input: ([0], [0])
Expected Output: [0]
Explanation: 0 + 0 = 0.
Input: ([0], [5, 6, 4])
Expected Output: [5, 6, 4]
Explanation: 0 + 465 = 465; differing lengths, no carry.
Input: ([9, 9, 9, 9], [9, 9, 9])
Expected Output: [8, 9, 9, 0, 1]
Explanation: 9999 + 999 = 10998, reversed [8, 9, 9, 0, 1].
Input: ([5], [5])
Expected Output: [0, 1]
Explanation: 5 + 5 = 10; single-digit inputs producing a carry into a new digit.
Hints
- Walk both arrays from index 0 (the least significant digit) toward the end, just like grade-school column addition.
- Maintain a single carry variable. At each position, sum the available digits plus the carry; append (sum % 10) and set carry = sum // 10.
- When one array runs out, keep going with just the carry and the remaining longer array. Don't forget a final carry can add one extra digit (e.g. 999 + 1 -> [0,0,0,1]).