What is the time complexity of Add Two Numbers?

The optimal solution has a time complexity of O(max(m, n)).

What is the space complexity of Add Two Numbers?

The space complexity is O(max(m, n)).

What data structures are used to solve Add Two Numbers?

This problem uses Linked List, Math, Recursion. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Add Two Numbers?

Insight 1: Use a dummy head node to simplify the creation of the result linked list, avoiding special handling for the first node. Insight 2: Keep track of the carry value from each digit addition to propagate it to the next higher digit.

Which companies ask LeetCode 2. Add Two Numbers in interviews?

This problem is frequently asked at Accenture, Adobe, Airbnb, Amazon, Apple and 30 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Add Two Numbers - LeetCode 2 Solution

Add Two Numbers - Complete Solution Guide

Add Two Numbers is LeetCode problem 2, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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],

Detailed Explanation

The problem asks us to add two numbers represented as linked lists. Each node in the linked list represents a single digit, and the digits are stored in reverse order. We need to return a new linked list representing the sum of the two numbers. For example, if l1 = [2, 4, 3] and l2 = [5, 6, 4], then l1 represents the number 342 and l2 represents the number 465. The sum 342 + 465 = 807, so we should return a linked list [7, 0, 8]. The problem emphasizes that the linked lists are non-empty and represent non-negative integers without leading zeros (except for the number 0 itself).

Solution Approach

The solution iterates through both linked lists simultaneously, adding the digits at each position along with any carry from the previous addition. A new node is created for each digit of the sum and appended to a new linked list. The iteration continues until both linked lists are exhausted and there is no remaining carry. A dummy head node is used to make adding the first node easier.

Step-by-Step Algorithm

Step 1: Initialize a dummy head node for the result linked list and a 'current' pointer to the dummy head.
Step 2: Initialize a 'carry' variable to 0.
Step 3: Iterate while either of the linked lists (l1 or l2) has more nodes or the 'carry' is greater than 0.
Step 4: In each iteration, get the values of the current nodes from l1 and l2. If a linked list is exhausted, use 0 as the value for that position.
Step 5: Calculate the sum of the two values and the 'carry'.
Step 6: Update the 'carry' by taking the integer division of the sum by 10.
Step 7: Calculate the digit to be added to the result linked list by taking the modulus of the sum by 10.
Step 8: Create a new node with the calculated digit and append it to the result linked list by setting current.next to the new node.
Step 9: Move the 'current' pointer to the newly added node.
Step 10: Advance l1 and l2 to their next nodes, or set them to null if they are exhausted.
Step 11: After the loop finishes, return the 'next' of the dummy head, which is the head of the actual result linked list.

Key Insights

Insight 1: Use a dummy head node to simplify the creation of the result linked list, avoiding special handling for the first node.
Insight 2: Keep track of the carry value from each digit addition to propagate it to the next higher digit.
Insight 3: Handle the case where one linked list is longer than the other or when there is a remaining carry after adding all digits.

Complexity Analysis

Time Complexity: O(max(m, n))

Space Complexity: O(max(m, n))

Topics

This problem involves: Linked List, Math, Recursion.

Companies

Asked at: Accenture, Adobe, Airbnb, Amazon, Apple, Avito, Bloomberg, ByteDance, Capgemini, Capital One, Cisco, Cognizant, Commvault, EPAM Systems, EarnIn, Expedia, Goldman Sachs, Google, Infosys, Intel, Meta, Microsoft, Nutanix, Nvidia, Oracle, Samsung, TikTok, Uber, Walmart Labs, Wix, Yahoo, Yandex, Zopsmart, josh technology, tcs.

Add Two Numbers | LeetCode 2

Medium

Linked List Math Recursion

Time: O(max(m, n))Space: O(max(m, n))

Solution Code

Available in:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy_head = new ListNode(0);
        ListNode current = dummy_head;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            
            int total_sum = val1 + val2 + carry;
            carry = total_sum / 10;
            int digit = total_sum % 10;
            
            current.next = new ListNode(digit);
            current = current.next;
            
            l1 = (l1 != null) ? l1.next : null;
            l2 = (l2 != null) ? l2.next : null;
            
        }
        return dummy_head.next;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2: Add Two Numbers - Detailed explanation and solution approaches.

Topics

Linked List Math Recursion

Companies

AccentureAdobeAirbnbAmazonAppleAvitoBloombergByteDance

Stats

Difficulty:Medium

Languages:4

