Solving the ‘Add Two Numbers’ Problem on LeetCode — Scala Solutions Walkthrough

Image Source

Introduction

The ‘Add Two Numbers’ problem on LeetCode involves adding two non-empty linked lists representing two non-negative integers. Each list’s digits are stored in reverse order, and each node contains a single digit. The task is to add the two numbers and return the sum as a linked list.

Scala is a functional and object-oriented language well-suited for handling data structures and concurrent programming. In this article we will being doing a walkthrough of four Scala solutions to tackle the ‘Add Two Numbers’ problem. By the end of this guide, you will understand the mechanics behind each approach and their efficiency and effectiveness. Code comments and detailed step-by-step explanations for each method are after the conclusion.

Problem Description

/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 *   var x: Int = _x
 * }
 */

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.

Function Signature in Scala:

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {

    }
}

Example 1:

Image Source

• 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.

Solution 1: Iterative Approach with Carry Handling

This simple approach involves iterating through both linked lists, summing corresponding digits, and managing the carry for sums greater than 9.

Scala Code:

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
        val dummy = new ListNode(0)
        var current = dummy
        var carry = 0

        var p = l1
        var q = l2

        while (p != null || q != null) {
            val x = if (p != null) p.x else 0
            val y = if (q != null) q.x else 0
            val sum = carry + x + y
            carry = sum / 10
            current.next = new ListNode(sum % 10)
            current = current.next

            if (p != null) p = p.next
            if (q != null) q = q.next
        }

        if (carry > 0) {
            current.next = new ListNode(carry)
        }

        dummy.next
    }
}

Time and Space Complexity

• Time Complexity: O(n), the algorithm traverses both linked lists l1 and l2 exactly once. In each iteration, it processes one node from each list and performs a constant amount of work (addition, carry handling, and node creation). Therefore, the time complexity is linear relative to the length of the longer list.
• Space Complexity: O(n), the space complexity is determined by the space required to store the result linked list. Since a new node is created for each digit of the sum, the space complexity is proportional to the length of the resulting list, which is O(n). The auxiliary space used for variables such as carry, dummy, and current is constant (O(1)), but the new linked list accounts for the overall O(n) space complexity.

Solution 2: Recursive Approach

This approach uses recursion to handle the addition of digits and carry, simplifying the iterative logic by breaking it down into smaller recursive calls.

Scala Code:

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode, carry: Int = 0): ListNode = {
        if (l1 == null && l2 == null && carry == 0) return null

        val sum = (if (l1 != null) l1.x else 0) + (if (l2 != null) l2.x else 0) + carry
        val node = new ListNode(sum % 10)
        node.next = addTwoNumbers(if (l1 != null) l1.next else null, if (l2 != null) l2.next else null, sum / 10)
        node
    }
}

Time and Space Complexity

• Time Complexity: O(n), similar to the iterative approach, the recursive solution processes each node of the input lists once. Each recursive call handles one digit addition and proceeds to the next nodes of l1 and l2, making the time complexity linear in relation to the length of the longer list.
• Space Complexity: O(n), the space complexity includes both the space for the new linked list and the recursive call stack. Each recursive call consumes stack space, which leads to O(n) space complexity due to recursion depth being equal to the length of the longer list. Additionally, the new linked list created to store the result contributes to O(n) space complexity. Thus, the total space complexity is O(n) for both the call stack and the new linked list.

Solution 3: Functional Approach with Zipping and Folding

This approach leverages Scala’s functional programming features, such as zip and foldLeft, to process the linked lists in a more idiomatic way.

Scala Code:

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
        def toLazyList(node: ListNode): LazyList[Int] =
            if (node == null) LazyList.empty else node.x #:: toLazyList(node.next)
        
        val lazyList1 = toLazyList(l1)
        val lazyList2 = toLazyList(l2)
        val resultLazyList = lazyList1.zipAll(lazyList2, 0, 0).foldLeft((LazyList.empty[Int], 0)) {
            case ((acc, carry), (x, y)) =>
                val sum = x + y + carry
                (acc :+ (sum % 10), sum / 10)
        }

        val finalLazyList = if (resultLazyList._2 > 0) resultLazyList._1 :+ resultLazyList._2 else resultLazyList._1
        def toListNode(lazyList: LazyList[Int]): ListNode =
            if (lazyList.isEmpty) null else new ListNode(lazyList.head, toListNode(lazyList.tail))

        toListNode(finalLazyList)
    }
}

Time and Space Complexity

