⬅ Previous Topic
Two Sum ProblemNext Topic ⮕
4 Sum Problem⬅ Previous Topic
Two Sum ProblemNext Topic ⮕
4 Sum ProblemTopic Contents
Given an array of integers, your task is to find all the unique triplets (a, b, c)
in the array such that:
a + b + c = 0
(the sum of the three elements is zero)If no such triplets exist, return an empty list.
arr
of integers.i
from 0 to n-2
:i > 0
and arr[i] == arr[i-1]
, skip to avoid duplicates.left = i + 1
and right = n - 1
.left < right
:arr[i] + arr[left] + arr[right]
.left
and right
to skip duplicates.left
forward.right
backward.def three_sum(nums):
nums.sort()
result = []
n = len(nums)
for i in range(n-2):
if i > 0 and nums[i] == nums[i-1]:
continue
left, right = i+1, n-1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
# Sample Input
arr = [-1, 0, 1, 2, -1, -4]
print("Triplets:", three_sum(arr))
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n^2) | In the best case, the input is small or contains many duplicate values that allow early skips, but the dominant term is still the nested loop structure with two pointers. |
Average Case | O(n^2) | We sort the array in O(n log n) and then use a loop with a two-pointer technique inside, which takes O(n^2) in total. |
Worst Case | O(n^2) | Even in the worst case with no duplicate skipping and all combinations needing to be checked, the time complexity remains O(n^2) due to the nested traversal using two pointers. |
O(1)
Explanation: The algorithm uses constant extra space apart from the output list. Sorting is done in-place and only a few variables (i, left, right) are used.
⬅ Previous Topic
Two Sum ProblemNext Topic ⮕
4 Sum ProblemYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.