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

Two Pointers

Guide 4 of 6 · Path 4 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

4Sum

Problem (restated)

Return all unique quadruplets that sum to target.

Intuition

Generalize k-sum: sort, fix two indices, two-pointer the rest; skip duplicates.

Approaches

Sort + nested two pointers

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

Idea. Nested i,j with lo/hi; skip equal neighbors to keep unique quadruplets.

Walkthrough. [1,0,-1,0,-2,2], target=0 → three unique quadruplets.

Trade-offs. O(n³) is standard; pair-hash uses more memory.

Solution
export function fourSum(nums: number[], target: number): number[][] {
  nums = [...nums].sort((a, b) => a - b);
  const res: number[][] = [];
  const n = nums.length;
  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      let lo = j + 1, hi = n - 1;
      while (lo < hi) {
        const s = nums[i]! + nums[j]! + nums[lo]! + nums[hi]!;
        if (s === target) {
          res.push([nums[i]!, nums[j]!, nums[lo]!, nums[hi]!]);
          lo++; hi--;
          while (lo < hi && nums[lo] === nums[lo - 1]) lo++;
          while (lo < hi && nums[hi] === nums[hi + 1]) hi--;
        } else if (s < target) lo++; else hi--;
      }
    }
  }
  return res;
}

export function fourSum(nums: number[], target: number): number[][] {
  nums = [...nums].sort((a, b) => a - b);
  const res: number[][] = [];
  const n = nums.length;
  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      let lo = j + 1, hi = n - 1;
      while (lo < hi) {
        const s = nums[i]! + nums[j]! + nums[lo]! + nums[hi]!;
        if (s === target) {
          res.push([nums[i]!, nums[j]!, nums[lo]!, nums[hi]!]);
          lo++; hi--;
          while (lo < hi && nums[lo] === nums[lo - 1]) lo++;
          while (lo < hi && nums[hi] === nums[hi + 1]) hi--;
        } else if (s < target) lo++; else hi--;
      }
    }
  }
  return res;
}

Reflection