Pattern visualizer
3Sum
Brute force checks every triple in O(n³). Instead, sort once: now duplicates sit next to each other and, with one element i fixed, the remaining pair-search becomes sorted Two Sum — a single comparison tells you which pointer to move. n fixed positions × one linear scan each = O(n²). Animated on: Find all unique triplets in [-1, 0, 1, 2, -1, -4] that sum to 0..
Sort, fix i, then two-pointer scan
time O(n²)space O(1)step 1 / 11
-1
[0]0
[1]1
[2]2
[3]-1
[4]-4
[5]line 2
Input [-1, 0, 1, 2, -1, -4], target sum 0. Unsorted, we can't steer a pointer or spot the duplicate -1s. Sort first.
Pseudocode
1FUNCTION threeSum(nums):2 sort nums into ascending order3 FOR i from 0 to (length of nums) - 3:4 IF i > 0 and nums[i] equals nums[i-1]: skip to the next i5 set l to i+1, r to (length of nums) - 16 WHILE l < r:7 s = nums[i] + nums[l] + nums[r]8 IF s equals 0: save this triple, move l one step right and r one step left9 ELSE IF s < 0: move l one step right, otherwise move r one step left10 RETURN the saved triples
← / → step · space play · Home restart