Find a triplet in an array that sums to a given number

Posted by N.K. Chauhan on Mar 31, 2024

Given an array arr[] of size "n" and an integer "x," the task is to find if there is a triplet in the array that sums up to the given integer "x".

Example
Input: arr[] = {1, 2, 4, 3, 6}, n = 5, x = 10, Output: true

Example
Input: arr[] = {1, 2, 4, 6}, n = 4, x = 10, Output: false


Solutions

Method 1: In O(n^2) time and O(1) space

This method includes sorting the array, fixing the first number, and finding the remaining two numbers using two pointers.

The idea is loop over the sorted array and fix the first element of the possible triplet, arr[i].

Then run a while loop until j < k, where j = i + 1 and k = n – 1 and do the following:

1) If the sum (arr[i] + arr[j] +arr[k]) is smaller than the required sum, increment j (j++).
2) Else, if the sum is bigger, decrement k, (k--).
3) Else, if the sum is equal to the given number (n), then return "true."

Complexity

The time complexity of this solution is O(n^2) and space complexity is O(1).

Related


Find maximum and minimum element of an array

Program to right rotate an array by 'k' elements

Move all negative numbers to beginning of the array

Segregate 0s and 1s in an array (Sort an array of 0s and 1s)

Find duplicates in O(n) time and O(n) extra space.

Segregate 0s, 1s and 2s in an array (Sort an array of 0s, 1s and 2s)

Find duplicates in O(n) time and O(1) extra space

Find largest sum contiguous sub-array (Kadane's Algorithm)

Minimize the difference between the heights of smallest and highest tower

Alternating +ve & -ve in array in O(1) time (maintaining order)

Maximum Product Subarray (Modified Kadane's Algorithm)