Jobs

Interviews

Discussions

Add Two Numbers II

Medium

Asked by:

More companies

42 views

Topics:

Linked ListsStacksRecursion

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3:

Input: l1 = [0], l2 = [0]
Output: [0]

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.

Follow up: Could you solve it without reversing the input lists?

Try coding it in LeetCode

Add Two Numbers II

Medium

Asked by:

42 views

Topics:

Linked ListsStacksRecursion

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3:

Input: l1 = [0], l2 = [0]
Output: [0]

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.

Follow up: Could you solve it without reversing the input lists?

Try coding it in LeetCode

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?
Can the digits in the linked lists be any integer, or are they limited to 0-9?
Should the returned linked list have leading zeros? For example, if the sum is 0, should I return a single node with value 0 or an empty list?
Are the input linked lists guaranteed to be non-empty, as stated, or should I handle cases where either l1 or l2 (or both) are null/empty?
What is the maximum possible length of the linked lists?

Brute Force Solution

Approach

Imagine you have two numbers represented as lists, with each digit being a list item. The brute force approach involves converting each list into actual whole numbers, adding them together, and then converting the result back into a list of digits.

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

First, turn each list of digits into a whole number. Treat each digit as part of a bigger number by figuring out its place value (ones, tens, hundreds, etc.) and combining them.
Once both lists are whole numbers, simply add them together to get their sum.
Now, take that sum and convert it back into a list of digits. You can do this by breaking down the sum into its individual digits by looking at the ones place, the tens place, and so on, and putting each digit into a new list.

Code Implementation

def add_two_numbers_ii_brute_force(list1, list2):
    first_number = 0
    for digit in list1:
        first_number = first_number * 10 + digit

    second_number = 0
    for digit in list2:
        second_number = second_number * 10 + digit

    # Convert the lists to numbers and find their sum.
    total_sum = first_number + second_number

    result_list = []

    # Handle the case where the sum is zero.
    if total_sum == 0:
        return [0]

    # Convert the sum back into a list of digits.
    while total_sum > 0:
        digit = total_sum % 10

        # Extract digits and add to result.
        result_list.insert(0, digit)
        total_sum //= 10

    return result_list

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves iterating through each linked list once to convert it into a number. Converting a list of n digits to a number takes O(n) time. Adding the two numbers takes constant O(1) time. Finally, converting the sum back into a list of digits takes at most O(n+m) which simplifies to O(n) where n and m are length of the initial lists. The overall time complexity is dominated by converting linked lists to numbers and back, which is O(n).

Space Complexity

O(N) – The algorithm creates a new list to store the result of adding the two numbers. In the worst-case scenario, where the sum requires as many digits as the longer of the two input lists, the size of this new list will be proportional to the number of digits in the sum. Converting the sum back into a list of digits may create up to N digits where N is the number of digits in the sum of the two input numbers. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The challenge is to add two numbers that are represented as linked lists, where the most significant digit comes first. The clever trick is to use stacks to reverse the order of digits without actually modifying the lists, allowing us to add from the least significant digit, just like we do with pen and paper.

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

Put all digits of the first number into a stack. Imagine stacking them one on top of another, with the last digit at the top.
Do the same for the second number, putting its digits into another stack.
Now, start adding the digits from the top of each stack. This is like adding from the rightmost digit of each number.
If the sum of the digits is more than 9, keep the ones digit and carry over the tens digit (which will be 1) to the next addition.
Create a new linked list node for each sum, and put the node at the beginning of the result list.
Continue until both stacks are empty and there's no carry-over left. If there's a remaining carry-over after processing all digits, add it as a new node at the beginning of the list.
The resulting linked list now represents the sum of the two numbers, with the most significant digit at the beginning.

Code Implementation

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

