🔺

Sort + Fix One + Two Pointers

Sort the array first. Fix one element (outer loop), then use opposite-end two pointers on the remaining suffix to find pairs that complete the target. O(n²) total.

Array Sort + Two Pointers 3Sum / kSum Time O(n²) Space O(1)

📋 When to Use

Find triplets / quadruplets summing to a target
Need all unique combinations (no hash-set dedup overhead)
Brute-force O(n³) is too slow — O(n²) is acceptable
Input can be sorted (or sorting is allowed)
Avoid duplicate triplets by skipping equal neighbors after sort

💡 After sorting, fix nums[i] and use L=i+1, R=n-1. Sum too small → L++. Sum too large → R--. Match → record triplet, skip duplicates, move both. Outer loop skips duplicate nums[i].

⚡ Complexity

Time

O(n²)

Space

O(1)

Sorting: O(n log n). Outer loop: O(n). Inner two-pointer sweep: O(n). Total: O(n²). No extra space — result list aside.

vs Brute Force

O(n³) → O(n²) with sort + two pointers

Problem — 3Sum (LeetCode #15) Given an integer array, find all unique triplets [nums[i], nums[j], nums[k]] such that nums[i] + nums[j] + nums[k] == 0. No duplicate triplets.
Input: nums = [-4, -1, -1, 0, 1, 2] · Answer: [[-1,-1,2], [-1,0,1]]

Step 1 / —

📌 Fix — outer loop fixes nums[i]

🔍 Scan — L/R converge on target sum

✦ Found — triplet recorded!

✅ Done

i = fixed element

L = left pointer

R = right pointer

nums = [-4, -1, -1, 0, 1, 2] (sorted)

✦ Triplets Found

nums[i] = —

L+R sum = —

triplets = 0

Click ▶ Play or Next ▶ to start

Arrays.sort(nums); // sort first — enables two-pointer

Complete Java TemplateJAVA

// Sort + Fix One + Two Pointers  (target sum = 0)
Arrays.sort(nums);

for (int i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) continue;  // skip duplicate fixed

    int left = i + 1, right = nums.length - 1;
    while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];

        if (sum == 0) {
            result.add(/* 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++;    // need larger
        } else {
            right--;   // need smaller
        }
    }
}

🎯 Practice Problems

#167Two Sum II — opposite-end pointers on sorted arrayMedium #153Sum — sort + fix one + two pointersMedium #163Sum Closest — track minimum absolute differenceMedium #184Sum — two nested loops + inner two pointersMedium #611Valid Triangle Number — count triplets, fix largest sideMedium GFGCount Triplets with Sum Smaller than TargetMedium