• Time Complexity: O(n), the functional approach using zipAll and foldLeft processes each element of the input lists exactly once, resulting in linear time complexity relative to the length of the longer list. The zipAll method pairs up elements from both lists, filling in with zeros where necessary, which operates in linear time. The foldLeft method then iterates through the paired elements to compute the sum and handle the carry, also in linear time. Hence, the overall time complexity is O(n).
• Space Complexity: O(n), the space complexity is primarily determined by the storage required for the lazy lists and the resulting linked list. Converting each input list to a LazyList involves storing each element of the list, leading to linear space usage. The zipAll method creates a new collection to hold the paired elements, adding to the space requirements. The foldLeft method builds the result lazy list by appending each computed digit, which also requires linear space. Therefore, the total space complexity, considering the storage for the input lazy lists and the result list, is O(n). The auxiliary space for variables such as accumulators and the carry is constant, but the overall space complexity is determined by the linear storage requirements.

Solution 4: Optimized Iterative Approach with In-Place Modification

This solution iterates through the linked lists and reuses existing nodes, updating their values in place to minimize additional memory usage.

Scala Code:

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
        var p = l1
        var q = l2
        val dummyHead = new ListNode(0)
        var current = dummyHead
        var carry = 0

        while (p != null || q != null) {
            val x = if (p != null) p.x else 0
            val y = if (q != null) q.x else 0
            val sum = carry + x + y
            carry = sum / 10

            if (p != null) {
                p.x = sum % 10
                current.next = p
                p = p.next
            } else {
                current.next = new ListNode(sum % 10)
            }

            if (q != null) q = q.next

            current = current.next
        }

        if (carry > 0) {
            current.next = new ListNode(carry)
        }

        dummyHead.next
    }
}

Time and Space Complexity

• Time Complexity: O(n), the algorithm processes each node of the input lists exactly once. During each iteration, the values of the current nodes from both linked lists are accessed and summed along with the carry. This involves a constant amount of work per node (value extraction, addition, carry update, and node modification). The iteration continues until all nodes in both lists have been processed, resulting in linear time complexity with respect to the length of the longer list. Hence, the overall time complexity is O(n).
• Space Complexity: O(1), this approach is highly space-efficient as it reuses nodes from the input linked lists whenever possible, thereby minimizing additional memory usage. The only new nodes created are for the result’s additional digits, which occur when the input lists have different lengths or when there is a final carry to be added. The primary memory usage is for a few auxiliary variables (dummyHead, current, p, q, carry), which do not depend on the input size and thus constitute constant space. Therefore, the overall space complexity is O(1), making this solution the most space-efficient among the approaches we have gone over.

Conclusion and Comparison

On analysis, all four Scala methods demonstrate similar time complexities, as each involves a single traversal of the input linked lists. The space complexity varies across the solutions due to different strategies for handling the result linked list and carry.

Solution 1: Iterative Approach with Carry Handling

• Pros: This approach is straightforward and easy to understand. It efficiently handles the addition of two numbers by iterating through the lists and managing the carry within a loop. The logic is clear and simple, making it easy to implement and debug.
• Cons: It requires the creation of a new linked list to store the result, which results in a space complexity of O(n). This approach is less space-efficient compared to the optimized iterative solution.

Solution 2: Recursive Approach

• Pros: The recursive approach provides an elegant and concise solution to the problem. It simplifies the iterative logic by breaking it down into smaller, manageable recursive calls. The code is clean and easy to follow, making it a good choice for those who prefer recursion.
• Cons: The recursive approach has a higher space complexity due to the recursion stack, which can lead to O(n) space usage. This can be a limitation for very large input sizes, as it may cause stack overflow issues.

Solution 3: Functional Approach with Zipping and Folding

• Pros: This solution leverages Scala’s functional programming strengths, making the code more idiomatic and expressive. The use of zipAll and foldLeft provides a concise and readable implementation.
• Cons: While this approach is elegant and functional, it may be less intuitive for those not familiar with functional programming concepts in Scala. Additionally, the space complexity is still O(n) due to the need to store intermediate lazy lists and the resulting linked list.

Solution 4: Optimized Iterative Approach with In-Place Modification

• Pros: This solution is highly space-efficient, reusing existing nodes and minimizing additional memory usage. It maintains a linear time complexity while reducing space complexity to constant space for auxiliary variables.
• Cons: The logic for node management is slightly more complex compared to the straightforward iterative approach. Careful handling of node pointers and values is required, which can make the implementation more error-prone and harder to debug.

Summary

• Solution 1: Iterative Approach with Carry Handling provides a balance between simplicity and efficiency, making it a good starting point for understanding the problem.
• Solution 2: Recursive Approach offers a clean and elegant solution, but its higher space complexity can be a limitation for large inputs.
• Solution 3: Functional Approach with Zipping and Folding leverages Scala’s functional programming features, providing a concise and expressive solution.
• Solution 4: Optimized Iterative Approach with In-Place Modification is the most space-efficient, minimizing additional memory usage by reusing existing nodes, though it requires careful implementation.

