⬅ Previous Topic
Three Sum ProblemNext Topic ⮕
Find Length of Largest Subarray with 0 Sum⬅ Previous Topic
Three Sum ProblemNext Topic ⮕
Find Length of Largest Subarray with 0 SumTopic Contents
Given an array of integers arr
and an integer target
, find all unique quadruplets (four numbers) in the array that sum up to the given target value.
(a, b, c, d)
such that a + b + c + d = target
.If no such quadruplets exist, return an empty list.
arr
of size n
and a target value target
.i
(0 to n-4).j
(i+1 to n-3).left = j+1
and right = n-1
to find two other numbers.target
, store the quadruplet.def four_sum(arr, target):
arr.sort()
n = len(arr)
res = []
for i in range(n-3):
if i > 0 and arr[i] == arr[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and arr[j] == arr[j-1]:
continue
left, right = j+1, n-1
while left < right:
total = arr[i] + arr[j] + arr[left] + arr[right]
if total == target:
res.append([arr[i], arr[j], arr[left], arr[right]])
left += 1
right -= 1
while left < right and arr[left] == arr[left-1]:
left += 1
while left < right and arr[right] == arr[right+1]:
right -= 1
elif total < target:
left += 1
else:
right -= 1
return res
# Sample Input
arr = [1, 0, -1, 0, -2, 2]
target = 0
print("Quadruplets:", four_sum(arr, target))
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n^3) | Even in the best case, we use two nested loops and a two-pointer approach, leading to cubic time complexity when scanning all possible quadruplets. |
Average Case | O(n^3) | For each pair of the first two elements (i and j), we use a two-pointer scan through the remaining array. This results in O(n³) combinations on average. |
Worst Case | O(n^3) | The algorithm always uses two nested loops plus a two-pointer traversal, so the worst-case complexity remains cubic. |
O(1) (excluding output)
Explanation: Only a few pointers and loop variables are used for the computation. However, the space needed to store the resulting quadruplets depends on the number of valid combinations found.
⬅ Previous Topic
Three Sum ProblemNext Topic ⮕
Find Length of Largest Subarray with 0 SumYou 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.