Jobs

Interviews

Discussions

Add Two Numbers #11 Most Asked

Medium

Adobe

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

Try coding it in LeetCode

Add Two Numbers #11 Most Asked

Medium

Adobe

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

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:

Could the input linked lists be of different lengths?
Are the digits in the nodes guaranteed to be single digits from 0 to 9?
What is the maximum number of nodes we can expect in each linked list?
Should I handle the case where one or both of the input linked lists are null?
Is it possible for the input numbers to be zero, for example, a linked list with a single node containing the value 0?

Brute Force Solution

Approach

The most direct way to solve this is to treat it like a simple arithmetic problem. We'll first convert each list of digits into the actual number it represents, then add these two numbers together using standard math, and finally, convert the sum back into a new list of digits.

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

First, take the first list of digits and read it from start to finish to figure out the complete number it stands for.
Do the exact same thing for the second list of digits to determine its complete number.
Now that you have two regular numbers, add them together just like you would on paper or with a calculator to get a final sum.
Take this final sum and break it down, digit by digit, starting from the ones place.
Create a new list, placing each digit of the sum into its own spot, making sure to put the ones digit first, then the tens digit, and so on.
This new list of digits is your final answer.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def add_two_numbers_brute_force(first_list, second_list):
    first_number = 0
    second_number = 0
    multiplier = 1
    current_node = first_list

    while current_node is not None:
        # Build the complete number by adding the value of each digit scaled by its position.
        first_number = first_number + current_node.value * multiplier
        multiplier = multiplier * 10
        current_node = current_node.next_node

    multiplier = 1
    current_node = second_list

    while current_node is not None:
        # Replicate the number conversion process for the second list.
        second_number = second_number + current_node.value * multiplier
        multiplier = multiplier * 10
        current_node = current_node.next_node

    sum_of_numbers = first_number + second_number

    dummy_head = ListNode()
    current_new_node = dummy_head

    if sum_of_numbers == 0:
        return ListNode(0)

    # Convert the calculated sum back into a list of digits in reverse order.
    while sum_of_numbers > 0:
        digit = sum_of_numbers % 10
        current_new_node.next_node = ListNode(digit)
        current_new_node = current_new_node.next_node
        sum_of_numbers = sum_of_numbers // 10

    # The dummy head was used to simplify list creation, so we return the actual starting node.
    return dummy_head.next_node

Big(O) Analysis

Time Complexity

O(max(n, m)) – The complexity is determined by the length of the input lists and the resulting sum. Let the lengths of the two lists be n and m. Converting the first list to a number takes n operations, and converting the second takes m operations. The number of digits in the sum will be proportional to the larger of the two initial numbers, so converting the sum back to a list takes roughly max(n, m) operations. Therefore, the total operations are dominated by the length of the longest input list, which simplifies to O(max(n, m)).

Space Complexity

O(max(M, N)) – The algorithm first converts the two input lists into two integer numbers, which requires storing two variables whose size depends on the number of digits in the lists. Then, it calculates their sum, which is also stored in a variable. The primary auxiliary space is used for the new list created to hold the digits of the final sum. The length of this resulting list is determined by the number of digits in the sum, which is at most one greater than the number of digits in the longer of the two input lists, where M and N are the lengths of the input lists.

Optimal Solution

Approach

The best way to solve this is to mimic how you'd add two large numbers by hand, column by column, from right to left. We'll start with the first digit of each number, add them up, and keep track of any amount we need to carry over to the next column, just like grade-school math.

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

Imagine the two numbers written one above the other, ready for addition.
Start with the rightmost digits (the beginning of each sequence) and add them together.
If the sum is 10 or more, you'll have a two-digit result. The second digit is what you write down for your answer's first digit, and the first digit (which will always be a '1') is the 'carry' that you'll remember for the next step.
Move to the next pair of digits to the left.
Add these two digits together, and also add the 'carry' from the previous step if there was one.
Again, write down the final digit of this new sum and carry over the '1' if the sum was 10 or more.
Continue this process, moving one position at a time, until you've gone through all the digits in both numbers.
If one number runs out of digits before the other, just pretend it has a zero in that spot and keep going.
After the very last addition, if you still have a '1' to carry over, that becomes the final, leftmost digit of your answer.

Code Implementation

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

