3Sum Closest

🎯

3Sum Closest

mediumTWO_POINTERAmazonGoogle

Imagine you are planning a group trip and want to pick three activities whose total cost is as close as possible to your budget without going over.

💡 This problem asks you to find three numbers in an array whose sum is closest to a target value. Beginners often struggle because the naive approach involves checking all triplets, which is inefficient. Understanding how to reduce the search space using sorting and two pointers is key.

📋

Problem Statement

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

3 ≤ n ≤ 10^5-10^4 ≤ nums[i] ≤ 10^4-10^5 ≤ target ≤ 10^5

💡

Example

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

Output2

The sum that is closest to the target is 2 (-1 + 2 + 1 = 2).

• All elements are the same → sum is triple that element
• Array contains negative and positive numbers → closest sum may cross zero
• Target is smaller than any possible sum → closest sum is minimum triple sum
• Target is larger than any possible sum → closest sum is maximum triple sum

⚠️

Common Mistakes

Not sorting the array before applying two pointers

Two-pointer approach fails because pointers rely on sorted order

✅ Always sort the array before using two pointers

Not updating closest sum correctly when a closer sum is found

Returns incorrect or suboptimal sum

✅ Compare absolute differences and update closest sum accordingly

Forgetting to move pointers after checking sums

Infinite loop or incorrect results

✅ Move left pointer if sum < target, right pointer if sum > target

Not handling the case when current sum equals target

Miss opportunity to return early and optimize

✅ Return immediately when exact match is found

Using incorrect loop boundaries causing index errors

Runtime errors or missing valid triplets

✅ Ensure loops run only until n-2 for i, and pointers are within valid range

🧠

Brute Force (Triple Nested Loops)

💡 Starting with brute force helps understand the problem deeply by exploring all possible triplets, even though it's inefficient. It lays the foundation for optimization.

Intuition

Check every possible combination of three numbers and track the sum closest to the target.

Algorithm

1. Initialize a variable to store the closest sum found so far.
2. Use three nested loops to iterate over all triplets in the array.
3. Calculate the sum of the current triplet.
4. Update the closest sum if the current sum is closer to the target.

💡 The triple nested loops are straightforward but can be overwhelming due to the number of iterations; understanding this helps appreciate the need for better methods.

</>

Code

def threeSumClosest(nums, target):
    n = len(nums)
    closest_sum = float('inf')
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                current_sum = nums[i] + nums[j] + nums[k]
                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum
    return closest_sum

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

Line Notes

n = len(nums)Determine the size of the input array for loop boundaries

closest_sum = float('inf')Initialize closest sum to infinity to ensure any sum will be closer initially

for i in range(n - 2)First pointer to pick the first element of the triplet

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

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

current_sum = nums[i] + nums[j] + nums[k]Calculate the sum of the current triplet

if abs(current_sum - target) < abs(closest_sum - target)Check if current sum is closer to target than previous closest

closest_sum = current_sumUpdate closest sum to the current sum

import java.util.*;
public class ThreeSumClosest {
    public static int threeSumClosest(int[] nums, int target) {
        int n = nums.length;
        int closestSum = Integer.MAX_VALUE / 2; // to avoid overflow
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    int currentSum = nums[i] + nums[j] + nums[k];
                    if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                        closestSum = currentSum;
                    }
                }
            }
        }
        return closestSum;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 2, 1, -4};
        int target = 1;
        System.out.println(threeSumClosest(nums, target)); // Output: 2
    }
}

Line Notes

int n = nums.length;Get array length for loop limits

int closestSum = Integer.MAX_VALUE / 2;Initialize closest sum to a large number safely to avoid overflow

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

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

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

int currentSum = nums[i] + nums[j] + nums[k];Calculate sum of current triplet

if (Math.abs(currentSum - target) < Math.abs(closestSum - target))Check if current sum is closer to target

closestSum = currentSum;Update closest sum

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int threeSumClosest(vector<int>& nums, int target) {
    int n = nums.size();
    int closestSum = INT_MAX / 2; // avoid overflow
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                int currentSum = nums[i] + nums[j] + nums[k];
                if (abs(currentSum - target) < abs(closestSum - target)) {
                    closestSum = currentSum;
                }
            }
        }
    }
    return closestSum;
}

