Find a triplet that sums to a given value

Medium

Problem

Given an array and a target x, return true if some three distinct indices hold values that sum to exactly x (or return the triplet).

Example 1

Input:  arr = [1, 4, 45, 6, 10, 8], x = 13
Output: true

1 + 4 + 8 = 13.

Also asked as: Find the triplet that sum to a given value · 3 sum

Test cases

Case 1

Input:    [1,4,45,6,10,8], 13
Expected: [1,4,8]

Case 2

Input:    [1,2,3], 10
Expected: null

Case 3

Input:    [1,2,3], 6
Expected: [1,2,3]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sort + fix one + two pointers

Time O(n²)Space O(1)

Sort. Fix index i, then two-pointer the rest for (target − a[i]).

function findTriplet(a, target) {
a.sort((x, y) => x - y);
for (let i = 0; i < a.length - 2; i++) {
let l = i + 1, r = a.length - 1;
while (l < r) {
const s = a[i] + a[l] + a[r];
if (s === target) return [a[i], a[l], a[r]];
s < target ? l++ : r--;
}
}
return null;
}