Three Sum Challenge
Find three numbers in an array that add up to a target value. Learn two-pointer techniques and array manipulation.
Target Sum
Array:
šÆ Problem Statement
Given an array of integers and a target sum, find all unique triplets in the array that add up to the target. Each triplet should contain three different numbers (iā jā k), and the solution should not contain duplicate triplets.
š” Key Concepts
Two Pointer Approach
After sorting, use two pointers to find pairs that sum to the complement of the current number.
Sorting First
Sort the array first to enable efficient two-pointer technique and avoid duplicates.
š Algorithm Pseudo Code
function threeSum(nums, target):
// Sort the array to enable two-pointer technique
sort(nums)
result = []
// Iterate through each number as the first element
for i from 0 to length(nums) - 2:
// Skip duplicates for the first element
if i > 0 and nums[i] == nums[i-1]:
continue
// Use two pointers for the remaining two elements (iā jā k constraint)
left = i + 1 // j starts after i
right = length(nums) - 1 // k starts at the end
while left < right: // ensures jā k
sum = nums[i] + nums[left] + nums[right]
if sum == target:
// Found a valid triplet (iā jā k guaranteed)
result.append([nums[i], nums[left], nums[right]])
// Skip duplicates for left pointer
while left < right and nums[left] == nums[left+1]:
left += 1
// Skip duplicates for right pointer
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
elif sum < target:
left += 1
else:
right -= 1
return resultš Step-by-Step Example
Input: nums = [-1, 0, 1, 2, -1, -4], target = 0
Step 1: Sort array ā [-4, -1, -1, 0, 1, 2]
Step 2: i=0, nums[0]=-4, left=1, right=5
sum = -4 + (-1) + 2 = -3 < 0, left++
Step 3: i=1, nums[1]=-1, left=2, right=5
sum = -1 + (-1) + 2 = 0, found triplet!
Result: [[-1, -1, 2], [-1, 0, 1]]
š Two Pointer Visualization
ā±ļø Complexity Analysis
Time Complexity
O(nĀ²) - Sorting O(n log n) + Two pointers O(nĀ²)
Space Complexity
O(1) - Only using a few variables
š Alternative Approaches
Brute Force
O(nĀ³) - Check all possible triplets
Two Pointer (Optimal)
O(nĀ²) - Sort + Two pointers
Hash Set
O(nĀ²) - Use hash set to avoid duplicates
š Real-world Applications
ā ļø Common Pitfalls
Duplicate Triplets
Always skip duplicates to avoid returning the same triplet multiple times.
Not Sorting
Sorting is essential for the two-pointer technique to work efficiently.
Early Termination
Don't stop after finding the first triplet - there might be multiple solutions.
1. Click on three numbers in the array
2. Their sum should equal the target value
3. You cannot use the same element twice
4. Find all valid triplets to advance
5. Complete all levels to win!