Jobs

Interviews

Discussions

Add Two Numbers

Medium

Google

65 views

Topics:

Linked Lists

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.

Add Two Numbers

Medium

Google

65 views

Topics:

Linked Lists

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.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked lists be of different lengths?
What is the range of values that each node in the linked list can have?
Is it possible for the input linked lists to be empty, and if so, what should I return?
Should the result linked list have leading zeros if the sum does?
Are the input numbers guaranteed to be non-negative?

Brute Force Solution

Approach

We're given two numbers represented as linked lists, and need to add them together. A brute force approach involves converting each linked list into regular numbers, adding the numbers, and then converting the result back into a linked list.

Here's how the algorithm would work step-by-step:

Take the first linked list and convert it into a normal number. This is done by figuring out what number each part of the list represents based on its position and adding them together.
Do the exact same thing with the second linked list, converting it into its number representation.
Now that we have both numbers, simply add them together like normal math.
Take the result of that addition, and break it down into individual digits.
Finally, create a new linked list where each digit from the sum becomes a part of this new list.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def add_two_numbers_brute_force(list_one, list_two):
    def linked_list_to_integer(linked_list):
        number = 0
        power_of_ten = 1
        current_node = linked_list

        while current_node:
            number += current_node.val * power_of_ten
            power_of_ten *= 10
            current_node = current_node.next
        return number

    # Convert the linked lists to integers
    number_one = linked_list_to_integer(list_one)
    number_two = linked_list_to_integer(list_two)

    # Add the numbers together
    total_sum = number_one + number_two

    # Handle the case where the sum is zero
    if total_sum == 0:
        return ListNode(0)

    # Convert the sum to a linked list
    head = None
    tail = None

    while total_sum > 0:
        digit = total_sum % 10
        total_sum //= 10
        new_node = ListNode(digit)

        # Build linked list, setting head
        if not head:
            head = new_node
            tail = new_node
        else:
            tail.next = new_node
            tail = new_node

    return head

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(max(m,n)) – Converting the first linked list of length m to a number takes O(m) time. Similarly, converting the second linked list of length n to a number takes O(n) time. Adding the two resulting numbers is O(1). Converting the sum back into a linked list takes O(log10(sum)), where sum is the result of the addition, which is bounded by the number of digits in the larger of the two input numbers. Since the maximum digits are proportional to max(m,n), the conversion back to a linked list is O(max(m,n)). Therefore, the overall time complexity is dominated by O(m) + O(n) + O(max(m,n)), which simplifies to O(max(m,n)).

Space Complexity

O(max(N, M)) – The space complexity is determined by the creation of the linked list to store the sum. The length of the resulting linked list is at most max(N, M) + 1, where N and M are the number of nodes in the input linked lists respectively (since we consider the number of digits). Converting the input linked lists to integers requires constant space. However, creating the new linked list from the sum requires space proportional to the number of digits in the sum, so the resulting linked list that stores the sum dictates the space. Therefore, the auxiliary space used is O(max(N, M)).

Optimal Solution

Approach

The key is to simulate adding the numbers the same way you would do it on paper, digit by digit, handling any carry-over values as you go. We process both numbers simultaneously, starting from their least significant digits, and build the result one digit at a time.

Here's how the algorithm would work step-by-step:

Start by looking at the rightmost digits of both numbers.
Add these digits together. If the sum is 10 or greater, note that you have a 'carry' of 1 to add to the next digits.
Create a new digit for the result using the ones place of this sum (meaning if the sum was 12 you would use a 2).
Now, move to the next digits in both numbers, moving from right to left.
Add these digits together, and also add any 'carry' value from the previous step.
Again, determine the ones place of the sum as the next digit of your result.
If you have a sum of 10 or greater, keep track of the 'carry' to add in the next step.
Repeat steps 4-7 until you have processed all digits from both numbers.
If after processing all digits there's still a 'carry', add a new digit with the value of the 'carry' to the beginning of the result.
The final result is the number represented by the digits you've created.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(list1, list2):
    carry = 0
    dummy_head = ListNode(0)
    current_node = dummy_head

    while list1 or list2:
        value_list1 = list1.val if list1 else 0
        value_list2 = list2.val if list2 else 0

        # Sum the digits and account for any carry
        digit_sum = value_list1 + value_list2 + carry

        # Determine the new carry for the next iteration
        carry = digit_sum // 10

        current_node.next = ListNode(digit_sum % 10)
        current_node = current_node.next

        if list1:
            list1 = list1.next
        if list2:
            list2 = list2.next

    # Add the final carry if it exists
    if carry > 0:
        current_node.next = ListNode(carry)

    return dummy_head.next

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(max(m, n)) – The time complexity is determined by the lengths of the two input linked lists, which we'll denote as 'm' and 'n' respectively. We iterate through both lists simultaneously, performing a constant-time addition operation at each step. The loop continues until we reach the end of both lists. Therefore, the number of iterations is bounded by the length of the longer list. Hence, the time complexity is O(max(m, n)).

Space Complexity

O(N) – The algorithm constructs a new linked list to store the sum of the two numbers. The size of this new linked list will be, at most, one greater than the length of the longer of the two input linked lists. Therefore, in the worst-case scenario, the space complexity is directly proportional to N, where N represents the maximum number of digits in either input number. This is because each node in the new list holds a digit of the sum. Thus the auxiliary space used is O(N).