int main() {
    vector<int> nums = {-1, 2, 1, -4};
    int target = 1;
    cout << threeSumClosest(nums, target) << endl; // Output: 2
    return 0;
}

Line Notes

int n = nums.size();Get the size of the input vector

int closestSum = INT_MAX / 2;Initialize closest sum to a large number safely

for (int i = 0; i < n - 2; i++)First loop picks first element

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

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

int currentSum = nums[i] + nums[j] + nums[k];Calculate sum of current triplet

if (abs(currentSum - target) < abs(closestSum - target))Check if current sum is closer to target

closestSum = currentSum;Update closest sum

function threeSumClosest(nums, target) {
    const n = nums.length;
    let closestSum = Infinity;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                const currentSum = nums[i] + nums[j] + nums[k];
                if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                    closestSum = currentSum;
                }
            }
        }
    }
    return closestSum;
}

// Test
console.log(threeSumClosest([-1, 2, 1, -4], 1)); // Output: 2

Line Notes

const n = nums.length;Get array length for loop boundaries

let closestSum = Infinity;Initialize closest sum to infinity for comparison

for (let i = 0; i < n - 2; i++)First pointer picks first element

for (let j = i + 1; j < n - 1; j++)Second pointer picks second element after i

for (let k = j + 1; k < n; k++)Third pointer picks third element after j

const currentSum = nums[i] + nums[j] + nums[k];Calculate sum of current triplet

if (Math.abs(currentSum - target) < Math.abs(closestSum - target))Check if current sum is closer to target

closestSum = currentSum;Update closest sum

⏱

Complexity

TimeO(n^3)

SpaceO(1)

Three nested loops each iterate up to n, resulting in cubic time complexity. No extra space besides variables.

💡 For n=20, this means 20*19*18 = 6840 operations, which is manageable, but for n=1000, it becomes 1 billion operations, which is too slow.

Interview Verdict: TLE for large inputs

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 efficiently find pairs that complement the first chosen element, reducing complexity from cubic to quadratic.

Intuition

Fix one element and use two pointers to find the other two elements whose sum is closest to the target minus the fixed element.

Algorithm

1. Sort the input array.
2. Initialize a variable to store the closest sum.
3. Iterate over the array, fixing one element at a time.
4. For each fixed element, use two pointers (start and end) to find the best pair.
5. Move pointers based on comparison of current sum with target to get closer.
6. Update closest sum whenever a closer sum is found.

💡 Sorting enables the two-pointer technique, which is a common pattern to reduce search space in sorted arrays.

</>

Code

def threeSumClosest(nums, target):
    nums.sort()
    n = len(nums)
    closest_sum = nums[0] + nums[1] + nums[2]
    for i in range(n - 2):
        left, right = i + 1, n - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum
            if current_sum < target:
                left += 1
            elif current_sum > target:
                right -= 1
            else:
                return current_sum
    return closest_sum

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

Line Notes

nums.sort()Sorting the array to apply two-pointer technique

closest_sum = nums[0] + nums[1] + nums[2]Initialize closest sum with first three elements

for i in range(n - 2)Fix one element at a time

left, right = i + 1, n - 1Initialize two pointers for the remaining elements

while left < rightLoop until pointers meet

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

if abs(current_sum - target) < abs(closest_sum - target)Update closest sum if current is closer

if current_sum < target: left += 1Move left pointer right to increase sum

elif current_sum > target: right -= 1Move right pointer left to decrease sum

else: return current_sumExact match found, return immediately

import java.util.*;
public class ThreeSumClosest {
    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int closestSum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < n - 2; i++) {
            int left = i + 1, right = n - 1;
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                    closestSum = currentSum;
                }
                if (currentSum < target) {
                    left++;
                } else if (currentSum > target) {
                    right--;
                } else {
                    return currentSum;
                }
            }
        }
        return closestSum;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 2, 1, -4};
        int target = 1;
        System.out.println(threeSumClosest(nums, target)); // Output: 2
    }
}

