Skip to main content

15. 3Sum

mediumAsked at HP

HP enterprise analytics pipelines perform multi-dimensional range queries and constraint-satisfaction checks on device telemetry. 3Sum is the canonical multi-pointer problem — HP uses it to evaluate whether you can methodically eliminate the cubic brute force down to quadratic through sorting and pointer discipline.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in HP loops.

  • Glassdoor (2026-Q1)— HP SWE onsite reports cite 3Sum as a common second-round medium question testing sorting and two-pointer technique.
  • Blind (2025-12)— HP technical interview prep threads recommend 3Sum as a must-practice medium for HP SWE roles.

Problem

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.

Constraints

  • 3 <= nums.length <= 3000
  • −10^5 <= nums[i] <= 10^5

Examples

Example 1

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

Explanation: Sort the array, fix each element, and use two pointers to find pairs that sum to its negation.

Example 2

Input
nums = [0,1,1]
Output
[]

Explanation: No triplet sums to zero.

Example 3

Input
nums = [0,0,0]
Output
[[0,0,0]]

Explanation: All zeros is the only valid triplet.

Approaches

1. Sort + two pointers

Sort the array. For each index i, use two pointers (left = i+1, right = end) to find pairs that sum to -nums[i]. Skip duplicates at every step.

Time
O(n²)
Space
O(1) excluding output
function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicate i
    let left = i + 1, right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }
  return result;
}

Tradeoff: O(n²) time after O(n log n) sort. The duplicate-skipping logic is the tricky part — handle it carefully at all three positions.

HP-specific tips

HP interviewers want you to call out the duplicate-skipping logic as a first-class concern — don't leave it as an afterthought. Walk through the [-1,0,1,2,-1,-4] example step by step showing how duplicates are skipped at the i, left, and right positions. Early termination is also a win: if nums[i] > 0, no three positive numbers can sum to zero, so you can break the outer loop.

Common mistakes

  • Using a set to de-duplicate — correct but harder to reason about; two-pointer with in-place skipping is cleaner.
  • Skipping duplicates only at i but not at left and right — produces duplicate triplets.
  • Not sorting before applying two pointers — the approach requires sorted order.
  • Using index-based instead of value-based duplicate checks — check nums[i] === nums[i-1], not i === i-1.

Follow-up questions

An interviewer at HP may pivot to one of these next:

  • 4Sum (LC 18) — add another loop and apply the same two-pointer pattern.
  • 3Sum Closest (LC 16) — find the triplet sum closest to a target.
  • How would you parallelize this across multiple CPU cores for a very large array?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why sort before applying two pointers?

Sorting allows the two-pointer technique: if the sum is too small, advance left to increase it; if too large, retreat right. Without sorting, you can't make this directed decision.

How do you skip duplicate triplets at the i level?

After processing index i, skip any subsequent indices with the same value: if (i > 0 && nums[i] === nums[i-1]) continue.

Can you solve 3Sum in O(n) time?

Not with known algorithms. O(n²) is the current best. Sorting reduces the search space but does not drop below quadratic for this problem.

Practice these live with InterviewChamp.AI

Drill 3Sum and other HP interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →