Add Two Numbers Leetcode Solution in Python PyPixel

We’re going to be discussing Add Two Numbers Leetcode Solution in Python which is a Leetcode Medium Problem (#2).
The “Add Two Numbers” problem on LeetCode presents an interesting challenge of adding two non-negative integers represented by linked lists. The digits of these numbers are stored in reverse order, and each node in the linked list contains a single digit. The task is to perform the addition and return the result as a linked list.

Problem Statement

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.

Leetcode Problem Link: https://leetcode.com/problems/add-two-numbers/

Solution

BruteForce Approach

Details:

1. Convert to Number: The linked lists are traversed to convert each digit into an integer, and the two resulting integers are summed.
2. Perform Addition: The sum is then converted back into a linked list, with each digit represented by a node.

Summary:

• The brute force solution involves converting linked lists to integers, performing addition, and then converting the result back to a linked list.
• The time complexity is dominated by the conversion steps, making it less efficient for large numbers.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def addTwoNumbersBruteForce(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        num1 = self.convert_to_number(l1)
        num2 = self.convert_to_number(l2)
        result = num1 + num2

        return self.convert_to_linked_list(result)

    def convert_to_number(self, node):
        result = 0
        multiplier = 1

        while node:
            result += node.val * multiplier
            multiplier *= 10
            node = node.next

        return result

    def convert_to_linked_list(self, number):
        dummy = ListNode()
        current = dummy

        for digit in str(number)[::-1]:
            current.next = ListNode(int(digit))
            current = current.next

        return dummy.next

Time Complexity:

• Conversion to Number: O(n) where n is the length of the longer linked list.
• Conversion to Linked List: O(m) where m is the number of digits in the sum.

Optimal Approach

Details:

1. Two-Pointer Iteration: Similar to the better solution, two pointers traverse both linked lists simultaneously.
2. Perform Addition: Addition is performed digit by digit, considering any carry from the previous step.
3. Create Result List: The result is constructed in-place, and a new linked list is returned.

Summary:

• The optimal solution shares similarities with the better solution but minimizes the use of variables and combines the addition logic with the iteration.
• It maintains efficiency and handles edge cases effectively.

class Solution:
    def addTwoNumbersOptimal(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        current = dummy
        carry = 0

        while l1 or l2 or carry:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0

            total_sum = x + y + carry
            carry, digit = divmod(total_sum, 10)

            current.next = ListNode(digit)
            current = current.next

            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

        return dummy.next

Time Complexity:

• Iterating Through Lists: O(max(n, m)) where n and m are the lengths of the input linked lists.

So these two were the brute and optimal solutions for add two numbers leetcode problem in python. I hope you got a good understanding of the solution and will be able to solve this problem upon iterations.

Something You Might Like: