How do you approach Add Two Numbers?

Iterate through both arrays simultaneously, keeping track of the carry.

What is the time complexity of Add Two Numbers?

Time complexity: O(max(m, n)) where m and n are the lengths of the two arrays. Space complexity: O(max(m, n)) for the result array.

What are common mistakes on Add Two Numbers?

Reassigning next before saving it, which loses the rest of the list. Skipping the dummy head, which forces a special case every time the real head changes. Advancing the fast pointer without checking both fast and fast.next - the null dereference only shows up on even-length lists.

gitGood.dev

← Back to problems

Add Two Numbers

MediumAlgorithms

Description

You are given two non-empty arrays representing two non-negative integers. The digits are stored in reverse order, and each element contains a single digit.

Add the two numbers and return the sum as an array, also in reverse order.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1

Input: l1 = [2,4,3], l2 = [5,6,4]

Output: [7,0,8]

Explanation: 342 + 465 = 807, reversed is [7,0,8].

Example 2

Input: l1 = [0], l2 = [0]

Output: [0]

Example 3

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

Output: [8,9,9,9,0,0,0,1]

Explanation: 9999999 + 9999 = 10009998, reversed is [8,9,9,9,0,0,0,1].

Constraints

- 1 <= l1.length, l2.length <= 100 - 0 <= l1[i], l2[i] <= 9 - The numbers represented by the arrays do not have leading zeroes (except the number 0).

Add Two Numbers: approach, complexity and pitfalls

A medium linked list problem, graded against 6 test cases (3 of them hidden).

The pattern: Linked List

Pointer manipulation - reversal, cycle detection, and merging without extra space.

Reach for it when you see: Any problem handing you a list head, especially with an O(1) space constraint.

If you are stuck

Show the 3-step hint ladder

Iterate through both arrays simultaneously, keeping track of the carry.
What happens when one array is longer than the other?
Don't forget to handle the final carry after processing all digits.

The optimal approach

Show the approach: Elementary Math with Carry

Iterate through both arrays digit by digit, adding corresponding digits along with any carry from the previous addition. If one array is shorter, treat missing digits as 0.

Time: O(max(m, n)) where m and n are the lengths of the two arrays
Space: O(max(m, n)) for the result array

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Linked List mistakes

These apply to the pattern as a whole, not just this problem.

Reassigning `next` before saving it, which loses the rest of the list.
Skipping the dummy head, which forces a special case every time the real head changes.
Advancing the fast pointer without checking both `fast` and `fast.next` - the null dereference only shows up on even-length lists.