Triplets with Sum in Range

Problem Overview

The count in [l, r] is (triplets with sum <= r) minus (triplets with sum <= l-1).

Intuition

The count in [l, r] is (triplets with sum <= r) minus (triplets with sum <= l-1). After sorting, fix arr[i] and scan the rest with two pointers: when arr[i]+arr[lo]+arr[hi] is small enough, every hi between lo+1 and the current hi also works, so add hi-lo at once. Two shrinking right pointers in one pass cover both bounds.

Algorithm

1Sort arr. atMostR = atMostLm1 = 0, lim = l-1.
2For i from 0 to n-3: if arr[i]+arr[i+1]+arr[i+2] > r, break (later mins only grow).
3hiR = hiL = n-1. For lo from i+1 to n-2: shrink hiR while the sum with arr[hiR] > r, shrink hiL while > lim.
4If hiR > lo, add hiR-lo to atMostR. Same for hiL and atMostLm1.
5Return atMostR - atMostLm1.

Example Walkthrough

Input: arr = [8, 3, 5, 2], l = 7, r = 11

1. Sorted: [2, 3, 5, 8].
2. Only triplet with sum in [7, 11] is 2+3+5 = 10.
3. 2+3+8 = 13 and 3+5+8 = 16 are above 11.

Output: 1

Common Pitfalls

• Use long for three-way sums - values can be large enough to overflow int.
• The formula is <= r minus <= l-1, not < r minus < l.
• After sorting, arr[i]+arr[i+1]+arr[i+2] is non-decreasing in i, so you can stop once that min exceeds r.
• Count unordered index triples i < j < k, not permutations of the same three values.

Triplets with Sum in Range.java

Java

// Approach: After sorting, count triplets with sum <= r minus those with sum
// <= l-1. For each i, two shrinking right pointers find, for every lo, the
// largest hi with arr[i]+arr[lo]+arr[hi] within each bound. Min-triplet prune:
// later i only grow, so stop when arr[i]+arr[i+1]+arr[i+2] > r.
// Complexity: O(n^2) time and O(1) extra space.
import java.util.Arrays;

class Solution {

    public int countTriplets(int[] arr, int l, int r) {
        Arrays.sort(arr);
        int n = arr.length;
        int atMostR = 0;
        int atMostLm1 = 0;
        int lim = l - 1;

        for (int i = 0; i < n - 2; i++) {
            if ((long) arr[i] + arr[i + 1] + arr[i + 2] > r) {
                break;
            }

            int hiR = n - 1;
            int hiL = n - 1;
            for (int lo = i + 1; lo < n - 1; lo++) {
                long base = (long) arr[i] + arr[lo];
                while (hiR > lo && base + arr[hiR] > r) {
                    hiR--;
                }
                while (hiL > lo && base + arr[hiL] > lim) {
                    hiL--;
                }
                if (hiR > lo) {
                    atMostR += hiR - lo;
                }
                if (hiL > lo) {
                    atMostLm1 += hiL - lo;
                }
            }
        }

        return atMostR - atMostLm1;
    }
}

Was this solution helpful?