What is the time complexity of 3Sum?

The optimal solution has a time complexity of O(n^2).

What data structures are used to solve 3Sum?

This problem uses Array, Two Pointers, Sorting. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving 3Sum?

Insight 1: Sorting the input array enables the use of the two-pointer technique to efficiently find pairs that sum to a specific target value. Insight 2: Skipping duplicate numbers after sorting is crucial to avoid including duplicate triplets in the final result. This is done by checking for equality with the previous element.

Which companies ask LeetCode 15. 3Sum in interviews?

This problem is frequently asked at AMD, Accenture, Adobe, Agoda, Altimetrik and 59 more companies.

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

3Sum - LeetCode 15 Solution

3Sum - Complete Solution Guide

3Sum is LeetCode problem 15, 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

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j , i != k , and j != k , and nums[i] + nums[j] + nums[k] == 0 . Notice that the solution set must not contain duplicate triplets. Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1

Detailed Explanation

The 3Sum problem requires us to find all unique triplets (sets of three numbers) within a given array of integers that sum up to zero. The triplets must consist of three distinct elements from the array, meaning the indices of the three numbers must be different. The solution should return a list of these unique triplets. Duplicate triplets should not be included in the result.

Solution Approach

The solution uses a combination of sorting and the two-pointer technique to efficiently find the triplets. First, the input array is sorted in ascending order. This allows for a linear traversal of the array, with two pointers (left and right) positioned to find the remaining two numbers that, when combined with the current element, sum to zero. After sorting, the algorithm iterates through the array. For each element, two pointers are initialized: 'left' starts at the next element after the current element, and 'right' starts at the end of the array. The algorithm then moves the left and right pointers towards each other, adjusting their positions based on whether the current sum is less than, greater than, or equal to zero. Duplicate triplets are avoided by skipping over duplicate numbers while moving the pointers.

Step-by-Step Algorithm

Step 1: Sort the input array `nums` in ascending order.
Step 2: Iterate through the sorted array from index `i = 0` to `n - 2`, where `n` is the length of the array.
Step 3: Inside the outer loop, check if the current number `nums[i]` is greater than 0. If it is, break the loop because all subsequent numbers will also be positive, making it impossible to find a triplet that sums to zero.
Step 4: Check for duplicate numbers for `nums[i]`. If `i > 0` and `nums[i] == nums[i - 1]`, skip the current iteration to avoid duplicate triplets.
Step 5: Initialize two pointers: `left = i + 1` and `right = n - 1`.
Step 6: While `left < right`, calculate the current sum `current_sum = nums[i] + nums[left] + nums[right]`.
Step 7: If `current_sum < 0`, increment the `left` pointer to increase the sum.
Step 8: If `current_sum > 0`, decrement the `right` pointer to decrease the sum.
Step 9: If `current_sum == 0`, add the triplet `[nums[i], nums[left], nums[right]]` to the result list.
Step 10: Increment `left` and decrement `right` to find other possible triplets. Also skip duplicate numbers for `left` and `right` pointers to avoid duplicate triplets.
Step 11: Repeat steps 6-10 until `left >= right`.
Step 12: Return the list of unique triplets.

Key Insights

Insight 1: Sorting the input array enables the use of the two-pointer technique to efficiently find pairs that sum to a specific target value.
Insight 2: Skipping duplicate numbers after sorting is crucial to avoid including duplicate triplets in the final result. This is done by checking for equality with the previous element.
Insight 3: The first number in the triplet can determine when to stop searching. If it is greater than zero, there's no possibility of finding a triplet that sums to zero because the array is sorted.

Complexity Analysis

Time Complexity: O(n^2)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers, Sorting.

Companies

Asked at: AMD, Accenture, Adobe, Agoda, Altimetrik, Amazon, American Express, Apple, Atlassian, Autodesk, BNY Mellon, Barclays, Bloomberg, Bosch, Cadence, Careem, Cisco, Citadel, Cloudflare, Cognizant, Docusign, Dream11, EPAM Systems, Flipkart, Gojek, Goldman Sachs, HCL, HashedIn, Infosys, Intuit, Meta, Microsoft, Morgan Stanley, Myntra, Nutanix, Nvidia, Oracle, PayPal, Paytm, Rakuten, Salesforce, Samsung, ServiceNow, Siemens, Sprinklr, Tesla, TikTok, Trexquant, Turing, Uber, Vimeo, Visa, Walmart Labs, Warnermedia, Wells Fargo, Wix, Works Applications, Yahoo, Yandex, Zoho, Zomato, Zopsmart, smartnews, tcs.

3Sum | LeetCode 15

Medium

Array Two Pointers Sorting

Time: O(n^2)Space: O(1)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            if (nums[i] > 0) {
                break;
            }

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = n - 1;

            while (left < right) {
                int current_sum = nums[i] + nums[left] + nums[right];

                if (current_sum < 0) {
                    left++;
                } else if (current_sum > 0) {
                    right--;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    left++;
                    right--;

                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }

                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }

        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 15: 3Sum - Detailed explanation and solution approaches.

