What is the time complexity of Add Two Numbers II?

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

What is the space complexity of Add Two Numbers II?

The space complexity is O(n + m).

What data structures are used to solve Add Two Numbers II?

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

What are the key insights for solving Add Two Numbers II?

Insight 1: Since we need to add the numbers starting from the most significant digit, we need a way to access the digits in reverse order. Using stacks is an efficient way to achieve this without modifying the original linked lists (as suggested in the follow-up). Insight 2: We need to simulate the addition process we do manually, handling the carry-over between digits.

Which companies ask LeetCode 445. Add Two Numbers II in interviews?

This problem is frequently asked at Juniper Networks.

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

Add Two Numbers II - LeetCode 445 Solution

Add Two Numbers II - Complete Solution Guide

Add Two Numbers II is LeetCode problem 445, 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 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] Constra

Detailed Explanation

The problem requires us to add two numbers represented as linked lists where each node contains a single digit and the most significant digit comes first. We need to return the sum as a new linked list, also with the most significant digit first. We are given that there are no leading zeros, except for the number 0 itself.

Solution Approach

The provided solution uses stacks to store the values of the linked lists in reverse order. This allows us to perform the addition from the least significant digit to the most significant digit. The algorithm iterates until both stacks are empty and there is no carry left. In each iteration, it pops a value from each stack (or uses 0 if the stack is empty), calculates the sum along with any carry from the previous step, and creates a new node with the digit to be added to the result list. The new node is prepended to the result linked list to build the sum in the correct order.

Step-by-Step Algorithm

Step 1: Traverse the first linked list (l1) and push each node's value onto stack s1.
Step 2: Traverse the second linked list (l2) and push each node's value onto stack s2.
Step 3: Initialize carry to 0 and head to NULL (which will become the head of the resulting linked list).
Step 4: While either stack s1 or s2 is not empty, or there is a carry, do the following:
Step 5: Pop the top element from s1 (or 0 if s1 is empty) and assign it to val1.
Step 6: Pop the top element from s2 (or 0 if s2 is empty) and assign it to val2.
Step 7: Calculate the sum total = val1 + val2 + carry.
Step 8: Calculate the digit = total % 10 (the remainder after division by 10).
Step 9: Calculate the new carry = total // 10 (the integer part of the division by 10).
Step 10: Create a new node with the calculated digit as its value.
Step 11: Set the new node's next pointer to the current head.
Step 12: Update the head to the new node.
Step 13: After the loop finishes, return the head of the resulting linked list.

Key Insights

Insight 1: Since we need to add the numbers starting from the most significant digit, we need a way to access the digits in reverse order. Using stacks is an efficient way to achieve this without modifying the original linked lists (as suggested in the follow-up).
Insight 2: We need to simulate the addition process we do manually, handling the carry-over between digits.
Insight 3: We need to consider the case where one list is longer than the other, and also the case where there is a carry left over after processing all digits.

Complexity Analysis

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

Space Complexity: O(n + m)

Topics

This problem involves: Linked List, Math, Stack.

Companies

Asked at: Juniper Networks.

Add Two Numbers II | LeetCode 445

Medium

Linked List Math Stack

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

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; }
 * }
 */
import java.util.Stack;

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();

        while (l1 != null) {
            s1.push(l1.val);
            l1 = l1.next;
        }

        while (l2 != null) {
            s2.push(l2.val);
            l2 = l2.next;
        }

        int carry = 0;
        ListNode head = null;

        while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
            int val1 = s1.isEmpty() ? 0 : s1.pop();
            int val2 = s2.isEmpty() ? 0 : s2.pop();

            int total = val1 + val2 + carry;
            int digit = total % 10;
            carry = total / 10;

            ListNode new_node = new ListNode(digit);
            new_node.next = head;
            head = new_node;
        }

        return head;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

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

Topics

Linked List Math Stack

Companies

Juniper Networks

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:445

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

13 steps

