DEV Community

loading...

How I Solved: Add Two Numbers (LeetCode #2)

imjoshellis profile image Josh Ellis ・3 min read

πŸ›‘οΈ This won't make any sense unless you're familiar with the problem explanation on LeetCode: https://leetcode.com/problems/add-two-numbers/

Simple Case

Let's start with the assumption that we're adding two non-null single-digit nodes.

In that case, we would start by adding the two values together:

const addTwoNumbers = (
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null => {
  const sum = l1.val + l2.val
}
Enter fullscreen mode Exit fullscreen mode

Next, we need to split the sum into a remainder and carry if it's greater than 10:

const rem = sum % 10
const carry = sum > 9 ? 1 : 0
Enter fullscreen mode Exit fullscreen mode

Finally, we'd return a new ListNode pointing at the carry if it exists:

const carryNode = carry > 0 ? new ListNode(carry) : null
return new ListNode(rem, carryNode)
Enter fullscreen mode Exit fullscreen mode

So far, what we have is this, which will work great if l1 and l2 are exactly one digit:

const addTwoNumbers = (
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null => {
  const sum = l1.val + l2.val
  const rem = sum % 10
  const carry = sum > 9 ? 1 : 0
  const carryNode = carry > 0 ? new ListNode(carry) : null
  return new ListNode(rem, carryNode)
}
Enter fullscreen mode Exit fullscreen mode

Recursion

Now we need to think about how to handle carrying a little better. What we need is a generic function that traverses down the list. Let's use recursion.

When the function returns, we want to move on to process the next nodes in each list.

Let's start by adding carry to the list of arguments, defaulting to 0. This way, we can pass the carry along with the recursive call:

const addTwoNumbers = (
  l1: ListNode | null,
  l2: ListNode | null,
  carry: number = 0
): ListNode | null => {
  // ...
Enter fullscreen mode Exit fullscreen mode

We can do that by calling addTwoNumbers with l1.next, l2.next, and carry in the next part of the ListNode constructor:

return new ListNode(rem, addTwoNumbers(l1?.next, l2?.next, carry))
Enter fullscreen mode Exit fullscreen mode

This will work if we also make sure to handle the null cases.

If both l1 and l2 are empty, we check the value of carry. If carry is 0, we are done and can return null. Otherwise, we're still done, but we need to return a node containing carry:

if (!l1 && !l2) return carry > 0 ? new ListNode(carry) : null
Enter fullscreen mode Exit fullscreen mode

With that base case in place, this code will be accepted by LeetCode, but there's one obvious optimization to be added still:

const addTwoNumbers = (
  l1: ListNode | null,
  l2: ListNode | null,
  carry: number = 0
): ListNode | null => {
  if (!l1 && !l2) return carry > 0 ? new ListNode(carry) : null
  const l1val = l1?.val || 0
  const l2val = l2?.val || 0
  const sum = l1val + l2val + carry
  const rem = sum % 10
  carry = sum > 9 ? 1 : 0
  return new ListNode(rem, addTwoNumbers(l1?.next, l2?.next, carry))
}
Enter fullscreen mode Exit fullscreen mode

Optimization

What if one of the lists is significantly longer than the other? We would waste time traversing it! If a list is empty and carry is 0, we can simply return the other list:

if (!l1 && carry === 0) return l2
if (!l2 && carry === 0) return l1
Enter fullscreen mode Exit fullscreen mode

Final Solution

Here's the final solution. On a good run, it's faster than ~98% of other TypeScript submissions.

To further optimize, we'd have to switch to an iterative method using a loop instead of recursion.

const addTwoNumbers = (
  l1: ListNode | null,
  l2: ListNode | null,
  carry: number = 0
): ListNode | null => {
  if (!l1 && !l2) return carry > 0 ? new ListNode(carry) : null
  if (!l1 && carry === 0) return l2
  if (!l2 && carry === 0) return l1
  const l1val = l1?.val || 0
  const l2val = l2?.val || 0
  const sum = l1val + l2val + carry
  const rem = sum % 10
  carry = sum > 9 ? 1 : 0
  return new ListNode(rem, addTwoNumbers(l1?.next, l2?.next, carry))
}
Enter fullscreen mode Exit fullscreen mode

Discussion

pic
Editor guide