def addTwoNumbers(list_one, list_two):
    dummy_head = ListNode(0)
    current_result_node = dummy_head
    carry_over = 0

    pointer_one = list_one
    pointer_two = list_two

    # Iterate through both lists until all digits are processed.
    while pointer_one is not None or pointer_two is not None:
        value_one = pointer_one.val if pointer_one is not None else 0
        value_two = pointer_two.val if pointer_two is not None else 0

        current_sum = value_one + value_two + carry_over

        # The new carry is the tens digit of the sum (e.g., 1 from 15).
        carry_over = current_sum // 10
        new_digit = current_sum % 10

        current_result_node.next = ListNode(new_digit)
        current_result_node = current_result_node.next

        if pointer_one is not None:
            pointer_one = pointer_one.next
        if pointer_two is not None:
            pointer_two = pointer_two.next

    # If there's a leftover carry after the last addition, it must be the most significant digit.
    if carry_over > 0:
        current_result_node.next = ListNode(carry_over)

    # The dummy head's next node is the actual start of our resulting list.
    return dummy_head.next

Big(O) Analysis

Time Complexity

O(max(m, n)) – The algorithm simulates manual addition by processing the digits of the two numbers one by one in a single pass. The process involves a single loop that continues until we have traversed all digits of both input numbers. Let the number of digits be m and n respectively; the total number of additions performed is determined by the length of the longer number. Therefore, the time complexity is directly proportional to the maximum of m and n, which simplifies to O(max(m, n)).

Space Complexity

O(N) – The algorithm constructs a new sequence to store the result. The length of this new sequence is directly proportional to the length of the longer of the two input numbers. In the worst case, the result sequence will have N+1 digits, where N is the length of the longer input number. Therefore, the space required for the answer grows linearly with the size of the input, in addition to a single variable needed to keep track of the 'carry' value.

Edge Cases

Case	How to Handle
Input lists of different lengths	The algorithm should treat missing nodes on the shorter list as having a value of zero.
Sum results in a carry on the most significant digit	A new node must be created for the final carry value after the main loop finishes.
One or both input lists are null	The problem states inputs are non-empty, but robust code should return the non-null list or null if both are null.
One or both input lists contain a single node	The general iterative approach handles this case correctly without any special logic.
Input numbers are very large, leading to long lists	A standard iterative solution handles this efficiently with O(max(N, M)) time and space complexity.
Input lists representing the number zero (a single node with value 0)	Adding a list representing zero to another list should correctly return a copy of the other list.
The sum of digits at a position is exactly 9 with a carry-in of 1	This correctly results in a node with value 0 and a carry-out of 1, which the loop logic must handle.
Potential for integer overflow if converting lists to numbers	The digit-by-digit summation approach avoids this language-specific overflow issue entirely.

Input lists of different lengths

How to Handle:

The algorithm should treat missing nodes on the shorter list as having a value of zero.

Sum results in a carry on the most significant digit

How to Handle:

A new node must be created for the final carry value after the main loop finishes.

One or both input lists are null

How to Handle:

The problem states inputs are non-empty, but robust code should return the non-null list or null if both are null.

One or both input lists contain a single node

How to Handle:

The general iterative approach handles this case correctly without any special logic.

Input numbers are very large, leading to long lists

How to Handle:

A standard iterative solution handles this efficiently with O(max(N, M)) time and space complexity.

Input lists representing the number zero (a single node with value 0)

How to Handle:

Adding a list representing zero to another list should correctly return a copy of the other list.

The sum of digits at a position is exactly 9 with a carry-in of 1

How to Handle:

This correctly results in a node with value 0 and a carry-out of 1, which the loop logic must handle.

Potential for integer overflow if converting lists to numbers

How to Handle:

The digit-by-digit summation approach avoids this language-specific overflow issue entirely.

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:

Could the input linked lists be of different lengths?
Are the digits in the nodes guaranteed to be single digits from 0 to 9?
What is the maximum number of nodes we can expect in each linked list?
Should I handle the case where one or both of the input linked lists are null?
Is it possible for the input numbers to be zero, for example, a linked list with a single node containing the value 0?

Brute Force Solution

Approach

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