Line Notes

Arrays.sort(nums);Sort the array to enable two-pointer approach

int closestSum = nums[0] + nums[1] + nums[2];Initialize closest sum with first three elements

for (int i = 0; i < n - 2; i++)Fix one element at a time

int left = i + 1, right = n - 1;Initialize two pointers for the remaining elements

while (left < right)Loop until pointers meet

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

if (Math.abs(currentSum - target) < Math.abs(closestSum - target))Update closest sum if current is closer

if (currentSum < target) { left++; }Move left pointer right to increase sum

else if (currentSum > target) { right--; }Move right pointer left to decrease sum

else { return currentSum; }Exact match found, return immediately

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int closestSum = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < n - 2; i++) {
        int left = i + 1, right = n - 1;
        while (left < right) {
            int currentSum = nums[i] + nums[left] + nums[right];
            if (abs(currentSum - target) < abs(closestSum - target)) {
                closestSum = currentSum;
            }
            if (currentSum < target) {
                left++;
            } else if (currentSum > target) {
                right--;
            } else {
                return currentSum;
            }
        }
    }
    return closestSum;
}

int main() {
    vector<int> nums = {-1, 2, 1, -4};
    int target = 1;
    cout << threeSumClosest(nums, target) << endl; // Output: 2
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort the vector to apply two-pointer technique

int closestSum = nums[0] + nums[1] + nums[2];Initialize closest sum with first three elements

for (int i = 0; i < n - 2; i++)Fix one element at a time

int left = i + 1, right = n - 1;Initialize two pointers for the remaining elements

while (left < right)Loop until pointers meet

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

if (abs(currentSum - target) < abs(closestSum - target))Update closest sum if current is closer

if (currentSum < target) { left++; }Move left pointer right to increase sum

else if (currentSum > target) { right--; }Move right pointer left to decrease sum

else { return currentSum; }Exact match found, return immediately

function threeSumClosest(nums, target) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let closestSum = nums[0] + nums[1] + nums[2];
    for (let i = 0; i < n - 2; i++) {
        let left = i + 1, right = n - 1;
        while (left < right) {
            const currentSum = nums[i] + nums[left] + nums[right];
            if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                closestSum = currentSum;
            }
            if (currentSum < target) {
                left++;
            } else if (currentSum > target) {
                right--;
            } else {
                return currentSum;
            }
        }
    }
    return closestSum;
}

// Test
console.log(threeSumClosest([-1, 2, 1, -4], 1)); // Output: 2

Line Notes

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

let closestSum = nums[0] + nums[1] + nums[2];Initialize closest sum with first three elements

for (let i = 0; i < n - 2; i++)Fix one element at a time

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

while (left < right)Loop until pointers meet

const currentSum = nums[i] + nums[left] + nums[right];Calculate current triplet sum

if (Math.abs(currentSum - target) < Math.abs(closestSum - target))Update closest sum if current is closer

if (currentSum < target) { left++; }Move left pointer right to increase sum

else if (currentSum > target) { right--; }Move right pointer left to decrease sum

else { return currentSum; }Exact match found, return immediately

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Sorting takes O(n log n), and the two-pointer search for each fixed element takes O(n), resulting in O(n^2) overall. Space is constant aside from input.

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

Interview Verdict: Accepted

This approach is efficient and accepted for large inputs, making it the standard solution to implement.

🧠

Early Exit Optimization

💡 This approach builds on the two-pointer method by adding early exit conditions to speed up when an exact match is found.

Intuition

If the current sum equals the target, we can immediately return since no closer sum is possible.

Algorithm

1. Sort the array.
2. Initialize closest sum with the first three elements.
3. Iterate over the array fixing one element.
4. Use two pointers to find pairs.
5. If current sum equals target, return immediately.
6. Otherwise, update closest sum and move pointers accordingly.

💡 This small optimization can save time in practice, especially when the exact target sum exists.

</>

Code

