Count Triplets with Sum Less than Target

mediumSave

ArraySortingTwo Pointers

Given an array of integers and a target integer, find the number of triplets in the array that have a sum less than the given target. A triplet is a grouping of three integers from the array. The integers in a triplet should be distinct indices (i.e., they should not be the same element repeated).

Example 1

Input

[
  [
    -1,
    0,
    2,
    3
  ],
  3
]

Output

Explanation. The triplets with sum less than 3 are [-1, 0, 2] and [-1, 0, 3].

Example 2

Input

Output

Explanation. The valid triplets are [-1, 4, 1], [-1, 2, 1], [-1, 1, 3], and [-1, 2, 3].

Example 3

Input

Output

Explanation. The valid triplets are [5, 1, 3], [1, 3, 4], [1, 3, 7], and [1, 4, 7].

Follow-up: Can this problem be solved more efficiently using a specific sorting or two-pointer technique?

Constraints:

- The array may contain both positive and negative integers. - The size of the array is at least 3. - The target can be any integer.

Views: 4