1
Step 1: Traverse the first linked list (l1) and push each node's value onto stack s1.
2
Step 2: Traverse the second linked list (l2) and push each node's value onto stack s2.
3
Step 3: Initialize carry to 0 and head to NULL (which will become the head of the resulting linked list).
4
Step 4: While either stack s1 or s2 is not empty, or there is a carry, do the following:
5
Step 5: Pop the top element from s1 (or 0 if s1 is empty) and assign it to val1.
6
Step 6: Pop the top element from s2 (or 0 if s2 is empty) and assign it to val2.
7
Step 7: Calculate the sum total = val1 + val2 + carry.
8
Step 8: Calculate the digit = total % 10 (the remainder after division by 10).
9
Step 9: Calculate the new carry = total // 10 (the integer part of the division by 10).
10
Step 10: Create a new node with the calculated digit as its value.
11
Step 11: Set the new node's next pointer to the current head.
12
Step 12: Update the head to the new node.
13
Step 13: After the loop finishes, return the head of the resulting 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(n, m))

💾

Space Complexity

O(n + m)

📝

Why?

The time complexity is determined by the number of nodes we iterate through. Filling the stacks takes O(n + m) time. Adding the numbers also takes O(max(n, m)) time. The space complexity is determined by the storage required for the two stacks, which is proportional to the number of nodes in the input linked lists.

📖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

Reverse Linked Lists

Reverse both linked lists, then add them like in problem 2 (Add Two Numbers), and finally reverse the result.

Time: O(max(n, m))Space: O(1) (if reversing in-place, excluding result list space which is O(max(n,m)))

Trade-offs: This approach avoids using stacks, but it modifies the original linked lists (which might not be desirable) and requires reversing the linked list twice which can add overhead.

Recursive Approach

Recursively traverse to the ends of the linked lists, and then add from the back. Propagate the carry up the call stack.

Time: O(max(n,m))Space: O(max(n,m)) due to the recursion call stack

Trade-offs: This approach avoids explicit stacks but may be limited by the recursion depth in some environments and also may be less readable than the iterative approach with stacks.

✨

Key Insights

1Insight 1: Since we need to add the numbers starting from the most significant digit, we need a way to access the digits in reverse order. Using stacks is an efficient way to achieve this without modifying the original linked lists (as suggested in the follow-up).
2Insight 2: We need to simulate the addition process we do manually, handling the carry-over between digits.
3Insight 3: We need to consider the case where one list is longer than the other, and also the case where there is a carry left over after processing all digits.

📚

Key Terms Explained

For Students

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Linked List

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

Edge Cases

Edge case 1: One list is significantly longer than the other. The solution handles this correctly by using 0 as the value for the shorter list when its stack becomes empty.
Edge case 2: The sum results in a carry at the most significant digit. The solution includes the `carry` in the while loop condition, ensuring that any remaining carry is added to the result.
Edge case 3: Both lists are empty or contain only zeros. The solution handles these scenarios gracefully, returning a linked list representing zero or an empty linked list (depending on the specific requirement).
Edge case 4: Adding two large numbers results in a very long output list, close to the constraint limit of the size of lists being [1,100]. The approach still works within the allocated memory as no extra memory is created other than the stacks and new linked list.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to handle the carry-over properly, leading to incorrect sums.

✗Common mistake 2: Not handling the case where one linked list is longer than the other, resulting in incomplete sums.

✗Common mistake 3: Not accounting for a final carry, leading to a missing digit in the most significant position of the result.

✗Common mistake 4: Incorrectly linking the new nodes when constructing the result linked list, leading to incorrect order or broken lists.

✅

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: Representing and manipulating very large numbers that exceed the limits of standard data types. For example, in cryptography or scientific computations.

🏦Real-world scenario 2: Implementing arbitrary-precision arithmetic libraries, where the precision of the numbers is not limited by the hardware's word size. This is useful in financial calculations or simulations requiring high accuracy.

💡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

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

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

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

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: August 25, 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

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

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

@InterviewProJun 29

❓

Frequently Asked Questions

How does the fast/slow pointer technique work?

Fast pointer moves 2 steps while slow moves 1 step. When fast reaches the end, slow is at middle. If there's a cycle, they will meet. This technique is used for: finding middle node, detecting cycles, finding cycle start point, and checking palindromes.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

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

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?