def threeSumClosest(nums, target):
    nums.sort()
    n = len(nums)
    closest_sum = nums[0] + nums[1] + nums[2]
    for i in range(n - 2):
        left, right = i + 1, n - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if current_sum == target:
                return current_sum
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum
            if current_sum < target:
                left += 1
            else:
                right -= 1
    return closest_sum

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

Line Notes

if current_sum == target:Check for exact match to return early

return current_sumReturn immediately if exact sum found

nums.sort()Sort array for two-pointer technique

closest_sum = nums[0] + nums[1] + nums[2]Initialize closest sum

for i in range(n - 2)Fix one element

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

if abs(current_sum - target) < abs(closest_sum - target)Update closest sum if closer

if current_sum < target: left += 1Move left pointer to increase sum

else: right -= 1Move right pointer to decrease sum

import java.util.*;
public class ThreeSumClosest {
    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int closestSum = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < n - 2; i++) {
            int left = i + 1, right = n - 1;
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                if (currentSum == target) {
                    return currentSum;
                }
                if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                    closestSum = currentSum;
                }
                if (currentSum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return closestSum;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 2, 1, -4};
        int target = 1;
        System.out.println(threeSumClosest(nums, target)); // Output: 2
    }
}

Line Notes

if (currentSum == target)Check for exact match to return early

return currentSum;Return immediately if exact sum found

Arrays.sort(nums);Sort array for two-pointer approach

int closestSum = nums[0] + nums[1] + nums[2];Initialize closest sum

for (int i = 0; i < n - 2; i++)Fix one element

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

if (Math.abs(currentSum - target) < Math.abs(closestSum - target))Update closest sum if closer

if (currentSum < target) { left++; } else { right--; }Move pointers to get closer to target

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int closestSum = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < n - 2; i++) {
        int left = i + 1, right = n - 1;
        while (left < right) {
            int currentSum = nums[i] + nums[left] + nums[right];
            if (currentSum == target) {
                return currentSum;
            }
            if (abs(currentSum - target) < abs(closestSum - target)) {
                closestSum = currentSum;
            }
            if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return closestSum;
}

int main() {
    vector<int> nums = {-1, 2, 1, -4};
    int target = 1;
    cout << threeSumClosest(nums, target) << endl; // Output: 2
    return 0;
}

Line Notes

if (currentSum == target)Check for exact match to return early

return currentSum;Return immediately if exact sum found

sort(nums.begin(), nums.end());Sort array for two-pointer technique

int closestSum = nums[0] + nums[1] + nums[2];Initialize closest sum

for (int i = 0; i < n - 2; i++)Fix one element

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

if (abs(currentSum - target) < abs(closestSum - target))Update closest sum if closer

if (currentSum < target) { left++; } else { right--; }Move pointers to get closer

function threeSumClosest(nums, target) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let closestSum = nums[0] + nums[1] + nums[2];
    for (let i = 0; i < n - 2; i++) {
        let left = i + 1, right = n - 1;
        while (left < right) {
            const currentSum = nums[i] + nums[left] + nums[right];
            if (currentSum === target) {
                return currentSum;
            }
            if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                closestSum = currentSum;
            }
            if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return closestSum;
}

// Test
console.log(threeSumClosest([-1, 2, 1, -4], 1)); // Output: 2

Line Notes

if (currentSum === target)Check for exact match to return early

return currentSum;Return immediately if exact sum found

nums.sort((a, b) => a - b);Sort array for two-pointer approach

let closestSum = nums[0] + nums[1] + nums[2];Initialize closest sum

for (let i = 0; i < n - 2; i++)Fix one element

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

if (Math.abs(currentSum - target) < Math.abs(closestSum - target))Update closest sum if closer

if (currentSum < target) { left++; } else { right--; }Move pointers to get closer

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Same as previous approach but with early exit to reduce runtime in best cases.

💡 Early exit can save time when exact target sum exists, but worst-case remains O(n^2).

Interview Verdict: Accepted

This is the preferred approach in interviews due to efficiency and simplicity.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, implement the sorting + two-pointer approach with early exit for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^3)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Sorting + Two Pointers	O(n^2)	O(1)	No	N/A	Code this approach as standard solution
3. Early Exit Optimization	O(n^2) best case faster	O(1)	No	N/A	Code this if comfortable, mention early exit

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the standard approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding.Step 3: Introduce sorting and two-pointer technique to optimize.Step 4: Code the two-pointer solution with early exit optimization.Step 5: Test your code with sample and edge cases.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your ability to optimize brute force, use sorting and two pointers, handle edge cases, and write clean code.

