1.

Given an array of distinct integers, you need to find all the triplets whose sum is equal to 0.

Answer»

Example:

Input: arr = {1, -2, 1, 0, 5}

Output: [1, -2, 1]

Explanation: In the given array, only the triplet [1, -2, 1] sums up to 0.

Input: arr = {0, -1, 2, -3, 1}

Output: [0, -1, 1], [2, -3, 1]

  • Approach 1: The basic approach involves running three loops and checking if the total of three elements is zero or not one by one. Print elements if the sum of the three elements is 0. Since this is a very STRAIGHTFORWARD approach, we are not providing the implementation of this approach.
  • Approach 2: In this approach, we use the concept of hashing. We run a nested LOOP with two loops, the outer loop from 0 to n-2 and the inner loop from i+1 to n-1. We check whether the hashmap contains the sum of the ith and jth elements multiplied by -1. If the hashmap contains the element, we have found a triplet and we print it.

Solution Code:

//function to print all the triplets in a given array whose sum equals 0.void printTriplets(INT arr[], int n){ bool flag = false; for (int i=0; i<n-1; i++) { unordered_set<int> hash_map; for (int j=i+1; j<n; j++) { int third_element = -(arr[i] + arr[j]); if (hash_map.find(third_element) != hash_map.end()) { cout << third_element << arr[i] << arr[j] << "\n"; flag = true; } else hash_map.insert(arr[j]); } } if (flag == false) cout << "There is no such triplet in the given array." << endl;}

Time Complexity: O(n^2)

Space Complexity: O(n)

Here, n is the size of the array

Explanation: In the above code, the function printTriplets() takes input of an array of distinct elements and prints all the triplets whose sum equals 0. We KEEP track of the element VISITED with the help of a hashmap. 

Approach 3: In this approach, we aim to optimize the space complexity of the above approach. We first sort the input array in ascending order. We create two variables low = i + 1 and high = n – 1 for each index i. 

  • If the total of array[i], array[low], and array[high] is equal to zero then print this triplet and increment low and decrement high.
  • If the sum is less than zero, increase the value of low; as the array is sorted, the sum will increase as the value of low is increased, so array[low+1] > array [low].
  • If the sum is larger than zero, reduce the value of high; as the array is sorted, the sum will decrease as the value of high is decreased, so array[high-1] < array [high].

Solution Code:

void printTriplets(int arr[], int n){ bool flag = false; // Sorting the given input array sort(arr, arr+n); for (int i=0; i<n-1; i++) { // initialize left and right int low = i + 1; int high = n - 1; int cur = arr[i]; while (low < high) { if (cur + arr[low] + arr[high] == 0) { // We print the elements if it's sum is zero cout << cur << arr[low] << arr[high] << "\n"; low++; high--; } // If sum of three elements is less than zero then we increment in left else if (cur + arr[low] + arr[high] < 0) low++; // if sum is greater than zero then we decrement in right side else high--; } } if (flag == false) cout << " No Triplet flag" << endl;}

Time Complexity: O(n^2)

Space Complexity: O(1)

Explanation: In the above code, the function printTriplets takes an array and the size of the array as an input parameter. We first sort the array and then iterate through every possible triplet that may sum up to 0.


Discussion

No Comment Found

Related InterviewSolutions