First, take the first list of digits and read it from start to finish to figure out the complete number it stands for.
Do the exact same thing for the second list of digits to determine its complete number.
Now that you have two regular numbers, add them together just like you would on paper or with a calculator to get a final sum.
Take this final sum and break it down, digit by digit, starting from the ones place.
Create a new list, placing each digit of the sum into its own spot, making sure to put the ones digit first, then the tens digit, and so on.
This new list of digits is your final answer.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def add_two_numbers_brute_force(first_list, second_list):
    first_number = 0
    second_number = 0
    multiplier = 1
    current_node = first_list

    while current_node is not None:
        # Build the complete number by adding the value of each digit scaled by its position.
        first_number = first_number + current_node.value * multiplier
        multiplier = multiplier * 10
        current_node = current_node.next_node

    multiplier = 1
    current_node = second_list

    while current_node is not None:
        # Replicate the number conversion process for the second list.
        second_number = second_number + current_node.value * multiplier
        multiplier = multiplier * 10
        current_node = current_node.next_node

    sum_of_numbers = first_number + second_number

    dummy_head = ListNode()
    current_new_node = dummy_head

    if sum_of_numbers == 0:
        return ListNode(0)

    # Convert the calculated sum back into a list of digits in reverse order.
    while sum_of_numbers > 0:
        digit = sum_of_numbers % 10
        current_new_node.next_node = ListNode(digit)
        current_new_node = current_new_node.next_node
        sum_of_numbers = sum_of_numbers // 10

    # The dummy head was used to simplify list creation, so we return the actual starting node.
    return dummy_head.next_node

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine the two numbers written one above the other, ready for addition.
Start with the rightmost digits (the beginning of each sequence) and add them together.
If the sum is 10 or more, you'll have a two-digit result. The second digit is what you write down for your answer's first digit, and the first digit (which will always be a '1') is the 'carry' that you'll remember for the next step.
Move to the next pair of digits to the left.
Add these two digits together, and also add the 'carry' from the previous step if there was one.
Again, write down the final digit of this new sum and carry over the '1' if the sum was 10 or more.
Continue this process, moving one position at a time, until you've gone through all the digits in both numbers.
If one number runs out of digits before the other, just pretend it has a zero in that spot and keep going.
After the very last addition, if you still have a '1' to carry over, that becomes the final, leftmost digit of your answer.

Code Implementation

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

def addTwoNumbers(list_one, list_two):
    dummy_head = ListNode(0)
    current_result_node = dummy_head
    carry_over = 0

    pointer_one = list_one
    pointer_two = list_two

    # Iterate through both lists until all digits are processed.
    while pointer_one is not None or pointer_two is not None:
        value_one = pointer_one.val if pointer_one is not None else 0
        value_two = pointer_two.val if pointer_two is not None else 0

        current_sum = value_one + value_two + carry_over

        # The new carry is the tens digit of the sum (e.g., 1 from 15).
        carry_over = current_sum // 10
        new_digit = current_sum % 10

        current_result_node.next = ListNode(new_digit)
        current_result_node = current_result_node.next

        if pointer_one is not None:
            pointer_one = pointer_one.next
        if pointer_two is not None:
            pointer_two = pointer_two.next

    # If there's a leftover carry after the last addition, it must be the most significant digit.
    if carry_over > 0:
        current_result_node.next = ListNode(carry_over)

    # The dummy head's next node is the actual start of our resulting list.
    return dummy_head.next

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input lists of different lengths	The algorithm should treat missing nodes on the shorter list as having a value of zero.
Sum results in a carry on the most significant digit	A new node must be created for the final carry value after the main loop finishes.
One or both input lists are null	The problem states inputs are non-empty, but robust code should return the non-null list or null if both are null.
One or both input lists contain a single node	The general iterative approach handles this case correctly without any special logic.
Input numbers are very large, leading to long lists	A standard iterative solution handles this efficiently with O(max(N, M)) time and space complexity.
Input lists representing the number zero (a single node with value 0)	Adding a list representing zero to another list should correctly return a copy of the other list.
The sum of digits at a position is exactly 9 with a carry-in of 1	This correctly results in a node with value 0 and a carry-out of 1, which the loop logic must handle.
Potential for integer overflow if converting lists to numbers	The digit-by-digit summation approach avoids this language-specific overflow issue entirely.

Input lists of different lengths

How to Handle:

The algorithm should treat missing nodes on the shorter list as having a value of zero.

Sum results in a carry on the most significant digit

How to Handle:

A new node must be created for the final carry value after the main loop finishes.

One or both input lists are null

How to Handle:

The problem states inputs are non-empty, but robust code should return the non-null list or null if both are null.

One or both input lists contain a single node

How to Handle:

The general iterative approach handles this case correctly without any special logic.

Input numbers are very large, leading to long lists

How to Handle:

A standard iterative solution handles this efficiently with O(max(N, M)) time and space complexity.

Input lists representing the number zero (a single node with value 0)

How to Handle:

Adding a list representing zero to another list should correctly return a copy of the other list.

The sum of digits at a position is exactly 9 with a carry-in of 1

How to Handle:

This correctly results in a node with value 0 and a carry-out of 1, which the loop logic must handle.

Potential for integer overflow if converting lists to numbers

How to Handle:

The digit-by-digit summation approach avoids this language-specific overflow issue entirely.

0/0 Adobe questions completed

0/0 completed