Triples Under a Limit

Medium

You are given an integer array values and a threshold limit. Count the index triples i < j < k for which values[i] + values[j] + values[k] < limit. Triples are told apart by their indices: equal values at different positions form different triples.

Example 1

values=[3, -1, 4, 0], limit=4 → 2

The triples (3, -1, 0) with sum 2 and (-1, 4, 0) with sum 3 qualify. The other two sum to 6 and 7.

Example 2

values=[2, 2, 2, 2], limit=6 → 0

Every triple sums to exactly 6, and the sum must be strictly less.

Example 3

values=[5, 1], limit=100 → 0

Two numbers are not enough to form a triple.

Constraints

0 ≤ len(values) ≤ 3500
-100 ≤ values[i] ≤ 100
-100 ≤ limit ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Binary Search Sorting

Similar problems

Warm Every Cabin Medium Pairs With a Fixed Gap Medium Stick Triples That Form a Triangle Medium Nearest k Values Medium Ranked Prime Ratios Medium

Input

values=[3, -1, 4, 0], limit=4

Expected

Run checks the first 3 tests in your browser. Submit checks all 94 tests on the server, hidden ones included.