Skip to main content

Find Triplet with Zero Sum

Problem Statement​

Given an array arr[] of distinct integers of size N, the task is to find if there are any three elements in arr[] whose sum is equal to zero.

Examples​

Example 1:

Input:
N = 5
arr[] = {-1, 0, 1, 2, -1, -4}

Output:
True

Explanation:
The triplets {-1, 0, 1} and {-1, -1, 2} both have a sum of zero.

Example 2:

Input:
N = 3
arr[] = {1, 2, 3}

Output:
False

Explanation:
No triplet has a sum of zero.

Your Task​

You don't need to read input or print anything. Your task is to complete the function findTriplet() which takes the integer N and integer array arr[] as parameters and returns true if there is a triplet with a sum of zero, otherwise false.

Expected Time Complexity: O(N2)O(N^2)
Expected Auxiliary Space: O(1)O(1)

Constraints​

  • 1≤N≤1051 ≤ N ≤ 10^5
  • −103≤arr[i]≤103-10^3 ≤ arr[i] ≤ 10^3

Solution​

Approach​

We can solve this problem using sorting and the two-pointer technique. Here's a step-by-step approach:

  1. Sort the array.
  2. Iterate through the array using a for loop, fixing one element at a time.
  3. Use two pointers to find the other two elements that sum up to zero with the fixed element:
    • One pointer starts from the next element after the fixed element.
    • The other pointer starts from the end of the array.
  4. Adjust the pointers based on the sum of the three elements:
    • If the sum is zero, return true.
    • If the sum is less than zero, move the left pointer to the right.
    • If the sum is greater than zero, move the right pointer to the left.
  5. If no triplet is found, return false.

Implementation​

class Solution {
public:
bool findTriplet(int arr[], int n) {
sort(arr, arr + n);
for (int i = 0; i < n - 2; i++) {
int left = i + 1, right = n - 1;
while (left < right) {
int sum = arr[i] + arr[left] + arr[right];
if (sum == 0) return true;
if (sum < 0) left++;
else right--;
}
}
return false;
}
};

Complexity Analysis​

  • Time Complexity: O(N2)O(N^2), where N is the length of the array. We iterate through the array and for each element, we use the two-pointer technique which takes linear time.
  • Space Complexity: O(1)O(1), as we only use a constant amount of extra space for variables.

References​