Leetcode Problem 2: Add Two Numbers

This exercise made me realise that Leetcode’s backend enforecs type checking at runtime. For those used to compiled languages, I just stated the bleeding obvious, but for Python people, this requires some serious adjusting, as Python does not natively type check. Specifically to this exercise, the input arrays needed to be of type ListNode and not vanilla list.

Input lists of type ListNode mean that we can’t use Python’s builtin lists, which are de facto dynamic arrays, and apply operations on the full set of elements. After all, the exercise asks for a LinkedList implementation. The way I made it work was to explicitly cast the input arrays l1 and l2 to ListNode.

Plain English breakdown of the algorithm:

  1. get current nodes and their value

  2. add the two nodes, while taking into account the carry

  3. if the sum of the current nodes is greater than 10,

    • set carry to 1
    • set current sum to current sum - 10

  4. if the sum of the current nodes is less than 10,

    • set carry to 0,
    • set current sum to value in step 2.

  5. recursively apply the above steps until we reach the end of the LinkedLists

Note 1 Link to heading

Step 3. is only possible because of the constraint:

  • 0 <= Node.val <= 9

So we know that the current sum is at most 19, and hence carry is either 0 or 1.

Note 2 Link to heading

I changed the signature of addTwoNumbers to accept the carry value from the previous stack, as I found recursion to be the most intuitive approach. Alternatively I could’ve used a for loop and set carry as a condition, and perhaps avoided recursion, but I didn’t find that approach intuitive.

Python solution Link to heading


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
        
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode, carry=0) -> ListNode:
        l1 = ListNode(l1)
        l2 = ListNode(l2)
        solution = ListNode()
            
        curr_node_1 = l1.val
        curr_node_2 = l2.val
        
        if curr_node_1 is not None:
            curr_val_1 = curr_node_1.val
        else:
            curr_val_1 = 0
            
        if curr_node_2 is not None:
            curr_val_2 = curr_node_2.val
        else:
            curr_val_2 = 0
            
        curr_sum = curr_val_1 + curr_val_2 + carry
        if curr_sum >= 10:
            curr_sum = curr_sum - 10
            carry = 1
        else:
            carry = 0
        
        solution.val += curr_sum 
        
        # case 1: same size input lists and both next elements are not None -> reset heads and recurse
        # addTwoNumbers
        if curr_node_1.next is not None and curr_node_2.next is not None:
            curr_node_1 = curr_node_1.next
            curr_node_2 = curr_node_2.next    
            solution.next = self.addTwoNumbers(curr_node_1, curr_node_2, carry)
            
        # case 2: same size input lists and both next elems are None -> return final node
        elif curr_node_1.next is None and curr_node_2.next is None:
            if carry == 1:
                return ListNode(solution.val, next=ListNode(carry))
        
        else:
            # case 3: input lists are of different sizes -> identify longer/smaller list
            #         either of the lists can have next elem as None
            if curr_node_1.next is None and curr_node_2.next is not None:
                curr_node_1 = ListNode() 
                curr_node_2 = curr_node_2.next
            else:
                curr_node_1 = curr_node_1.next 
                curr_node_2 = ListNode()
            
            solution.next = self.addTwoNumbers(curr_node_1, curr_node_2, carry)
                        
        return solution

C++ solution Link to heading


class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2, int carry=0) {
        ListNode *solution = new ListNode();
        ListNode *curr_1 = l1;
        ListNode *curr_2 = l2;
        int curr_1_val = 0, curr_2_val = 0;

        if(curr_1 != nullptr) {
            curr_1_val = curr_1->val;
        }

        if(curr_2 != nullptr) {
            curr_2_val = curr_2->val;
        }

        int curr_sum = curr_1_val + curr_2_val + carry;
        if (curr_sum >= 10) {
            curr_sum = curr_sum - 10;
            carry = 1;
        }
        else {
            carry = 0;
        }

        solution->val += curr_sum;

        if(curr_1->next != nullptr and curr_2->next != nullptr) {
            curr_1 = curr_1->next;
            curr_2 = curr_2->next;
            solution->next = this->addTwoNumbers(curr_1, curr_2, carry);
        }
        else if (curr_1->next == nullptr and curr_2->next == nullptr) {
            if (carry == 1) {
                return new ListNode(solution->val, new ListNode(carry));
            }
        }
        else {
            if (curr_1->next == nullptr and curr_2->next != nullptr) {
                curr_1 = new ListNode();
                curr_2 = curr_2->next;
            }
            else {
                curr_1 = curr_1->next;
                curr_2 = new ListNode();
            }

            solution->next = this->addTwoNumbers(curr_1, curr_2, carry);
        }

        return solution;
    }
};

Python statistics Link to heading

Runtime: 72 ms         -> faster than 48.20% of Python 3 submissions 
Memory Usage: 14.4 MB  -> beats  43.64% of Python 3 submissions

C++ statistics Link to heading

Runtime: 32 ms         -> faster than 42.83% of C++ online submissions 
Memory Usage: 72.2 MB  -> less than 5.45% of C++ online submissions

Complexity analysis Link to heading

  • Time complexity: O(max(m, n)), where m and n are the lengths of the lists. That is because we call addTwoNumbers at most m or n times in order to traverse the lists and reach the base.

  • Space complexity: O(max(m, n)), because it depends on the length of the solution Node, which in turn depends on whichever is greater between m or n.



Share on:
LinkedIn