While the second solution offers elegance and the first is a straightforward approach, the third solution provides an excellent demonstration of Scala’s functional programming features, making it a great option for coding interviews to showcase language-specific capabilities. However, for practical purposes and overall efficiency, the fourth solution is the best choice due to its optimal space usage and constant space complexity, making it ideal for handling large input sizes while maintaining linear time complexity.

• LeetCode — Add Two Numbers
• Scala Documentation

Thank you for reading! If you find this guide helpful, please consider highlighting, clapping, responding or connecting with me on Twitter/X as it’s very appreciated and helps keep content like this free!

Also check out my other Leetcode Walkthrough Lists:

• Two Sum Problem
• Palindrome Number Problem

Commented Code and Step-by-Step Explanations

Solution 1: Iterative Approach with Carry Handling

In this approach, we use an iterative method to traverse the input linked lists. We maintain a running sum of the digits and handle the carry for sums greater than 9. This solution iterates through both linked lists, adding corresponding digits along with any carry from the previous step. If the sum of the digits exceeds 9, the carry is updated accordingly. A new linked list is created to store the result, with each node representing a digit of the sum. This method makes sure that all the digits are processed correctly, including the final carry if it exists.

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
        val dummy = new ListNode(0)  // Create a dummy node to serve as the head of the result list
        var current = dummy  // Initialize a pointer to build the result list
        var carry = 0  // Initialize the carry to 0

        var p = l1  // Pointer to traverse l1
        var q = l2  // Pointer to traverse l2

        while (p != null || q != null) {  // Traverse both lists
            val x = if (p != null) p.x else 0  // Get the value of the current node in l1, or 0 if l1 is null
            val y = if (q != null) q.x else 0  // Get the value of the current node in l2, or 0 if l2 is null
            val sum = carry + x + y  // Calculate the sum of the current values and the carry
            carry = sum / 10  // Update the carry
            current.next = new ListNode(sum % 10)  // Create a new node with the digit value and link it to the result list
            current = current.next  // Move to the next node in the result list

            if (p != null) p = p.next  // Move to the next node in l1
            if (q != null) q = q.next  // Move to the next node in l2
        }

        if (carry > 0) {  // If there is a remaining carry, create a new node for it
            current.next = new ListNode(carry)
        }

        dummy.next  // Return the head of the result list
    }
}

Step-by-Step Explanation

• Step 1: Initialize a dummy node to serve as the head of the result list and a current pointer to build the result list. Initialize carry to 0.
• Step 2: Traverse l1 and l2 simultaneously.
• Step 3: Extract the values of the current nodes (x and y). If a list has been fully traversed, use 0 as the value.
• Step 4: Compute the sum of the current values and the carry.
• Step 5: Determine the new carry by dividing the sum by 10.
• Step 6: Create a new node with the value of sum % 10 and link it to the result list.
• Step 7: Move the current pointer to the new node.
• Step 8: After exiting the loop, check if there is any remaining carry. If so, create a new node with the carry value and link it to the result list.
• Step 9: Return the next of the dummy node as the head of the result list.

Solution 2: Recursive Approach

This approach uses recursion to handle the addition of digits and carry, simplifying the iterative logic by breaking it down into smaller recursive calls. At each step, the function processes one digit from each input list, adds them along with the carry, and recursively proceeds to the next nodes. The base case for the recursion handles the situation where both input lists are null and no carry remains. This method leverages the call stack to manage the state, which can make the code more elegant and concise, especially for those who prefer a recursive solution.

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode, carry: Int = 0): ListNode = {
        if (l1 == null && l2 == null && carry == 0) return null  // Base case: if all are null and no carry, return null

        val sum = (if (l1 != null) l1.x else 0) + (if (l2 != null) l2.x else 0) + carry  // Compute sum
        val node = new ListNode(sum % 10)  // Create a new node with the digit value
        node.next = addTwoNumbers(if (l1 != null) l1.next else null, if (l2 != null) l2.next else null, sum / 10)  // Recursive call with next nodes and carry
        node  // Return the node
    }
}

Step-by-Step Explanation

• Step 1: Base case: If both l1 and l2 are null and there is no carry, return null.
• Step 2: Add the values of the current nodes (l1 and l2) and the carry.
• Step 3: Calculate the sum and the new carry.
• Step 4: Create a new node with the value of sum % 10.
• Step 5: Recursively call the function with the next nodes of l1 and l2, passing the new carry.
• Step 6: Link the result of the recursive call to the next of the new node.
• Step 7: Return the newly created node.

