Hackerrank: Triple Sum Solution

Approach

First, remove duplicated elements in each array to avoid duplicated triplet

Then

Option 1: brute force, exhausive search by 3 nested loop to find triplet

Option 2:

• iterate through each element of
  B
  , count the number of elements, which are less than or equal to the iterated element of
  B
  , in each
  A
  and
  C
• counting using binary search

Implementation

1function binarySearch(A, x) {
2  let N = A.length
3  let begin = 0
4  let end = N - 1
5  let result = -1
6  while (begin <= end) {
7    let mid = Math.floor((begin + end) / 2)
8    if (A[mid] <= x) {
9      begin = mid + 1
10      result = mid
11    } else {
12      end = mid - 1
13    }
14  }
15  return result + 1
16}
17
18function triplets(a, b, c) {
19  const ascSortThenUnique = arr =>
20    Array.from(new Set(arr)).sort((a, b) => a - b)
21  a = ascSortThenUnique(a)
22  b = ascSortThenUnique(b)
23  c = ascSortThenUnique(c)
24  let res = 0
25  for (const q of b) {
26    res += binarySearch(a, q) * binarySearch(c, q)
27  }
28  return res
29}