Given an array arr[], find all possible indices [i, j, k] of triplets [arr[i], arr[j], arr[k]] in the array whose sum is equal to zero. Return indices of triplets in any order and all the returned triplets indices should also be internally sorted, i.e., for any triplet indices [i, j, k], the condition i < j < k should hold.
Note: Try to solve this using the O(n2) approach.
Examples:
Input: arr[] = [0, -1, 2, -3, 1] Output: [[0, 1, 4], [2, 3, 4]] Explanation: Triplets with sum 0 are:
arr[0] + arr[1] + arr[4] = 0 + (-1) + 1 = 0 arr[2] + arr[3] + arr[4] = 2 + (-3) + 1 = 0
Input: arr[] = [1, -2, 1, 0, 5] Output: [[0, 1, 2]] Explanation: Only triplet which satisfies the condition is arr[0] + arr[1] + arr[2] = 1 + (-2) + 1 = 0
Input: arr[] = [2, 3, 1, 0, 5] Output: [[]] Explanation: There is no triplet with sum 0.
Constraints:
3 <= arr.size() <= 103
-104 <= arr[i] <= 104
Approach 01:
-
C++
-
Python
#include <vector>
#include <set>
#include <unordered_map>
#include <algorithm>
class Solution {
public:
std::vector<std::vector<int>> findTriplets(const std::vector<int>& arr) {
std::set<std::tuple<int, int, int>> uniqueTriplets;
int arrayLength = arr.size();
std::unordered_map<int, std::vector<std::pair<int, int>>> pairSumMap;
// Store sum of all pairs with their indices
for (int i = 0; i < arrayLength; i++) {
for (int j = i + 1; j < arrayLength; j++) {
int currentSum = arr[i] + arr[j];
pairSumMap[currentSum].emplace_back(i, j);
}
}
for (int i = 0; i < arrayLength; i++) {
// Find remaining value to achieve zero sum
int requiredSum = -arr[i];
if (pairSumMap.find(requiredSum) != pairSumMap.end()) {
for (const auto& indices : pairSumMap[requiredSum]) {
// Ensure no two indices are the same in the triplet
if (indices.first != i && indices.second != i) {
std::vector<int> triplet = {i, indices.first, indices.second};
std::sort(triplet.begin(), triplet.end());
uniqueTriplets.insert(std::make_tuple(triplet[0], triplet[1], triplet[2]));
}
}
}
}
// Convert set of tuples to vector of vectors
std::vector<std::vector<int>> result;
for (const auto& triplet : uniqueTriplets) {
result.push_back({std::get<0>(triplet), std::get<1>(triplet), std::get<2>(triplet)});
}
return result;
}
};
class Solution:
def findTriplets(self, arr):
uniqueTriplets = set()
arrayLength = len(arr)
pairSumMap = {}
# Store sum of all pairs with their indices
for i in range(arrayLength):
for j in range(i + 1, arrayLength):
currentSum = arr[i] + arr[j]
if currentSum not in pairSumMap:
pairSumMap[currentSum] = []
pairSumMap[currentSum].append((i, j))
for i in range(arrayLength):
# Find remaining value to achieve zero sum
requiredSum = -arr[i]
if requiredSum in pairSumMap:
for indices in pairSumMap[requiredSum]:
# Ensure no two indices are the same in the triplet
if indices[0] != i and indices[1] != i:
triplet = sorted([i, indices[0], indices[1]])
uniqueTriplets.add(tuple(triplet))
return [list(triplet) for triplet in uniqueTriplets]
Time Complexity
- Pair Sum Calculation:
The first nested loop goes through all pairs of elements in
arrto calculate their sums and store them in thepairSumMap. This takes \( O(N^2) \), where \( N \) is the length of the array. - Triplet Search:
The second loop iterates over each element in
arr(with a single loop of \( O(N) \)) and for each element, checks for valid pairs inpairSumMap. Finding and validating pairs withinpairSumMapinvolves iterating over the list of pairs, which in the worst case can be \( O(N) \). This results in an overall time complexity of \( O(N^2) \) for this section. - Overall Time Complexity:
The overall time complexity is \( O(N^2) + O(N^2) = O(N^2) \).
Space Complexity
- Pair Sum Map:
The
pairSumMapstores sums of all pairs, which requires \( O(N^2) \) space for storage. - Unique Triplets Set:
The
uniqueTripletsset stores unique triplet combinations and can hold up to \( O(N^3) \) triplets in the worst case, but in practice, it is less than \( O(N^3) \) due to uniqueness constraints. - Overall Space Complexity:
The overall space complexity is \( O(N^2) + O(N^3) = O(N^3) \) in the worst case.
Approach 02:
-
C++
-
Python
#include <vector>
#include <limits>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> calculateSubArraySums(vector<int>& nums, int subArraySize) {
int currentSum = 0;
vector<int> subArraySums;
for (int i = 0; i < nums.size(); ++i) {
currentSum += nums[i];
// Start forming subarrays after the first subArraySize elements
if (i >= subArraySize - 1) {
subArraySums.push_back(currentSum);
currentSum -= nums[i - subArraySize + 1];
}
}
return subArraySums;
}
int calculateMaxSum(int remainingCount, int startIndex, int subArraySize, vector<int>& subArraySums, vector<vector<int>>& dp) {
if (startIndex >= subArraySums.size() || remainingCount == 0) {
return 0;
}
if (dp[remainingCount][startIndex] != -1) {
return dp[remainingCount][startIndex];
}
// Include current subarray
int includeCurrent = subArraySums[startIndex] + calculateMaxSum(remainingCount - 1, startIndex + subArraySize, subArraySize, subArraySums, dp);
// Skip current subarray
int excludeCurrent = calculateMaxSum(remainingCount, startIndex + 1, subArraySize, subArraySums, dp);
dp[remainingCount][startIndex] = max(includeCurrent, excludeCurrent);
return dp[remainingCount][startIndex];
}
void solve(int subArraySize, int remainingCount, int currentIndex, vector<int>& resultIndices, vector<int>& subArraySums, vector<vector<int>>& dp) {
while (remainingCount > 0 && currentIndex < subArraySums.size()) {
int includeCurrent = subArraySums[currentIndex] + calculateMaxSum(remainingCount - 1, currentIndex + subArraySize, subArraySize, subArraySums, dp);
int excludeCurrent = calculateMaxSum(remainingCount, currentIndex + 1, subArraySize, subArraySums, dp);
if (includeCurrent >= excludeCurrent) {
resultIndices.push_back(currentIndex);
remainingCount--;
currentIndex += subArraySize;
} else {
currentIndex++;
}
}
}
vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int subArraySize) {
vector<int> resultIndices;
vector<int> subArraySums = calculateSubArraySums(nums, subArraySize);
int n = subArraySums.size();
vector<vector<int>> dp(4, vector<int>(n, -1)); // 4 rows for up to 3 subarrays + base case
solve(subArraySize, 3, 0, resultIndices, subArraySums, dp);
return resultIndices;
}
};
from typing import List
class Solution:
def calculateSubArraySums(self, nums: List[int], subArraySize: int) -> List[int]:
currentSum = 0
subArraySums = []
for i in range(len(nums)):
currentSum += nums[i]
# Start forming subarrays after the first subArraySize elements
if i >= subArraySize - 1:
subArraySums.append(currentSum)
currentSum -= nums[i - subArraySize + 1]
return subArraySums
def calculateMaxSum(self, remainingCount: int, startIndex: int, subArraySize: int, subArraySums: List[int], dp: List[List[int]]) -> int:
if startIndex >= len(subArraySums) or remainingCount == 0:
return 0
if dp[remainingCount][startIndex] != -1:
return dp[remainingCount][startIndex]
# Include current subarray
includeCurrent = subArraySums[startIndex] + self.calculateMaxSum(remainingCount - 1, startIndex + subArraySize, subArraySize, subArraySums, dp)
# Skip current subarray
excludeCurrent = self.calculateMaxSum(remainingCount, startIndex + 1, subArraySize, subArraySums, dp)
dp[remainingCount][startIndex] = max(includeCurrent, excludeCurrent)
return dp[remainingCount][startIndex]
def solve(self, subArraySize: int, remainingCount: int, currentIndex: int, resultIndices: List[int], subArraySums: List[int], dp: List[List[int]]):
while remainingCount > 0 and currentIndex < len(subArraySums):
includeCurrent = subArraySums[currentIndex] + self.calculateMaxSum(remainingCount - 1, currentIndex + subArraySize, subArraySize, subArraySums, dp)
excludeCurrent = self.calculateMaxSum(remainingCount, currentIndex + 1, subArraySize, subArraySums, dp)
if includeCurrent >= excludeCurrent:
resultIndices.append(currentIndex)
remainingCount -= 1
currentIndex += subArraySize
else:
currentIndex += 1
def maxSumOfThreeSubarrays(self, nums: List[int], subArraySize: int) -> List[int]:
resultIndices = []
subArraySums = self.calculateSubArraySums(nums, subArraySize)
n = len(subArraySums)
dp = [[-1] * n for _ in range(4)] # 4 rows for up to 3 subarrays + base case
self.solve(subArraySize, 3, 0, resultIndices, subArraySums, dp)
return resultIndices
Time Complexity
- Map Construction:
- Iterating through the array to populate the
indexMaptakes \( O(n) \), where \( n \) is the size of the array.
- Iterating through the array to populate the
- Triplet Search:
- The outer loop iterates over all possible first indices, i.e., \( O(n) \).
- The middle loop iterates over all possible second indices, i.e., \( O(n) \).
- For each pair of indices, the lookup and processing of potential third indices depends on the size of the map and can involve up to \( O(n) \) iterations in the worst case.
- Overall, the triplet search takes \( O(n^3) \) in the worst case.
- Overall Time Complexity:
The total time complexity is: \( O(n^3) \).
Space Complexity
- Index Map:
- The
indexMapstores indices of each element in the array, requiring \( O(n) \) space.
- The
- Output Storage:
- The result
tripletscan store up to \( O(n^3) \) triplets in the worst case.
- The result
- Auxiliary Variables:
- Loop variables and temporary variables require \( O(1) \) space.
- Overall Space Complexity:
The total space complexity is dominated by the size of the output, resulting in: \( O(n^3) \).