Topics

Array Two Pointers Sorting

Companies

AMDAccentureAdobeAgodaAltimetrikAmazonAmerican ExpressApple

Stats

Difficulty:Medium

Languages:4

Companies:64

Problem #:15

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

12 steps

1
Step 1: Sort the input array `nums` in ascending order.
2
Step 2: Iterate through the sorted array from index `i = 0` to `n - 2`, where `n` is the length of the array.
3
Step 3: Inside the outer loop, check if the current number `nums[i]` is greater than 0. If it is, break the loop because all subsequent numbers will also be positive, making it impossible to find a triplet that sums to zero.
4
Step 4: Check for duplicate numbers for `nums[i]`. If `i > 0` and `nums[i] == nums[i - 1]`, skip the current iteration to avoid duplicate triplets.
5
Step 5: Initialize two pointers: `left = i + 1` and `right = n - 1`.
6
Step 6: While `left < right`, calculate the current sum `current_sum = nums[i] + nums[left] + nums[right]`.
7
Step 7: If `current_sum < 0`, increment the `left` pointer to increase the sum.
8
Step 8: If `current_sum > 0`, decrement the `right` pointer to decrease the sum.
9
Step 9: If `current_sum == 0`, add the triplet `[nums[i], nums[left], nums[right]]` to the result list.
10
Step 10: Increment `left` and decrement `right` to find other possible triplets. Also skip duplicate numbers for `left` and `right` pointers to avoid duplicate triplets.
11
Step 11: Repeat steps 6-10 until `left >= right`.
12
Step 12: Return the list of unique triplets.

💡

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(n^2)

🐢 Quadratic - Gets slow with large inputs. Consider optimization!

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is dominated by the nested loops. The outer loop iterates `n` times, and the inner while loop (two-pointer technique) takes O(n) time in the worst case. Sorting the array takes O(n log n) time, but it's dominated by the O(n^2) complexity of the nested loops. The space complexity is O(1) because the algorithm primarily uses a fixed amount of extra space for pointers and temporary variables. The space used for the output list is typically not considered in the space complexity analysis, as the problem statement dictates that the output list must be created.

📖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

Hash Map Approach

Use a hash map to store the frequency of each number in the array. Then, iterate through all possible pairs of numbers and check if the negative sum of the pair exists in the hash map. This approach is conceptually simpler but can be less efficient in practice.

Time: O(n^2) on average, O(n^3) in worst-case if hash collisions are numerous.Space: O(n)

Trade-offs: The hash map approach might be easier to implement initially, but its space complexity is higher, and its performance can be worse than the sorting and two-pointer approach, especially when the input array is large. The sorting approach is generally preferred due to its better space complexity and comparable time complexity. Moreover, it does not perform well when collision rate is too high.

✨

Key Insights

1Insight 1: Sorting the input array enables the use of the two-pointer technique to efficiently find pairs that sum to a specific target value.
2Insight 2: Skipping duplicate numbers after sorting is crucial to avoid including duplicate triplets in the final result. This is done by checking for equality with the previous element.
3Insight 3: The first number in the triplet can determine when to stop searching. If it is greater than zero, there's no possibility of finding a triplet that sums to zero because the array is sorted.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: Input array with all zeros (e.g., `[0, 0, 0]`). The solution correctly identifies `[0, 0, 0]` as a valid triplet.
Edge case 2: Input array with no possible triplets that sum to zero (e.g., `[1, 2, 3]`). The solution correctly returns an empty list.
Edge case 3: Input array with duplicate numbers (e.g., `[-1, 0, 1, 2, -1, -4]`). The solution correctly handles duplicates by skipping them with the additional while loops, ensuring only unique triplets are added to the result.
Edge case 4: An input array which is too short, less than 3 elements. While the constraint enforces array size greater than equal to 3, a defensive check for smaller arrays would not go amiss (but also is not explicitly required, the presented code handles cases with size less than 3 by returning an empty result)

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Failing to sort the input array. The two-pointer technique relies on the array being sorted to work correctly.

✗Common mistake 2: Not handling duplicate numbers, leading to duplicate triplets in the result. The extra while loops to skip duplicate numbers are essential.

✗Common mistake 3: Not checking the base cases. If the array has size less than 3, no triplet can exist.

✗Common mistake 4: Assuming all possible triplets can be formed, not checking if the sum equals zero. This leads to incorrect or incomplete results.

✅

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: Financial analysis, where finding combinations of assets that balance each other out (sum to zero or a target value) is important for risk management.

🏦Real-world scenario 2: Image processing, where identifying pixel combinations with specific color properties (e.g., summing to a particular color value) is used in image recognition or filtering.

💡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

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 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: June 16, 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

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

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 "3Sum"?

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

🤖 Need help with this problem?