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

Posted by N.K. Chauhan on Nov 18, 2022

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


Print all Subsets (Power Set) of a given array

Two Sum - return index of a pair of array elements with a given sum

Program to print Union of two sorted arrays

Longest substring without repeating characters

Program to print Intersection of two sorted arrays

Count the number of inversions in an array - in O(n log n) time

Print all possible permutations of an Array in O(1) space

Word Break Problem (Using HashMap and DP)

Merge two sorted arrays in O(1) space

Rain water trapping problem - O(n) time & O(n) space