Pairs With a Sum in Range

Medium

You are given an integer array weights and two bounds low and high. Count the index pairs (i, j) with i < j for which weights[i] + weights[j] lies between low and high, inclusive.

Example 1

weights=[3, 9, 4, 6, 1], low=7, high=10 → 5

The pairs 3+4, 3+6, 9+1, 4+6 and 6+1 fit, five in total.

Example 2

weights=[2, 2, 2], low=4, high=4 → 3

Any two of the three values sum to 4: three pairs.

Example 3

weights=[-5, 5], low=1, high=3 → 0

Constraints

1 ≤ len(weights) ≤ 10⁵
-10⁹ ≤ weights[i] ≤ 10⁹
-10⁹ ≤ low ≤ high ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Binary Search Sorting

Similar problems

Triples Under a Limit Medium Warm Every Cabin Medium Pairs With a Fixed Gap Medium Stick Triples That Form a Triangle Medium Nearest k Values Medium

Input

weights=[3, 9, 4, 6, 1], low=7, high=10

Expected

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