Companies:35

Problem #:2

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

11 steps

1
Step 1: Initialize a dummy head node for the result linked list and a 'current' pointer to the dummy head.
2
Step 2: Initialize a 'carry' variable to 0.
3
Step 3: Iterate while either of the linked lists (l1 or l2) has more nodes or the 'carry' is greater than 0.
4
Step 4: In each iteration, get the values of the current nodes from l1 and l2. If a linked list is exhausted, use 0 as the value for that position.
5
Step 5: Calculate the sum of the two values and the 'carry'.
6
Step 6: Update the 'carry' by taking the integer division of the sum by 10.
7
Step 7: Calculate the digit to be added to the result linked list by taking the modulus of the sum by 10.
8
Step 8: Create a new node with the calculated digit and append it to the result linked list by setting current.next to the new node.
9
Step 9: Move the 'current' pointer to the newly added node.
10
Step 10: Advance l1 and l2 to their next nodes, or set them to null if they are exhausted.
11
Step 11: After the loop finishes, return the 'next' of the dummy head, which is the head of the actual result linked list.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(max(m, n))

💾

Space Complexity

O(max(m, n))

📝

Why?

The time complexity is determined by the while loop, which iterates until both lists are exhausted. The number of iterations is bound by the length of the longer list. The space complexity is determined by the size of the result list. The result list can be at most one node longer than the longer of the input lists (due to the carry).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Converting linked lists to integers, adding, and converting back

Convert both linked lists to integers, add them, and then convert the result back into a linked list. This is generally discouraged because large linked lists can easily overflow integer limits.

Time: O(m + n) to convert the lists + O(log(sum)) to convert back, but the conversion to and from integers may require handling large numbers or may not be possible due to integer limits.Space: O(log(sum)) to store the digits of the sum, and O(1) auxiliary space.

Trade-offs: This approach is easier to understand conceptually but is not practical due to the potential for integer overflow. The main solution is more robust for large inputs. The conversion to/from string can be used to mitigate the integer overflow risk, but then the complexities depend on the string operations.

✨

Key Insights

1Insight 1: Use a dummy head node to simplify the creation of the result linked list, avoiding special handling for the first node.
2Insight 2: Keep track of the carry value from each digit addition to propagate it to the next higher digit.
3Insight 3: Handle the case where one linked list is longer than the other or when there is a remaining carry after adding all digits.

📚

Key Terms Explained

For Students

Recursion

A function that calls itself to solve smaller versions of the same problem.

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

Edge Cases

Edge case 1: One linked list is shorter than the other. The code handles this by treating the shorter list as having a value of 0 for the missing digits.
Edge case 2: There is a carry remaining after adding all the digits. The code handles this by continuing the loop until the carry becomes 0, adding a new node with the carry value if necessary.
Edge case 3: Both input lists are empty (invalid according to the problem constraints, but the code would correctly return a list containing 0 if the initial dummy node val was kept as 0).
Edge case 4: Both input lists only contain the number 0. The solution handles this correctly, returning a linked list containing only 0.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle the carry-over value. This can lead to incorrect results, especially when the sum of two digits is 10 or more.

✗Common mistake 2: Not handling the case where one linked list is longer than the other. It's important to continue adding the remaining digits of the longer list, along with any carry.

✗Common mistake 3: Not initializing the dummy head node correctly or forgetting to return the next node of the dummy head. This can lead to incorrect or empty results.

✗Common mistake 4: Failing to handle the remaining carry after processing both lists. The while loop should continue as long as there is a carry value.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Arbitrary-precision arithmetic in cryptography or scientific computing, where numbers can exceed the limits of standard data types. This algorithm can be adapted to perform addition on these very large numbers.

🏦Real-world scenario 2: Handling large numbers in financial systems where precision is critical. Representing monetary values with linked lists could allow for calculations beyond the limits of floating-point numbers or standard integers.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The dummy node technique prevents edge cases. For cycle detection, Floyd's algorithm is the standard. Always handle empty list and single node cases.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Losing reference to nodes when modifying pointers. Use temporary variables to save references.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 3, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

❓

Frequently Asked Questions

Why use a dummy node in linked list problems?

A dummy node simplifies edge cases where the head might change (insertion/deletion at head) or when building a new list. Initialize dummy.next = head, work with dummy.next throughout, and return dummy.next at the end to handle all cases uniformly.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Add Two Numbers"?

For this medium-level Linked List problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether math techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?