Solution 3: Functional Approach with Zipping and Folding

This approach utilizes Scala’s functional programming features, such as zip and foldLeft, to process the linked lists in a more idiomatic way. By converting the linked lists to lazy lists, we can utilize functional operations to handle the addition and carry. The zipAll method pairs elements from both lists, and foldLeft processes these pairs to compute the sum and carry for each digit. This approach demonstrates the power and expressiveness of functional programming in Scala.

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
        def toLazyList(node: ListNode): LazyList[Int] =
            if (node == null) LazyList.empty else node.x #:: toLazyList(node.next)  // Convert linked list to LazyList using recursion
        
        val lazyList1 = toLazyList(l1)  // Convert l1 to LazyList
        val lazyList2 = toLazyList(l2)  // Convert l2 to LazyList
        val resultLazyList = lazyList1.zipAll(lazyList2, 0, 0).foldLeft((LazyList.empty[Int], 0)) {  // Zip and fold the LazyLists
            case ((acc, carry), (x, y)) =>
                val sum = x + y + carry  // Calculate sum of corresponding elements and carry
                (acc :+ (sum % 10), sum / 10)  // Append digit to accumulator and update carry
        }

        val finalLazyList = if (resultLazyList._2 > 0) resultLazyList._1 :+ resultLazyList._2 else resultLazyList._1  // Append remaining carry if any
        def toListNode(lazyList: LazyList[Int]): ListNode =
            if (lazyList.isEmpty) null else new ListNode(lazyList.head, toListNode(lazyList.tail))  // Convert LazyList to linked list using recursion

        toListNode(finalLazyList)  // Convert the result lazy list back to linked list and return it
    }
}

Step-by-Step Explanation

• Step 1: Convert the linked lists to lazy lists for easier manipulation.
• Step 2: Use zipAll to pair elements from both lazy lists, filling missing values with 0.
• Step 3: Use foldLeft to process the pairs, compute the sum and carry, and build the result lazy list.
• Step 4: If there is any remaining carry after processing all elements, append it to the result lazy list.
• Step 5: Convert the result lazy list back to a linked list.
• Step 6: Return the head of the result linked list.

Solution 4: Optimized Iterative Approach with In-Place Modification

This solution iterates through the linked lists and reuses existing nodes, updating their values in place to minimize additional memory usage. By modifying the nodes directly, this approach reduces the space complexity significantly. The method makes sure that the carry is correctly managed and that the resulting linked list is formed by linking the modified nodes of the input lists. This approach is efficient in terms of space and maintains the simplicity of the iterative method.

object Solution {
    def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
        var p = l1
        var q = l2
        val dummyHead = new ListNode(0)  // Create a dummy node to serve as the head of the result list
        var current = dummyHead  // Initialize a pointer to build the result list
        var carry = 0  // Initialize the carry to 0

        while (p != null || q != null) {  // Traverse both lists
            val x = if (p != null) p.x else 0  // Get the value of the current node in l1, or 0 if l1 is null
            val y = if (q != null) q.x else 0  // Get the value of the current node in l2, or 0 if l2 is null
            val sum = carry + x + y  // Calculate the sum of the current values and the carry
            carry = sum / 10  // Update the carry

            if (p != null) {
                p.x = sum % 10  // Update the value of the current node in l1
                current.next = p  // Link the current node to the result list
                p = p.next  // Move to the next node in l1
            } else {
                current.next = new ListNode(sum % 10)  // Create a new node if p is null
            }

            if (q != null) q = q.next  // Move to the next node in l2

            current = current.next  // Move to the next node in the result list
        }

        if (carry > 0) {  // If there is a remaining carry, create a new node for it
            current.next = new ListNode(carry)
        }

        dummyHead.next  // Return the head of the result list
    }
}

Step-by-Step Explanation

• Step 1: Initialize a dummy node to serve as the head of the result list and a current pointer to build the result list. Initialize carry to 0.
• Step 2: Traverse l1 and l2 simultaneously.
• Step 3: Extract the values of the current nodes (x and y). If a list has been fully traversed, use 0 as the value.
• Step 4: Compute the sum of the current values and the carry.
• Step 5: Determine the new carry by dividing the sum by 10.
• Step 6: If p is not null, update its value to sum % 10 and link it to the result list. Otherwise, create a new node with the value of sum % 10.
• Step 7: Move the current pointer to the next node.
• Step 8: Move p and q to their next nodes.
• Step 9: After exiting the loop, check if there is any remaining carry. If so, create a new node with the carry value and link it to the result list.
• Step 10: Return the next of the dummy node as the head of the result list.