Pattern visualizer
4Sum
Checking all four indices costs O(n^4). Sorting first collapses one whole dimension: once two indices are frozen, the rest is the classic sorted two-sum, where a sum that is too small can only be raised by abandoning the smallest value and one that is too large only lowered by abandoning the largest. Each discarded value is gone for good, so the tail scan is linear. Sorting also puts equal values next to each other, which is why duplicates can be skipped by a neighbour comparison instead of de-duplicating the answer list at the end. Animated on: nums = [1, 0, -1, 0, -2, 2], target = 0 — find every unique quadruplet that sums to the target..
Fix two indices, then run two-sum on the sorted tail
nums = [1, 0, -1, 0, -2, 2], target = 0. Unsorted, nothing tells us which way to search: a sum that is too small could be fixed by swapping in any of the remaining values.
1FUNCTION fourSum(nums, target)2 SORT nums3 FOR i <- 0 TO LENGTH(nums) - 44 IF i > 0 AND nums[i] = nums[i - 1] THEN CONTINUE5 FOR j <- i + 1 TO LENGTH(nums) - 36 IF j > i + 1 AND nums[j] = nums[j - 1] THEN CONTINUE7 l <- j + 18 r <- LENGTH(nums) - 19 WHILE l < r10 s <- nums[i] + nums[j] + nums[l] + nums[r]11 IF s = target THEN APPEND (nums[i], nums[j], nums[l], nums[r]) TO out12 IF s <= target THEN l <- l + 113 IF s >= target THEN r <- r - 114 RETURN out
← / → step · space play · Home restart