LeetCode Problem 2: Add Two Numbers Solution in Python

Interview Questions

Introduction

One of the most useful platforms when it comes to technical interview preparation is LeetCode that gives you access to thousands of problems of varying difficulty level.

In today’s guide we are going to walk through the solution of the second problem on the platform, called Add Two Numbers that involves Linked Lists and is of Medium difficulty level. This problem may appear in any technical interview for Engineering and ML positions.

Note that if you haven’t attempted to solve this problem yet, I strongly encourage you to give it a try before looking at the solution which is presented and thoroughly explain in the next few sections of the article.

The problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

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.

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]

Constraints:

The number of nodes in each linked list is in the range [1, 100].

0 <= Node.val <= 9

It is guaranteed that the list represents a number that does not have leading zeros.

Source: LeetCode

Solution Walk-Through

First, we need to ensure that we will be utilising all the information and details provided in the problem description. For this particular example these details are:

two non-empty linked lists
representing non-negative integers
digits are stored in reversed order

The first two points essentially narrow down the problem as it could be a little bit more tricky to deal with empty linked lists or linked lists representing negative and/or positive integers.

Now the last bit of information is also crucial and we can actually use it to our advantage. Since the numbers represented by the linked lists are in reversed order, this could actually help us work with the carry we need to forward when adding two digits together.

Now let’s get started with our algorithm that could eventually give a proper solution to the problem in question.

First, we need to initialise 3 variables. The first one will be holding the carry will be forwarding over at each step, the second one will be a Linked List that will represent the final result (initially set to value 0) and the third one will be our pointer that will be using in order to move towards the next node at every iteration.

carry = 0
result = ListNode(0)
pointer = result

At this point you may have to recall how shared references work in Python as any update in pointer will have an immediate effect on result as well as both of these variables are sharing the same object reference.

Now that we have initialised these variables we can start iterating over the linked lists. Essentially, we need to keep iterating until there are no more nodes in either of the lists and when we don’t carry over any additional unit. Therefore, a while loop with the conditions shown below should do the trick:

carry = 0
result = ListNode(0)
pointer = result

while (l1 or l2 or carry):

Then we need to retrieve the digits from the individual nodes. Since the linked lists could be of different size (or even reach the end of both lists but still carrying over a unit) we also need to handle the cases where the value of the node is None.

carry = 0
result = ListNode(0)
pointer = result

while (l1 or l2 or carry):

    first_num = l1.val if l1.val else 0
    second_num = l2.val if l2.val else 0

Then we need to perform the addition and see whether this will have any impact. To do so, we first add together the two numbers as well as the carry. Then we compute the next digit of the solution by taking the modulo between the sum and number 10 and then carry by performing a floor division between the sum and number 10 .

For instance, if the sum of the two digits is 12, num variable will be set to 2 (because 12 % 10 = 2) and carry will be 1 (since 12 // 10 = 1).

carry = 0
result = ListNode(0)
pointer = result

while (l1 or l2 or carry):

    first_num = l1.val if l1.val else 0
    second_num = l2.val if l2.val else 0


    summation = first_num + second_num + carry
    num = summation % 10
    carry = summation // 10

Finally, we store the result to the pointer (that will also update result since these two variables are sharing the reference to the same object) and the move the pointer to the next node (if any):

carry = 0
result = ListNode(0)
pointer = result

while (l1 or l2 or carry):

    first_num = l1.val if l1.val else 0
    second_num = l2.val if l2.val else 0

    summation = first_num + second_num + carry
    num = summation % 10
    carry = summation // 10

    pointer.next = ListNode(num)

    pointer = pointer.next
    l1 = l1.next if l1 else None
    l2 = l2.next if l2 else None

Finally, we return result.next since the initial node of the result was actually a 0 .

carry = 0
result = ListNode(0)
pointer = result

while (l1 or l2 or carry):

    first_num = l1.val if l1.val else 0
    second_num = l2.val if l2.val else 0

    summation = first_num + second_num + carry
    num = summation % 10
    carry = summation // 10

    pointer.next = ListNode(num)

    pointer = pointer.next
    l1 = l1.next if l1 else None
    l2 = l2.next if l2 else None

return result.next

Full Code for the Solution

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        carry = 0
        result = ListNode(0)
        pointer = result

        while (l1 or l2 or carry):

            first_num = l1.val if l1.val else 0
            second_num = l2.val if l2.val else 0

            summation = first_num + second_num + carry

            num = summation % 10
            carry = summation // 10

            pointer.next = ListNode(num)

            pointer = pointer.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return result.next

Time Complexity

One of the most important aspects in algorithm development that is also taken into account when evaluating solutions as part of technical interviews is time complexity.

Assuming that the length of l1 linked list is m and the length of l2 linked list is n then we are iterating at most m or n times depending on which of the two has more nodes. Therefore, the time complexity of the algorithm is O(max(m, n)).

Final Thoughts

In today’s article we discussed about one fairly challenging problem on LeetCode which is the second one called "Add Two Numbers" that involves one of the most fundamental data structures namely Linked Lists.

Note that there may be other solutions to this problem. Feel free to leave a comment with any potential improvements and I’d be more than happy to discuss your inputs!

Become a member and read every story on Medium. Your membership fee directly supports me and other writers you read. You’ll also get full access to every story on Medium.