Triplets

Reported in interviews at Citadel

Problem statement

Given an array of $n$ distinct integers $d = [d[0], d[1], \ldots, d[n-1]]$ and an integer threshold $t$, count how many index triplets $(a, b, c)$ satisfy both of the following conditions:

  • $d[a] < d[b] < d[c]$
  • $d[a] + d[b] + d[c] \le t$

Implement:

def triplets(t, d):
    ...

where t is the integer threshold and d is the array of distinct integers. Return a long integer denoting the number of valid triplets.

Example: d = [1, 2, 3, 4, 5], t = 8. The following 4 triplets satisfy both constraints (by value): $(1, 2, 3) = 6$, $(1, 2, 4) = 7$, $(1, 2, 5) = 8$, and $(1, 3, 4) = 8$. The answer is $4$.

Show hint

Since all values are distinct, how much of the problem does putting the array in order take care of for you?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems