3Sum

🎯

3Sum

mediumTWO_POINTERAmazonFacebookGoogle

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

💡 This problem asks to find all unique triplets in an array that sum to zero. Beginners often struggle because of the need to avoid duplicates and efficiently search combinations, which requires sorting and the two-pointer technique.

📋

Problem Statement

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

💡

Example

Input"nums = [-1,0,1,2,-1,-4]"

Output[[-1,-1,2],[-1,0,1]]

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

• Empty array → []
• Array with less than 3 elements → []
• All zeros → [[0,0,0]]
• No triplets sum to zero → []

⚠️

Common Mistakes

Not sorting the array before two pointers

Two pointers won't work correctly, leading to wrong or missed triplets

✅ Always sort the array before applying two pointers

Not skipping duplicates for fixed element i

Duplicate triplets appear in the output

✅ Check if nums[i] == nums[i-1] and continue to next i

Not skipping duplicates for left and right pointers

Duplicate triplets appear multiple times

✅ After finding a triplet, move pointers past duplicates

Using a set of arrays without sorting triplets first in brute force

Same triplet in different orders treated as different, causing duplicates

✅ Sort triplet before adding to set

Modifying pointers incorrectly inside loops

Infinite loops or missed triplets

✅ Carefully increment/decrement pointers and check loop conditions

🧠

Brute Force (Triple Nested Loops)

💡 Starting with brute force helps understand the problem's core: checking all triplets. Though inefficient, it builds intuition about the problem constraints and duplicate handling.

Intuition

Check every possible triplet combination and collect those that sum to zero, then remove duplicates.

Algorithm

1. Iterate over the array with index i from 0 to n-3.
2. For each i, iterate with index j from i+1 to n-2.
3. For each j, iterate with index k from j+1 to n-1.
4. Check if nums[i] + nums[j] + nums[k] == 0, if yes, add the triplet to a set to avoid duplicates.

💡 The triple nested loops are straightforward but hard to optimize without sorting or pointers.

</>

Code

from typing import List

def threeSum(nums: List[int]) -> List[List[int]]:
    n = len(nums)
    res = set()
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    triplet = tuple(sorted((nums[i], nums[j], nums[k])))
                    res.add(triplet)
    return [list(triplet) for triplet in res]

# Driver code
if __name__ == '__main__':
    print(threeSum([-1,0,1,2,-1,-4]))

Line Notes

for i in range(n):Outer loop picks the first element of the triplet

for j in range(i+1, n):Second loop picks the second element after i

for k in range(j+1, n):Third loop picks the third element after j

if nums[i] + nums[j] + nums[k] == 0:Check if the current triplet sums to zero

triplet = tuple(sorted((nums[i], nums[j], nums[k])))Sort triplet to avoid duplicates in different orders

res.add(triplet)Add triplet to a set to ensure uniqueness

return [list(triplet) for triplet in res]Convert set of tuples back to list of lists for output

import java.util.*;

public class ThreeSumBrute {
    public static List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Set<List<Integer>> res = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] == 0) {
                        List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);
                        Collections.sort(triplet);
                        res.add(triplet);
                    }
                }
            }
        }
        return new ArrayList<>(res);
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(threeSum(nums));
    }
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop selects first element

for (int j = i + 1; j < n; j++) {Second loop selects second element after i

for (int k = j + 1; k < n; k++) {Third loop selects third element after j

if (nums[i] + nums[j] + nums[k] == 0) {Check if sum of triplet is zero

List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);Create list for triplet

Collections.sort(triplet);Sort triplet to avoid duplicates in different orders

res.add(triplet);Add triplet to set to ensure uniqueness

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    int n = nums.size();
    set<vector<int>> res;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    vector<int> triplet = {nums[i], nums[j], nums[k]};
                    sort(triplet.begin(), triplet.end());
                    res.insert(triplet);
                }
            }
        }
    }
    return vector<vector<int>>(res.begin(), res.end());
}