def addTwoNumbers(list1, list2):
    stack1 = []
    stack2 = []

    while list1:
        stack1.append(list1.val)
        list1 = list1.next

    while list2:
        stack2.append(list2.val)
        list2 = list2.next

    carry = 0
    result = None

    # Process digits from stacks, simulating adding from right to left
    while stack1 or stack2 or carry:
        digit1 = stack1.pop() if stack1 else 0
        digit2 = stack2.pop() if stack2 else 0

        sum_of_digits = digit1 + digit2 + carry
        carry = sum_of_digits // 10
        digit = sum_of_digits % 10

        # Construct new node at the beginning of result list
        new_node = ListNode(digit)
        new_node.next = result
        result = new_node

    return result

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each linked list once to push the nodes' values onto the stacks. Then, it iterates at most max(len(l1), len(l2)) times where l1 and l2 are the two input lists to perform the addition by popping from the stack, where each pop and addition operation takes constant time. Lastly, inserting a node at the beginning of a linked list is O(1), so the total time complexity is dominated by the stack push and pop operations, resulting in O(n) where n is the length of the longer linked list.

Space Complexity

O(N) – The primary space usage comes from the two stacks used to store the digits of the input linked lists. Let N be the total number of nodes in the two linked lists. In the worst case, one list could be significantly longer than the other, leading to stacks containing all N nodes' values. Therefore, the auxiliary space is proportional to N. Additionally, the resulting linked list to store the sum could contain up to N+1 nodes, further contributing to O(N) space.

Edge Cases

Case	How to Handle
Both input lists are null or empty.	Return null (or an empty list) if both input lists are null, indicating a sum of zero.
One list is null or empty while the other is not.	Treat the null/empty list as representing zero, and effectively just return the non-null list.
Input lists have significantly different lengths.	Pad the shorter list with leading zeros (conceptually, using stacks to align) to ensure correct digit-by-digit addition.
Sum results in a carry-over to a new most significant digit.	Add a new node with the carry-over value at the head of the resulting list.
Input lists represent very large numbers that might cause integer overflow if converted to native integer types.	The linked list representation itself handles arbitrarily large numbers, as intermediate calculations are done digit by digit, so no overflow should occur.
All digits in one or both lists are zeros.	Handle the case correctly, resulting in a single node with the value zero, unless both lists are empty.
Carry propagation through many digits.	Ensure the carry is propagated correctly through multiple nodes during the digit-by-digit addition, updating each node's value and carry appropriately.
Leading zeros are present in either of the input lists (other than single 0)	While the problem states the lists represent non-negative integers, handle leading zeros by stripping them, or include logic during addition not to include the leading zeros.

Both input lists are null or empty.

How to Handle:

Return null (or an empty list) if both input lists are null, indicating a sum of zero.

One list is null or empty while the other is not.

How to Handle:

Treat the null/empty list as representing zero, and effectively just return the non-null list.

Input lists have significantly different lengths.

How to Handle:

Pad the shorter list with leading zeros (conceptually, using stacks to align) to ensure correct digit-by-digit addition.

Sum results in a carry-over to a new most significant digit.

How to Handle:

Add a new node with the carry-over value at the head of the resulting list.

Input lists represent very large numbers that might cause integer overflow if converted to native integer types.

How to Handle:

The linked list representation itself handles arbitrarily large numbers, as intermediate calculations are done digit by digit, so no overflow should occur.

All digits in one or both lists are zeros.

How to Handle:

Handle the case correctly, resulting in a single node with the value zero, unless both lists are empty.

Carry propagation through many digits.

How to Handle:

Ensure the carry is propagated correctly through multiple nodes during the digit-by-digit addition, updating each node's value and carry appropriately.

Leading zeros are present in either of the input lists (other than single 0)

How to Handle:

While the problem states the lists represent non-negative integers, handle leading zeros by stripping them, or include logic during addition not to include the 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?
Can the digits in the linked lists be any integer, or are they limited to 0-9?
Should the returned linked list have leading zeros? For example, if the sum is 0, should I return a single node with value 0 or an empty list?
Are the input linked lists guaranteed to be non-empty, as stated, or should I handle cases where either l1 or l2 (or both) are null/empty?
What is the maximum possible length of the linked lists?

Brute Force Solution

Approach

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

First, turn each list of digits into a whole number. Treat each digit as part of a bigger number by figuring out its place value (ones, tens, hundreds, etc.) and combining them.
Once both lists are whole numbers, simply add them together to get their sum.
Now, take that sum and convert it back into a list of digits. You can do this by breaking down the sum into its individual digits by looking at the ones place, the tens place, and so on, and putting each digit into a new list.

Code Implementation