Edge Cases

Case	How to Handle
Both input lists are empty (null)	Return a linked list with a single node containing 0 or return null, depending on the specific requirement; handle by checking for null lists at the beginning and returning a appropriate value.
One list is empty (null), the other is not	Treat the empty list as a list of zeros, allowing the non-empty list to be returned or used in calculation with the zero list.
Lists of significantly different lengths	Iterate until both lists are exhausted, handling remaining digits of the longer list with a possible carry-over.
Large numbers causing integer overflow	Use `long` data type to store intermediate sums to avoid immediate overflow, then mod by 10 before assigning to Node.
Carry-over at the most significant digit	After processing all digits, check for a remaining carry and add a new node to the end of the result list if needed.
One or both input lists contain a single node with value 0	The algorithm should correctly handle lists with a single node having a value of zero and properly add it with the other number, accounting for potential carry-over.
Resultant sum is zero	Return a linked list containing a single node with value 0.
Very long lists that could exhaust memory	The solution uses constant extra space for the carry value and the result list nodes, so scalability is determined by the size of the input, but creation of a very long list could lead to memory issues.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked lists be of different lengths?
What is the range of values that each node in the linked list can have?
Is it possible for the input linked lists to be empty, and if so, what should I return?
Should the result linked list have leading zeros if the sum does?
Are the input numbers guaranteed to be non-negative?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first linked list and convert it into a normal number. This is done by figuring out what number each part of the list represents based on its position and adding them together.
Do the exact same thing with the second linked list, converting it into its number representation.
Now that we have both numbers, simply add them together like normal math.
Take the result of that addition, and break it down into individual digits.
Finally, create a new linked list where each digit from the sum becomes a part of this new list.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def add_two_numbers_brute_force(list_one, list_two):
    def linked_list_to_integer(linked_list):
        number = 0
        power_of_ten = 1
        current_node = linked_list

        while current_node:
            number += current_node.val * power_of_ten
            power_of_ten *= 10
            current_node = current_node.next
        return number

    # Convert the linked lists to integers
    number_one = linked_list_to_integer(list_one)
    number_two = linked_list_to_integer(list_two)

    # Add the numbers together
    total_sum = number_one + number_two

    # Handle the case where the sum is zero
    if total_sum == 0:
        return ListNode(0)

    # Convert the sum to a linked list
    head = None
    tail = None

    while total_sum > 0:
        digit = total_sum % 10
        total_sum //= 10
        new_node = ListNode(digit)

        # Build linked list, setting head
        if not head:
            head = new_node
            tail = new_node
        else:
            tail.next = new_node
            tail = new_node

    return head

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the rightmost digits of both numbers.
Add these digits together. If the sum is 10 or greater, note that you have a 'carry' of 1 to add to the next digits.
Create a new digit for the result using the ones place of this sum (meaning if the sum was 12 you would use a 2).
Now, move to the next digits in both numbers, moving from right to left.
Add these digits together, and also add any 'carry' value from the previous step.
Again, determine the ones place of the sum as the next digit of your result.
If you have a sum of 10 or greater, keep track of the 'carry' to add in the next step.
Repeat steps 4-7 until you have processed all digits from both numbers.
If after processing all digits there's still a 'carry', add a new digit with the value of the 'carry' to the beginning of the result.
The final result is the number represented by the digits you've created.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(list1, list2):
    carry = 0
    dummy_head = ListNode(0)
    current_node = dummy_head

    while list1 or list2:
        value_list1 = list1.val if list1 else 0
        value_list2 = list2.val if list2 else 0

        # Sum the digits and account for any carry
        digit_sum = value_list1 + value_list2 + carry

        # Determine the new carry for the next iteration
        carry = digit_sum // 10

        current_node.next = ListNode(digit_sum % 10)
        current_node = current_node.next

        if list1:
            list1 = list1.next
        if list2:
            list2 = list2.next

    # Add the final carry if it exists
    if carry > 0:
        current_node.next = ListNode(carry)

    return dummy_head.next

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both input lists are empty (null)	Return a linked list with a single node containing 0 or return null, depending on the specific requirement; handle by checking for null lists at the beginning and returning a appropriate value.
One list is empty (null), the other is not	Treat the empty list as a list of zeros, allowing the non-empty list to be returned or used in calculation with the zero list.
Lists of significantly different lengths	Iterate until both lists are exhausted, handling remaining digits of the longer list with a possible carry-over.
Large numbers causing integer overflow	Use `long` data type to store intermediate sums to avoid immediate overflow, then mod by 10 before assigning to Node.
Carry-over at the most significant digit	After processing all digits, check for a remaining carry and add a new node to the end of the result list if needed.
One or both input lists contain a single node with value 0	The algorithm should correctly handle lists with a single node having a value of zero and properly add it with the other number, accounting for potential carry-over.
Resultant sum is zero	Return a linked list containing a single node with value 0.
Very long lists that could exhaust memory	The solution uses constant extra space for the carry value and the result list nodes, so scalability is determined by the size of the input, but creation of a very long list could lead to memory issues.