int main() {
    vector<int> nums = {-1,0,1,2,-1,-4};
    vector<vector<int>> result = threeSum(nums);
    for (auto &triplet : result) {
        for (int num : triplet) cout << num << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

for (int i = 0; i < n; i++) {Outer loop picks first element

for (int j = i + 1; j < n; j++) {Second loop picks second element after i

for (int k = j + 1; k < n; k++) {Third loop picks third element after j

if (nums[i] + nums[j] + nums[k] == 0) {Check if sum of triplet is zero

vector<int> triplet = {nums[i], nums[j], nums[k]};Create vector for triplet

sort(triplet.begin(), triplet.end());Sort triplet to avoid duplicates in different orders

res.insert(triplet);Insert triplet into set to ensure uniqueness

function threeSum(nums) {
    const n = nums.length;
    const res = new Set();
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            for (let k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] === 0) {
                    const triplet = [nums[i], nums[j], nums[k]].sort((a,b) => a - b);
                    res.add(triplet.toString());
                }
            }
        }
    }
    return Array.from(res).map(s => s.split(',').map(Number));
}

// Test
console.log(threeSum([-1,0,1,2,-1,-4]));

Line Notes

for (let i = 0; i < n; i++) {Outer loop selects first element

for (let j = i + 1; j < n; j++) {Second loop selects second element after i

for (let k = j + 1; k < n; k++) {Third loop selects third element after j

if (nums[i] + nums[j] + nums[k] === 0) {Check if sum of triplet is zero

const triplet = [nums[i], nums[j], nums[k]].sort((a,b) => a - b);Sort triplet to avoid duplicates

res.add(triplet.toString());Add triplet as string to set to ensure uniqueness

return Array.from(res).map(s => s.split(',').map(Number));Convert set of strings back to array of arrays

⏱

Complexity

TimeO(n^3 * log3) ≈ O(n^3)

SpaceO(n^3) in worst case due to storing triplets

Three nested loops each iterate up to n, sorting triplets is constant time (3 elements), set operations add overhead but dominated by O(n^3).

💡 For n=20, this means about 8000 triplets checked, which is slow but still manageable; for n=1000, it becomes 1 billion checks, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

🧠

Sorting + Two Pointers

💡 Sorting the array allows us to use two pointers to find pairs that sum to a target efficiently, reducing complexity from cubic to quadratic.

Intuition

Fix one element and use two pointers to find pairs that sum to the negative of the fixed element, skipping duplicates to avoid repeated triplets.

Algorithm

1. Sort the input array.
2. Iterate over the array with index i from 0 to n-3.
3. Skip duplicate elements at i to avoid duplicate triplets.
4. Use two pointers, left = i+1 and right = n-1, to find pairs where nums[left] + nums[right] == -nums[i].
5. If sum is less than target, move left pointer right; if more, move right pointer left.
6. When a valid triplet is found, add it to the result and skip duplicates for left and right pointers.

💡 Sorting and skipping duplicates are key to avoid repeated triplets and reduce search space.

</>

Code

from typing import List

def threeSum(nums: List[int]) -> List[List[int]]:
    nums.sort()
    n = len(nums)
    res = []
    for i in range(n):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                res.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
    return res

# Driver code
if __name__ == '__main__':
    print(threeSum([-1,0,1,2,-1,-4]))

Line Notes

nums.sort()Sorting enables two-pointer technique and duplicate skipping

if i > 0 and nums[i] == nums[i-1]:Skip duplicate fixed elements to avoid repeated triplets

left, right = i + 1, n - 1Initialize two pointers after fixed element

while left < right:Loop to find pairs summing to target

total = nums[i] + nums[left] + nums[right]Calculate current triplet sum

if total < 0: left += 1Sum too small, move left pointer right to increase sum

elif total > 0: right -= 1Sum too large, move right pointer left to decrease sum

else:Found valid triplet

left += 1Move left pointer to next position after finding a triplet

right -= 1Move right pointer to previous position after finding a triplet

while left < right and nums[left] == nums[left - 1]: left += 1Skip duplicates for left pointer to avoid repeated triplets

while left < right and nums[right] == nums[right + 1]: right -= 1Skip duplicates for right pointer to avoid repeated triplets

import java.util.*;

public class ThreeSumTwoPointers {
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = n - 1;
            while (left < right) {
                int total = nums[i] + nums[left] + nums[right];
                if (total < 0) left++;
                else if (total > 0) right--;
                else {
                    res.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 res;
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(threeSum(nums));
    }
}

Line Notes

Arrays.sort(nums);Sort array to apply two-pointer technique

if (i > 0 && nums[i] == nums[i - 1]) continue;Skip duplicate fixed elements

int left = i + 1, right = n - 1;Initialize two pointers

while (left < right) {Loop to find pairs

int total = nums[i] + nums[left] + nums[right];Calculate sum of triplet

if (total < 0) left++;Sum too small, move left pointer right

else if (total > 0) right--;Sum too large, move right pointer left

else {Found valid triplet

left++;Move left pointer after finding a triplet

right--;Move right pointer after finding a triplet

while (left < right && nums[left] == nums[left - 1]) left++;Skip duplicates for left pointer

while (left < right && nums[right] == nums[right + 1]) right--;Skip duplicates for right pointer

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        int left = i + 1, right = n - 1;
        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];
            if (total < 0) left++;
            else if (total > 0) right--;
            else {
                res.push_back({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 res;
}

int main() {
    vector<int> nums = {-1,0,1,2,-1,-4};
    vector<vector<int>> result = threeSum(nums);
    for (auto &triplet : result) {
        for (int num : triplet) cout << num << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort array to enable two-pointer approach

if (i > 0 && nums[i] == nums[i - 1]) continue;Skip duplicate fixed elements

int left = i + 1, right = n - 1;Initialize two pointers

while (left < right) {Loop to find pairs that sum to target

int total = nums[i] + nums[left] + nums[right];Calculate current triplet sum

if (total < 0) left++;Sum too small, move left pointer right

else if (total > 0) right--;Sum too large, move right pointer left

else {Found valid triplet

left++;Move left pointer after finding a triplet

right--;Move right pointer after finding a triplet

while (left < right && nums[left] == nums[left - 1]) left++;Skip duplicates for left pointer

while (left < right && nums[right] == nums[right + 1]) right--;Skip duplicates for right pointer

function threeSum(nums) {
    nums.sort((a, b) => a - b);
    const res = [];
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let left = i + 1, right = n - 1;
        while (left < right) {
            const total = nums[i] + nums[left] + nums[right];
            if (total < 0) left++;
            else if (total > 0) right--;
            else {
                res.push([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 res;
}

// Test
console.log(threeSum([-1,0,1,2,-1,-4]));

Line Notes

nums.sort((a, b) => a - b);Sort array to apply two-pointer technique

if (i > 0 && nums[i] === nums[i - 1]) continue;Skip duplicate fixed elements

let left = i + 1, right = n - 1;Initialize two pointers

while (left < right) {Loop to find pairs

const total = nums[i] + nums[left] + nums[right];Calculate sum of triplet

if (total < 0) left++;Sum too small, move left pointer right

else if (total > 0) right--;Sum too large, move right pointer left

else {Found valid triplet

left++;Move left pointer after finding a triplet

right--;Move right pointer after finding a triplet

while (left < right && nums[left] === nums[left - 1]) left++;Skip duplicates for left pointer

while (left < right && nums[right] === nums[right + 1]) right--;Skip duplicates for right pointer

⏱

Complexity

TimeO(n^2)

SpaceO(n) or O(k) for output storage

Sorting takes O(n log n), then for each element, two pointers scan the rest in O(n), total O(n^2).

💡 For n=1000, about 1 million operations, which is efficient enough for interviews and real use.

Interview Verdict: Accepted

This is the standard efficient solution expected in interviews for 3Sum.

🧠

Hash Set Based Two Sum for Each Fixed Element

💡 Using a hash set to find pairs that sum to the target complements the fixed element, offering an alternative to two pointers but with extra space.

Intuition

Fix one element, then use a hash set to find if the complement of the current number exists to form a zero sum triplet.

Algorithm

1. Sort the array to handle duplicates easily.
2. Iterate over the array with index i from 0 to n-3.
3. Skip duplicate fixed elements.
4. For each i, create an empty hash set.
5. Iterate j from i+1 to n-1, compute complement = -nums[i] - nums[j].
6. If complement is in the set, add the triplet to result and skip duplicates.
7. Otherwise, add nums[j] to the set.

💡 Hash set lookup is O(1), but sorting is still needed to avoid duplicates.

</>

Code

from typing import List

def threeSum(nums: List[int]) -> List[List[int]]:
    nums.sort()
    n = len(nums)
    res = []
    for i in range(n):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        seen = set()
        j = i + 1
        while j < n:
            complement = -nums[i] - nums[j]
            if complement in seen:
                triplet = sorted([nums[i], complement, nums[j]])
                res.append(triplet)
                while j + 1 < n and nums[j] == nums[j + 1]:
                    j += 1
            seen.add(nums[j])
            j += 1
    return res

# Driver code
if __name__ == '__main__':
    print(threeSum([-1,0,1,2,-1,-4]))

Line Notes

nums.sort()Sort array to handle duplicates easily

if i > 0 and nums[i] == nums[i-1]:Skip duplicate fixed elements

seen = set()Hash set to store seen numbers for two sum

complement = -nums[i] - nums[j]Calculate needed complement to form zero sum

if complement in seen:Check if complement exists to form triplet

triplet = sorted([nums[i], complement, nums[j]])Sort triplet to avoid duplicates in different orders

while j + 1 < n and nums[j] == nums[j + 1]: j += 1Skip duplicates for j pointer to avoid repeated triplets

seen.add(nums[j])Add current number to seen set

j += 1Move to next element

import java.util.*;

public class ThreeSumHashSet {
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            Set<Integer> seen = new HashSet<>();
            for (int j = i + 1; j < n; j++) {
                int complement = -nums[i] - nums[j];
                if (seen.contains(complement)) {
                    List<Integer> triplet = Arrays.asList(nums[i], complement, nums[j]);
                    Collections.sort(triplet);
                    res.add(triplet);
                    while (j + 1 < n && nums[j] == nums[j + 1]) j++;
                }
                seen.add(nums[j]);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(threeSum(nums));
    }
}

Line Notes

Arrays.sort(nums);Sort array to handle duplicates

if (i > 0 && nums[i] == nums[i - 1]) continue;Skip duplicate fixed elements

Set<Integer> seen = new HashSet<>();Hash set to track seen numbers

int complement = -nums[i] - nums[j];Calculate complement needed

if (seen.contains(complement)) {Check if complement exists

List<Integer> triplet = Arrays.asList(nums[i], complement, nums[j]);Create list for triplet

Collections.sort(triplet);Sort triplet to avoid duplicates

res.add(triplet);Add triplet to result list

while (j + 1 < n && nums[j] == nums[j + 1]) j++;Skip duplicates for j pointer

seen.add(nums[j]);Add current number to seen set

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        unordered_set<int> seen;
        for (int j = i + 1; j < n; j++) {
            int complement = -nums[i] - nums[j];
            if (seen.count(complement)) {
                vector<int> triplet = {nums[i], complement, nums[j]};
                sort(triplet.begin(), triplet.end());
                res.push_back(triplet);
                while (j + 1 < n && nums[j] == nums[j + 1]) j++;
            }
            seen.insert(nums[j]);
        }
    }
    return res;
}

int main() {
    vector<int> nums = {-1,0,1,2,-1,-4};
    vector<vector<int>> result = threeSum(nums);
    for (auto &triplet : result) {
        for (int num : triplet) cout << num << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort array to handle duplicates

if (i > 0 && nums[i] == nums[i - 1]) continue;Skip duplicate fixed elements

unordered_set<int> seen;Hash set to track seen numbers

int complement = -nums[i] - nums[j];Calculate needed complement

if (seen.count(complement)) {Check if complement exists

vector<int> triplet = {nums[i], complement, nums[j]};Create vector for triplet

sort(triplet.begin(), triplet.end());Sort triplet to avoid duplicates

res.push_back(triplet);Add triplet to result

while (j + 1 < n && nums[j] == nums[j + 1]) j++;Skip duplicates for j pointer

seen.insert(nums[j]);Add current number to seen set

function threeSum(nums) {
    nums.sort((a, b) => a - b);
    const res = [];
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        const seen = new Set();
        for (let j = i + 1; j < n; j++) {
            const complement = -nums[i] - nums[j];
            if (seen.has(complement)) {
                const triplet = [nums[i], complement, nums[j]].sort((a,b) => a - b);
                res.push(triplet);
                while (j + 1 < n && nums[j] === nums[j + 1]) j++;
            }
            seen.add(nums[j]);
        }
    }
    return res;
}

// Test
console.log(threeSum([-1,0,1,2,-1,-4]));

Line Notes

nums.sort((a, b) => a - b);Sort array to handle duplicates

if (i > 0 && nums[i] === nums[i - 1]) continue;Skip duplicate fixed elements

const seen = new Set();Hash set to track seen numbers

const complement = -nums[i] - nums[j];Calculate complement needed

if (seen.has(complement)) {Check if complement exists

const triplet = [nums[i], complement, nums[j]].sort((a,b) => a - b);Sort triplet to avoid duplicates

res.push(triplet);Add triplet to result

while (j + 1 < n && nums[j] === nums[j + 1]) j++;Skip duplicates for j pointer

seen.add(nums[j]);Add current number to seen set

⏱

Complexity

TimeO(n^2)

SpaceO(n) for hash set

Sorting is O(n log n), for each element we scan the rest with hash set lookups O(1), total O(n^2).

💡 This approach uses extra space but is still efficient for large inputs.

Interview Verdict: Accepted

This approach is a valid alternative to two pointers, especially if the array is not sorted or if interviewer prefers hash sets.

📊

All Approaches - One-Glance Tradeoffs

💡 The two pointers approach is the best balance of efficiency and simplicity for 3Sum and should be your go-to in interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^3)	O(n^3) for storing triplets	No	Yes	Mention only - never code
2. Sorting + Two Pointers	O(n^2)	O(k) output space	No	Yes	Code this approach
3. Hash Set Based Two Sum	O(n^2)	O(n) extra space	No	Yes	Mention as alternative

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs and edge cases clearly.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem.Introduce sorting and two pointers to optimize the solution.Discuss alternative hash set approach if asked.Write clean, bug-free code and test with edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize, handle duplicates, and write clean code with correct edge case handling.

Common Follow-ups

• What if the array is not sorted? → Use hash set approach.
• How to handle duplicates efficiently? → Sort and skip duplicates.
• Can this be extended to 4Sum? → Yes, fix two elements and use two pointers.
• What is the time complexity? → O(n^2) is optimal for 3Sum.

💡 These follow-ups test your depth of understanding and ability to adapt solutions.

🔍

Pattern Recognition

When to Use

1) Asked to find triplets summing to a target (often zero). 2) Need to avoid duplicates. 3) Input array can be sorted. 4) Two-pointer technique applicable.

Signature Phrases

find all unique tripletssum to zerono duplicate triplets

NOT This Pattern When

Problems asking for closest sum or count of pairs without uniqueness constraints

Similar Problems

4Sum - extends 3Sum by fixing two elements and using two pointersTwo Sum - simpler version with pairs instead of triplets

Practice

1. You are given a string and need to determine if it reads the same forwards and backwards, ignoring case and non-alphanumeric characters. Which approach guarantees an optimal O(n) time and O(n) space solution for this problem?

easy

A. Reverse the original string and compare it directly to the input string without any preprocessing.

B. Use dynamic programming to check all substrings for palindrome properties.

C. Use a greedy approach to skip characters that don't match and try to fix mismatches on the fly.

D. Preprocess the string by removing non-alphanumeric characters and converting to lowercase, then use two pointers from opposite ends to compare characters.

Solution

1. Step 1: Understand problem constraints

   The problem requires ignoring case and non-alphanumeric characters, so direct comparison or naive reversal won't work correctly.

2. Step 2: Identify approach that handles preprocessing and efficient comparison

   Preprocessing to clean the string and then using two pointers from opposite ends ensures O(n) time and space, and correctly handles all cases.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Preprocessing + two pointers is standard for palindrome checks ignoring punctuation [OK]

Hint: Preprocess then two pointers is optimal palindrome check [OK]

Common Mistakes:

• Trying to compare original string directly without cleaning
• Using DP which is overkill and slower
• Greedy skipping mismatches leads to incorrect results

2. The following code attempts to implement the optimal two-pointer forward approach for backspace string compare. Which line contains a subtle bug that causes incorrect results on inputs starting with backspaces?

medium

A. Line 2: write = 0

B. Line 7: elif write >= 0:

C. Line 9: return ''.join(arr[:write])

D. Line 5: if arr[read] != '#':

Solution

1. Step 1: Analyze the condition for backspace handling

   The condition 'elif write >= 0' allows write to decrement even when write is 0, causing write to become -1, which is invalid and leads to incorrect string reconstruction.

2. Step 2: Correct condition

   The condition should be 'elif write > 0' to prevent write from going negative and ensure backspaces at the start are handled safely.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   write pointer must not go below zero [OK]

Hint: write must stay >= 0; decrement only if write > 0 [OK]

Common Mistakes:

• Allowing write to become negative on backspace
• Returning arr[:write] without checking write validity
• Misplacing the backspace condition

3. The following code attempts to count pairs with absolute difference at most K using binary search. Identify the line containing the subtle bug that causes incorrect counting for some inputs.

import bisect

def count_pairs_buggy(nums, K):
    count = 0
    n = len(nums)
    for i in range(n - 1):
        target = nums[i] + K
        j = bisect.bisect_right(nums, target, i) - 1
        if j > i:
            count += j - i
    return count

medium

A. Line 5: for i in range(n - 1):

B. Line 7: target = nums[i] + K

C. Line 8: j = bisect.bisect_right(nums, target, i) - 1

D. Line 9: if j > i:

Solution

1. Step 1: Understand bisect_right usage

   bisect_right should start searching from i + 1 to avoid counting pairs where j ≤ i.

2. Step 2: Identify bug in line 8

   Using i as the start index includes nums[i] itself, causing pairs with i == j or double counting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing i to i + 1 fixes the bug [OK]

Hint: bisect must start from i+1 to avoid invalid pairs [OK]

Common Mistakes:

• Starting binary search at i instead of i+1
• Off-by-one errors in bisect indices
• Counting pairs where i >= j

4. The following code attempts to reverse a list of characters in-place using recursion. Identify the line that contains a subtle bug that could cause incorrect behavior or runtime error.

def reverseString(s):
    def helper(left, right):
        if left > right:
            return
        s[left], s[right] = s[right], s[left]
        helper(left + 1, right - 1)

if __name__ == "__main__":
    s = ['r','a','c','e','c','a','r']
    reverseString(s)
    print(s)

medium

A. Line 7: The initial call to helper is missing and should be added.

B. Line 4: The swap operation overwrites characters incorrectly without a temporary variable.

C. Line 5: The recursive call should increment both pointers by 1 instead of incrementing left and decrementing right.

D. Line 3: The base case condition should be 'left >= right' instead of 'left > right'.

Solution

1. Step 1: Examine base case condition

   The base case uses 'if left > right', but when left == right (middle element), swap should stop to avoid redundant swap or index errors.

2. Step 2: Correct base case

   Changing condition to 'left >= right' ensures recursion stops correctly when pointers meet or cross.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Base case off-by-one causes incorrect or extra swaps [OK]

Hint: Base case must include equality to avoid extra swaps [OK]

Common Mistakes:

• Off-by-one in base case
• Assuming swap needs temp variable in Python
• Incorrect pointer increments

5. Suppose the problem is modified so that you can reuse the same line multiple times to form containers (i.e., pairs can include the same index twice). Which of the following statements about adapting the two-pointer approach is correct?

hard

A. The two-pointer approach still works without changes because pointers can point to the same index.

B. The problem reduces to finding the maximum height line squared, so just return height[i] * 0 for some i.

C. A new approach is needed because the two-pointer method relies on distinct indices and cannot handle reuse.

D. You must switch to a brute force approach checking all pairs including identical indices to handle reuse.

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means pairs can be (i, i), which the original two-pointer approach does not consider.

2. Step 2: Analyze two-pointer limitations

   The two-pointer method relies on distinct indices moving inward; it cannot handle pairs with the same index, so it must be modified or replaced.

3. Step 3: Evaluate options

   Brute force can handle reuse but is inefficient; simply returning height[i]*0 is incorrect; two-pointer without changes fails.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Two-pointer requires distinct indices -> reuse breaks original approach [OK]

Hint: Two-pointer needs distinct indices; reuse breaks this assumption [OK]

Common Mistakes:

• Assuming two-pointer works unchanged
• Ignoring reuse pairs with same index
• Thinking reuse reduces problem complexity