Triplet Zero Sum — Problem Statement & Solution Guide
Problem Description
A financial analyst has a list of net profit/loss values. Find the count of unique triplets from the list that perfectly cancel each other out (sum to zero).
DSA Pattern Breakdown
DSA Pattern Breakdown
"Triplet Zero Sum"
WHY DOES IT MATTER?
The two‑pointer pattern transforms a potentially cubic search into a quadratic one by exploiting order. It is a cornerstone technique for any problem that asks for pairs or triplets meeting a numeric condition, making it indispensable for interviewers testing algorithmic insight.
OPTIMIZATION CHALLENGE
The key insight is that after fixing one element, the remaining two numbers form a sorted sub‑array where the sum behaves monotonically. This allows a single linear pass with two pointers to locate the complementary pair, cutting the inner loop from O(n) to O(n) per fixed element, resulting in O(n²) overall.
REAL-WORLD CONNECTION
Think of a financial ledger where you need to reconcile three transactions that net to zero. By sorting transactions chronologically, you can sweep from the smallest debit to the largest credit, pairing them efficiently without revisiting already balanced subsets—mirroring the two‑pointer sweep in distributed ledger reconciliation.
During the interview, sort the array first, then iterate with an index i. Inside the loop, set left = i+1 and right = n-1; while left < right, compute sum = nums[i] + nums[left] + nums[right]. If sum == 0, increment count and skip over any duplicates on both sides before moving pointers. This duplicate‑skipping step is often the make‑or‑break detail.
COMPLEXITY AT A GLANCE
O(n^2)O(1) additionalCore Theory — Why This Approach?
The classic "3‑Sum" problem asks for all unique triplets (i, j, k) such that nums[i] + nums[j] + nums[k] = 0. A naïve solution enumerates every combination of three indices, leading to O(n³) time, which quickly becomes infeasible for n > 10⁴ – a typical size in financial data streams. The bottleneck is the repeated scanning of the same sub‑arrays and the lack of any ordering information to prune the search space.
By first sorting the array, we impose a monotonic structure that enables the two‑pointer technique. After fixing the first element of a potential triplet, the remaining two numbers can be found by moving a low pointer from the left and a high pointer from the right, adjusting them based on the current sum. This reduces the inner search to linear time, yielding an overall O(n²) algorithm while still guaranteeing that each unique triplet is reported exactly once by skipping duplicates during iteration.
The optimal paradigm therefore combines sorting (O(n log n)) with a deterministic linear scan for each fixed pivot. This hybrid approach leverages order to eliminate redundant work, turning an exponential‑ish brute force into a quadratic solution that comfortably handles the input limits of modern interview problems.
Interview Questions on This Problem
Q1How would you modify the 3‑Sum solution to return the count of unique triplets instead of the triplets themselves?
After sorting, use the same two‑pointer scan for each fixed index, but instead of storing the triplet, increment a counter each time a valid sum of zero is found. Ensure you skip over duplicate values for the fixed index and both pointers to avoid double‑counting.
Q2Can the 3‑Sum algorithm be adapted to work with a streaming input where numbers arrive one‑by‑one?
In a streaming context you cannot sort the entire dataset upfront. One approach is to maintain a hash‑set of seen numbers and, for each new element x, iterate over previously seen pairs (a, b) to check if a + b + x == 0, which is O(n²) per element. A more scalable solution uses a balanced BST to keep elements sorted and applies a sliding‑window two‑pointer search on the current window, trading off exactness for bounded memory.
Q3Why does the two‑pointer technique fail on an unsorted array, and how does sorting restore its correctness?
Two pointers rely on the invariant that moving the left pointer increases the sum and moving the right pointer decreases it. This monotonic behavior only holds when the underlying segment is sorted. Sorting guarantees that as indices move inward, the values change predictably, allowing us to decide which pointer to advance based on the current sum.
Examples
Input
[0, -2, 2, -3, 3]
Output
2
Explanation: Step-by-step: with input [0, -2, 2, -3, 3], we sort the array to get [-3, -2, 0, 2, 3]. Then we initialize three pointers, left = 0, mid = 1, right = 4. We move the mid pointer to find a pair that sums up to the negation of the leftmost element. If we find a pair, we increment the count and move the left pointer to find another triplet. If we don't find a pair, we move the right pointer to find another pair. Finally, we return the count.
Input
[0, 0, 0]
Output
1
Explanation: Step-by-step: with input [0, 0, 0], we sort the array to get [0, 0, 0]. Then we initialize three pointers, left = 0, mid = 1, right = 2. We move the mid pointer to find a pair that sums up to the negation of the leftmost element. If we find a pair, we increment the count and move the left pointer to find another triplet. If we don't find a pair, we move the right pointer to find another pair. Finally, we return the count.
Constraints
- 3 <= n <= 3000
- -10^5 <= arr[i] <= 10^5
Optimal Approach & Strategy
Sort the array and for each element use a two‑pointer sweep on the remaining sub‑array to find complementary pairs in linear time, achieving O(n²) overall.
Brute Force Approach
Enumerate every combination of three indices and check if their values sum to zero, leading to O(n³) time.
Verified Code Solutions
function countTriplets(nums) {
nums.sort((a, b) => a - b);
let count = 0;
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicate first element
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
count++;
const leftVal = nums[left];
const rightVal = nums[right];
while (left < right && nums[left] === leftVal) left++;
while (left < right && nums[right] === rightVal) right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return count;
}
// Example usage
const nums = [0, -2, 2, -3, 3];
console.log(countTriplets(nums));#include <bits/stdc++.h>\nusing namespace std;\n\nint countTriplets(vector<int>& nums) {\n sort(nums.begin(), nums.end());\n int n = nums.size();\n int count = 0;\n for (int i = 0; i < n - 2; ++i) {\n if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicate first element\n int left = i + 1;\n int right = n - 1;\n while (left < right) {\n long long sum = (long long)nums[i] + nums[left] + nums[right];\n if (sum == 0) {\n ++count;\n // skip duplicates for left and right\n int leftVal = nums[left];\n int rightVal = nums[right];\n while (left < right && nums[left] == leftVal) ++left;\n while (left < right && nums[right] == rightVal) --right;\n } else if (sum < 0) {
++left;\n } else {
--right;\n }\n }\n }\n return count;\n}\n\nint main() {\n vector<int> nums = {0, -2, 2, -3, 3};\n cout << countTriplets(nums) << endl;\n return 0;\n}\npublic class Solution {
public int countTriplets(int[] nums) {
java.util.Arrays.sort(nums);
int n = nums.length;
int count = 0;
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicate first element
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
count++;
int leftVal = nums[left];
int rightVal = nums[right];
while (left < right && nums[left] == leftVal) left++;
while (left < right && nums[right] == rightVal) right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums = {0, -2, 2, -3, 3};
Solution sol = new Solution();
System.out.println(sol.countTriplets(nums));
}
}def count_triplets(nums):
nums.sort()
n = len(nums)
count = 0
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate first element
left, right = i + 1, n - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
count += 1
left_val, right_val = nums[left], nums[right]
while left < right and nums[left] == left_val:
left += 1
while left < right and nums[right] == right_val:
right -= 1
elif s < 0:
left += 1
else:
right -= 1
return count
# Example usage
nums = [0, -2, 2, -3, 3]
print(count_triplets(nums))function countTriplets(nums) {
nums.sort((a, b) => a - b);
let count = 0;
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicate first element
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
count++;
const leftVal = nums[left];
const rightVal = nums[right];
while (left < right && nums[left] === leftVal) left++;
while (left < right && nums[right] === rightVal) right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return count;
}
// Example usage
const nums = [0, -2, 2, -3, 3];
console.log(countTriplets(nums));Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.