Common Follow-ups

• What if we want all triplets with sum closest to target? → Store all sums with minimal difference.
• How to handle duplicates to avoid repeated triplets? → Skip duplicates while iterating.
• Can this approach be extended to 4Sum Closest? → Yes, fix two elements and use two pointers.
• What if the array is very large and memory is limited? → Use in-place sorting and careful pointer management.

💡 These follow-ups test your understanding of variations and edge cases beyond the basic problem.

🔍

Pattern Recognition

When to Use

1) Problem asks for triplets or k-sums; 2) Find sum closest to target; 3) Input array can be sorted; 4) Two pointers can be applied after fixing one element.

Signature Phrases

three integerssum closest to targetsorted arraytwo pointers

NOT This Pattern When

Problems that require subsets or combinations without ordering or closest sums, e.g., subset sum or knapsack.

Similar Problems

3Sum - find triplets that sum to zero4Sum - extend to four elementsTwo Sum Closest - simpler two-element version

Practice

1. You are given two strings that may contain the backspace character '#'. After processing all backspaces, you need to determine if the resulting strings are equal. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Sort both strings after removing backspaces and then compare them.

B. Use a brute force approach by building the final strings with stacks and then compare them.

C. Use dynamic programming to track the state of each character after backspaces.

D. Use two pointers starting from the end of both strings, simulating backspaces on the fly without extra space.

Solution

1. Step 1: Understand the problem constraints

   The problem requires comparing two strings after applying backspace operations, which can be done efficiently by simulating the effect of backspaces without reconstructing the entire string explicitly.

2. Step 2: Identify the optimal approach

   Using two pointers from the end of both strings allows skipping characters affected by backspaces on the fly, achieving O(n + m) time and O(1) extra space, which is optimal compared to building stacks or using DP.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two pointers from the end simulate backspaces efficiently [OK]

Hint: Two pointers from end simulate backspaces efficiently [OK]

Common Mistakes:

• Assuming DP is needed for backspace processing
• Using sorting which changes character order
• Building full strings with stacks uses extra space

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

3. Given the following code snippet, what is the output when calling two_sum_binary_search([1,3,5,7], 8)?

easy

A. [1, 4]

B. [3, 4]

C. [1, 3]

D. [2, 3]

Solution

1. Step 1: Trace first iteration with i=0 (numbers[i]=1)

   Complement = 8 - 1 = 7; binary_search searches indices 1 to 3 for 7; finds at index 3.

2. Step 2: Return indices 1-based: i+1=1, j+1=4

   Returns [1, 4]. No further iterations needed.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Complement found at last index, output matches [1,4] [OK]

Hint: Trace binary search complement index carefully [OK]

Common Mistakes:

• Off-by-one in indices
• Wrong complement calculation
• Misunderstanding binary search bounds

4. What is the time complexity of the optimal two-pointer approach for the 3Sum Smaller problem when the input array has length n?

medium

A. O(n^2) because the outer loop runs n times and the inner two-pointer scan runs in O(n)

B. O(n^3) because of the nested loops

C. O(n log n) due to sorting dominating the complexity

D. O(n^2 log n) because each two-pointer step involves a binary search

Solution

1. Step 1: Identify loops and sorting cost

   Sorting takes O(n log n). The main loop runs O(n) times.

2. Step 2: Analyze inner two-pointer loop

   For each i, two pointers scan the remaining array once, total O(n) per i.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall time is O(n log n + n^2) -> O(n^2) dominates [OK]

Hint: Two pointers scan each element once per outer iteration [OK]

Common Mistakes:

• Confusing two-pointer scan as O(n^2) per iteration
• Ignoring sorting cost or assuming it dominates
• Assuming binary search is used inside two-pointer

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