Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Two Pointers

Guide 3 of 6 · Path 3 of 6

← PreviousNext →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtwo-pointers

3Sum Closest

Problem (restated)

Given an integer array nums and integer target, find three integers whose sum is closest to target. Return that sum.

Intuition

Sort, fix one index, two-pointer the rest while tracking the closest sum. same spine as 3Sum.

Approaches

Sort + two pointers

Tested only
Time O(n²)Space O(1)

Idea. For each i, lo/hi scan; update best when |sum-target| improves.

Walkthrough. nums=[-1,2,1,-4], target=1 → closest sum is 2.

Trade-offs. O(n²) after sort is expected; hashing does not simplify closest-sum.

Solution
export function threeSumClosest(nums: number[], target: number): number {
  nums = [...nums].sort((a, b) => a - b);
  let best = nums[0]! + nums[1]! + nums[2]!;
  for (let i = 0; i < nums.length - 2; i++) {
    let lo = i + 1, hi = nums.length - 1;
    while (lo < hi) {
      const s = nums[i]! + nums[lo]! + nums[hi]!;
      if (Math.abs(s - target) < Math.abs(best - target)) best = s;
      if (s === target) return s;
      if (s < target) lo++; else hi--;
    }
  }
  return best;
}

export function threeSumClosest(nums: number[], target: number): number {
  nums = [...nums].sort((a, b) => a - b);
  let best = nums[0]! + nums[1]! + nums[2]!;
  for (let i = 0; i < nums.length - 2; i++) {
    let lo = i + 1, hi = nums.length - 1;
    while (lo < hi) {
      const s = nums[i]! + nums[lo]! + nums[hi]!;
      if (Math.abs(s - target) < Math.abs(best - target)) best = s;
      if (s === target) return s;
      if (s < target) lo++; else hi--;
    }
  }
  return best;
}

Reflection