def add_two_numbers_ii_brute_force(list1, list2):
    first_number = 0
    for digit in list1:
        first_number = first_number * 10 + digit

    second_number = 0
    for digit in list2:
        second_number = second_number * 10 + digit

    # Convert the lists to numbers and find their sum.
    total_sum = first_number + second_number

    result_list = []

    # Handle the case where the sum is zero.
    if total_sum == 0:
        return [0]

    # Convert the sum back into a list of digits.
    while total_sum > 0:
        digit = total_sum % 10

        # Extract digits and add to result.
        result_list.insert(0, digit)
        total_sum //= 10

    return result_list

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Put all digits of the first number into a stack. Imagine stacking them one on top of another, with the last digit at the top.
Do the same for the second number, putting its digits into another stack.
Now, start adding the digits from the top of each stack. This is like adding from the rightmost digit of each number.
If the sum of the digits is more than 9, keep the ones digit and carry over the tens digit (which will be 1) to the next addition.
Create a new linked list node for each sum, and put the node at the beginning of the result list.
Continue until both stacks are empty and there's no carry-over left. If there's a remaining carry-over after processing all digits, add it as a new node at the beginning of the list.
The resulting linked list now represents the sum of the two numbers, with the most significant digit at the beginning.

Code Implementation

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

def addTwoNumbers(list1, list2):
    stack1 = []
    stack2 = []

    while list1:
        stack1.append(list1.val)
        list1 = list1.next

    while list2:
        stack2.append(list2.val)
        list2 = list2.next

    carry = 0
    result = None

    # Process digits from stacks, simulating adding from right to left
    while stack1 or stack2 or carry:
        digit1 = stack1.pop() if stack1 else 0
        digit2 = stack2.pop() if stack2 else 0

        sum_of_digits = digit1 + digit2 + carry
        carry = sum_of_digits // 10
        digit = sum_of_digits % 10

        # Construct new node at the beginning of result list
        new_node = ListNode(digit)
        new_node.next = result
        result = new_node

    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both input lists are null or empty.	Return null (or an empty list) if both input lists are null, indicating a sum of zero.
One list is null or empty while the other is not.	Treat the null/empty list as representing zero, and effectively just return the non-null list.
Input lists have significantly different lengths.	Pad the shorter list with leading zeros (conceptually, using stacks to align) to ensure correct digit-by-digit addition.
Sum results in a carry-over to a new most significant digit.	Add a new node with the carry-over value at the head of the resulting list.
Input lists represent very large numbers that might cause integer overflow if converted to native integer types.	The linked list representation itself handles arbitrarily large numbers, as intermediate calculations are done digit by digit, so no overflow should occur.
All digits in one or both lists are zeros.	Handle the case correctly, resulting in a single node with the value zero, unless both lists are empty.
Carry propagation through many digits.	Ensure the carry is propagated correctly through multiple nodes during the digit-by-digit addition, updating each node's value and carry appropriately.
Leading zeros are present in either of the input lists (other than single 0)	While the problem states the lists represent non-negative integers, handle leading zeros by stripping them, or include logic during addition not to include the leading zeros.

Both input lists are null or empty.

How to Handle:

Return null (or an empty list) if both input lists are null, indicating a sum of zero.

One list is null or empty while the other is not.

How to Handle:

Treat the null/empty list as representing zero, and effectively just return the non-null list.

Input lists have significantly different lengths.

How to Handle:

Pad the shorter list with leading zeros (conceptually, using stacks to align) to ensure correct digit-by-digit addition.

Sum results in a carry-over to a new most significant digit.

How to Handle:

Add a new node with the carry-over value at the head of the resulting list.

Input lists represent very large numbers that might cause integer overflow if converted to native integer types.

How to Handle:

The linked list representation itself handles arbitrarily large numbers, as intermediate calculations are done digit by digit, so no overflow should occur.

All digits in one or both lists are zeros.

How to Handle:

Handle the case correctly, resulting in a single node with the value zero, unless both lists are empty.

Carry propagation through many digits.

How to Handle:

Ensure the carry is propagated correctly through multiple nodes during the digit-by-digit addition, updating each node's value and carry appropriately.

Leading zeros are present in either of the input lists (other than single 0)

How to Handle:

While the problem states the lists represent non-negative integers, handle leading zeros by stripping them, or include logic during addition not to include the leading zeros.