3Sum

📋

Problem

Imagine you are analyzing financial transactions and want to find all unique triplets of expenses that sum to zero, helping detect suspicious patterns.

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. The solution set must not contain duplicate triplets.

1 ≤ nums.length ≤ 10^5-10^5 ≤ nums[i] ≤ 10^5

Edge cases: Empty array → []Array with less than 3 elements → []All zeros → [[0,0,0]]

</>

IDE

def threeSum(nums: list[int]) -> list[list[int]]:public List<List<Integer>> threeSum(int[] nums)vector<vector<int>> threeSum(vector<int>& nums)function threeSum(nums)

def threeSum(nums):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    // Write your solution here
    return {};
}

function threeSum(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [[-1,0,1]]Stops after finding first valid triplet, missing others.✅ Continue searching after finding a triplet; do not return early.

Wrong: [[0,0,0],[0,0,0]]Fails to skip duplicate triplets properly.✅ Skip duplicates for fixed and pointer elements after adding triplet.

Wrong: [[-1,-1,2],[-1,0,1],[-1,-1,2]]Does not remove duplicate triplets due to missing sorting or duplicate checks.✅ Sort triplets before adding and skip duplicates in loops.

Wrong: [[-2,0,2]]Misses some valid triplets due to incorrect pointer movement or duplicate skipping.✅ Adjust pointers correctly and skip duplicates only after adding triplet.

Wrong: Timeout or no outputUsing brute force triple nested loops for large input.✅ Implement sorting + two pointers approach with O(n^2) time complexity.

✓

Test Cases

Handle empty and very small arrays carefully to avoid errors.

Focus on duplicate skipping and finding all triplets, not just one.

Optimize your solution to O(n^2) time complexity using sorting and two pointers.

t1_01basic

Input{"nums":[-1,0,1,2,-1,-4]}

Expected[[-1,-1,2],[-1,0,1]]

⏱ Performance - must finish in 2000ms

After sorting, the array is [-4,-1,-1,0,1,2]. The triplets that sum to zero are [-1,-1,2] and [-1,0,1].

💡 Sort the array first to use two pointers effectively.

💡 Use a fixed pointer and two pointers to find pairs summing to the negative of fixed element.

💡 Skip duplicates for fixed and pointer elements to avoid duplicate triplets.

Why it failed: Failed basic case: likely missing sorting or duplicate skipping. Fix by sorting input and skipping duplicates in loops.

✓ Correctly finds all unique triplets summing to zero.

t1_02basic

Input{"nums":[0,1,1]}

Expected[]

⏱ Performance - must finish in 2000ms

No triplets possible since array length is 3 but no three elements sum to zero.

💡 Check if array length is less than 3, return empty early.

💡 Even with 3 elements, verify sum equals zero before adding triplet.

💡 Ensure no false positives when no valid triplets exist.

Why it failed: Incorrect output: likely not handling small arrays or sum checks properly. Fix by verifying length and sum conditions.

✓ Correctly returns empty list when no triplets sum to zero.

t2_01edge

Input{"nums":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input array returns empty list as no triplets exist.

💡 Handle empty input by returning empty list immediately.

💡 Check array length before processing to avoid errors.

💡 Return [] if nums length < 3.

Why it failed: Fails empty input: likely no length check causing errors or wrong output. Fix by returning [] if length < 3.

✓ Correctly handles empty input by returning empty list.

t2_02edge

Input{"nums":[0]}

Expected[]

⏱ Performance - must finish in 2000ms

Single element array cannot form triplets, so output is empty.

💡 Check if array length is less than 3 and return empty list.

💡 Avoid processing when insufficient elements for triplets.

💡 Return [] for arrays with fewer than 3 elements.

Why it failed: Fails single element input: likely missing length check. Fix by returning [] if length < 3.

✓ Correctly returns empty list for single element input.

t2_03edge

Input{"nums":[0,0,0]}

Expected[[0,0,0]]

⏱ Performance - must finish in 2000ms

All zeros form one valid triplet summing to zero.

💡 Check for duplicates and allow triplets with repeated elements if valid.

💡 After sorting, identical elements can form valid triplets.

💡 Ensure duplicate triplets are not repeated in output.

Why it failed: Fails all zeros case: likely skipping duplicates too aggressively or missing triplet with identical elements. Fix by allowing triplet if sum is zero and skipping duplicates only after adding.

✓ Correctly identifies triplet [0,0,0] without duplicates.

t3_01corner

Input{"nums":[-2,0,1,1,2]}

Expected[[-2,0,2],[-2,1,1]]

⏱ Performance - must finish in 2000ms

Triplets include [-2,0,2] and [-2,1,1]. Tests correct handling of duplicates and multiple valid triplets.

💡 Sort array and use two pointers to find pairs for each fixed element.

💡 Skip duplicates for fixed and pointer elements to avoid repeated triplets.

💡 Check sums carefully and move pointers accordingly.

Why it failed: Fails to find all triplets or includes duplicates: likely missing duplicate skipping or incorrect pointer movement. Fix by skipping duplicates after adding triplet and adjusting pointers properly.

✓ Correctly finds all unique triplets including duplicates in input.

t3_02corner

Input{"nums":[-1,0,1,2,-1,-4,-2,-3,3,0,4]}

Expected[[-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]

⏱ Performance - must finish in 2000ms

Complex input with multiple triplets tests correct handling of multiple duplicates and negative/positive values.

💡 Sort input and iterate with two pointers for each fixed element.

💡 Skip duplicates for fixed and pointer elements to avoid repeated triplets.

💡 Carefully move pointers based on sum comparison to zero.

Why it failed: Fails complex case: likely incorrect duplicate handling or pointer logic. Fix by skipping duplicates and adjusting pointers correctly after each found triplet.

✓ Correctly finds all unique triplets in complex input.

t3_03corner

Input{"nums":[-1,0,1,2,-1,-4]}

Expected[[-1,-1,2],[-1,0,1]]

⏱ Performance - must finish in 2000ms

Tests greedy trap: picking first valid triplet only misses others.

💡 Do not stop after finding first triplet; continue searching for others.

💡 Use two pointers to find all pairs for each fixed element.

💡 Skip duplicates but continue scanning to find all valid triplets.

Why it failed: Fails greedy trap: returns incomplete triplets list. Fix by continuing search after finding a triplet instead of returning early.

✓ Correctly finds all triplets, not just first.

t4_01performance

Input{"nums":[-100000,-99999,-99998,-99997,-99996,-99995,-99994,-99993,-99992,-99991,-99990,-99989,-99988,-99987,-99986,-99985,-99984,-99983,-99982,-99981,-99980,-99979,-99978,-99977,-99976,-99975,-99974,-99973,-99972,-99971,-99970,-99969,-99968,-99967,-99966,-99965,-99964,-99963,-99962,-99961,-99960,-99959,-99958,-99957,-99956,-99955,-99954,-99953,-99952,-99951,-99950,-99949,-99948,-99947,-99946,-99945,-99944,-99943,-99942,-99941,-99940,-99939,-99938,-99937,-99936,-99935,-99934,-99933,-99932,-99931,-99930,-99929,-99928,-99927,-99926,-99925,-99924,-99923,-99922,-99921,-99920,-99919,-99918,-99917,-99916,-99915,-99914,-99913,-99912,-99911,-99910,-99909,-99908,-99907,-99906,-99905,-99904,-99903,-99902,-99901]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 tests O(n^2) time complexity; brute force O(n^3) would time out.

💡 Sorting + two pointers approach runs in O(n^2) time.

💡 Brute force triple nested loops O(n^3) will time out for n=100.

💡 Optimize by skipping duplicates and using two pointers after sorting.

Why it failed: TLE due to O(n^3) brute force approach; fix by implementing O(n^2) two pointers after sorting.

✓ Efficient O(n^2) solution passes within time limit.

Practice

1. You are given an array representing heights of vertical lines on the x-axis. You want to find two lines that together with the x-axis form a container, such that the container holds the maximum amount of water. Which algorithmic approach guarantees finding the optimal solution in O(n) time?

easy

A. Two pointers starting at opposite ends, moving the pointer at the shorter line inward.

B. Brute force by checking all pairs of lines and calculating their container area.

C. Dynamic programming to store maximum areas for subproblems of line pairs.

D. Greedy approach moving the pointer at the taller line inward to maximize area.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding two lines that maximize the container area, which depends on the minimum height and the distance between lines.

2. Step 2: Analyze algorithmic approaches

   Brute force (checking all pairs) is O(n²), dynamic programming is unnecessary and inefficient here, and moving the pointer at the taller line can miss optimal solutions. The two-pointer approach moving the pointer at the shorter line inward guarantees checking all promising pairs efficiently in O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer approach with shorter line pointer movement -> O(n) optimal [OK]

Hint: Two pointers move inward from ends, shorter line pointer moves [OK]

Common Mistakes:

• Moving pointer at taller line instead of shorter line
• Using DP unnecessarily
• Assuming greedy on taller line pointer works

2. You are given an array of integers and need to reorder it so that all even numbers appear before all odd numbers. Which algorithmic approach guarantees an optimal in-place solution with O(n) time and O(1) space complexity?

easy

A. Using a two-pointer technique that partitions the array in a single pass by swapping elements

B. Using dynamic programming to track even and odd counts and reorder accordingly

C. Sorting the array using a comparison-based sort and then grouping evens and odds

D. Using a brute force approach by creating two separate arrays for evens and odds and concatenating them

Solution

1. Step 1: Understand the problem constraints

   The problem requires reordering the array so that evens come before odds, ideally in-place and efficiently.

2. Step 2: Identify the optimal approach

   The two-pointer technique allows scanning the array once, swapping evens to the front, achieving O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer partitioning is classic for in-place parity partitioning [OK]

Hint: Two-pointer partitioning solves in-place parity grouping [OK]

Common Mistakes:

• Assuming sorting is needed for parity grouping
• Thinking DP applies to simple partitioning
• Believing extra arrays are optimal for in-place constraints

3. Consider the following Python code for squaring and sorting an array in-place:

def sortedSquares(nums):
    for i in range(len(nums)):
        nums[i] = nums[i] * nums[i]
    nums.sort()
    return nums

nums = [-3, 0, 2]
print(sortedSquares(nums))

What is the output of this code?

easy

A. [9, 4, 0]

B. [9, 0, 4]

C. [0, 4, 9]

D. [4, 0, 9]

Solution

1. Step 1: Square each element

   nums becomes [9, 0, 4] after squaring -3, 0, and 2 respectively.

2. Step 2: Sort the squared array

   Sorting [9, 0, 4] results in [0, 4, 9].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Squares then sort yields sorted squares [OK]

Hint: Square then sort yields sorted squares [OK]

Common Mistakes:

• Forgetting to sort after squaring
• Mixing up order of squared elements
• Off-by-one errors in indexing

4. Suppose the problem changes so that elements can be reused multiple times in triplets (i.e., indices can repeat). Which modification to the two-pointer approach correctly counts the number of triplets with sum less than target?

hard

A. Keep the same two-pointer approach but allow left and right pointers to be equal and count accordingly.

B. Use three nested loops to consider all triplets with possible repeated indices.

C. Sort the array and for each i, use two pointers starting at i to allow reuse, adjusting counting logic accordingly.

D. Sort the array and for each i, use a single pointer to count pairs with sum less than target minus nums[i], allowing reuse.

Solution

1. Step 1: Understand reuse of elements

   Allowing repeated indices means pairs can include the same element multiple times, so two-pointer approach must adapt.

2. Step 2: Adjust approach for reuse

   Using a single pointer to count pairs with sum less than target - nums[i] allows counting with reuse, since two pointers crossing is no longer valid.

3. Step 3: Why other options fail

   Allowing left == right breaks two-pointer logic (A). Three nested loops (B) is correct but inefficient. Starting two pointers at i (C) is incorrect because it counts invalid pairs.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Single pointer counting with reuse is correct and efficient [OK]

Hint: Reuse requires counting pairs with single pointer or adjusted logic [OK]

Common Mistakes:

• Allowing pointers to cross causing invalid counts
• Using naive triple loops ignoring efficiency
• Starting two pointers incorrectly leading to missed counts

5. Suppose the input array can contain negative integers and zeros, and you want to partition the array so that all even numbers (including negative evens and zero) come before all odd numbers. Which modification to the original two-pointer algorithm is necessary to handle this correctly?

hard

A. Change the parity check to use abs(nums[i]) % 2 == 0 to handle negative numbers

B. Use a sorting-based approach since parity is ambiguous with negative numbers

C. No change needed; the original parity check nums[i] % 2 == 0 works correctly for negatives and zero

D. Add a separate pass to move zeros to the front before partitioning evens and odds

Solution

1. Step 1: Understand parity with negatives and zero

   In Python, num % 2 == 0 correctly identifies even numbers including negatives and zero.

2. Step 2: Confirm no algorithm change needed

   The original two-pointer approach works unchanged since parity check is valid for all integers.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Modulo operator handles negative evens and zero correctly [OK]

Hint: Modulo operator works for negative evens and zero [OK]

Common Mistakes:

• Thinking abs() is needed for parity check
• Assuming zeros need special handling
• Believing sorting is required for negatives