Subsequences With Min + Max ≤ Target: Two Pointers

You're given an array of positive integers nums and an integer target, and you have to count the non-empty subsequences of nums where the smallest value plus the largest value is at most target. Two subsequences that pick the same values from different places both count, since it's the positions that tell them apart. The answer can get huge so you return it modulo 10⁹ + 7.

Examples

Input	Output	Why
`nums = [3, 5, 6, 7], target = 9`	`4`	You get [3], [3, 5], [3, 6] and [3, 5, 6], and something like [5] on its own doesn't work because 5 + 5 is 10.
`nums = [3, 3, 6, 8], target = 10`	`6`	Each 3 on its own and with the 6, so that's four, and then both 3's together, with or without the 6.
`nums = [2, 3, 3, 4, 6, 7], target = 12`	`61`	There are 63 non-empty subsequences in all, and only [6, 7] and [7] go over.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶
1 ≤ target ≤ 10⁶

Hints

Hint 1

A subsequence only cares about which positions it picks, and the condition only cares about its min and max. So does the order of the array matter at all here?

Hint 2

It doesn't, so you can sort it. Now fix lo as the smallest element you'll use. If nums[lo] + nums[hi] ≤ target, how many subsequences have nums[lo] as their minimum and nothing past hi?

Hint 3

Every subset of the hi − lo elements after lo can come along, since they're all between nums[lo] and nums[hi]. That's 2^(hi − lo) of them. Add that and move lo up, or move hi down when the sum's too big.

Where people lose marks

Working out 2^(hi − lo) with a shift or a float, which I've seen quite a few times. It'll overflow long before n gets anywhere near 10⁵, so you'd build the table mod 10⁹ + 7 as you go.
Stopping the loop when lo = hi, because nums[lo] on its own is still a subsequence if 2 × nums[lo] ≤ target and you'd miss it. The loop has to run while lo ≤ hi.
Worrying that the sort breaks the subsequences. I wouldn't, since all it does is relabel the positions and the number of sets of positions with a given min and max stays the same.

Dry run on `[3,5,6,7],9`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 6

Step 1 / 6

nums
30lo516273hi
count0
I'd sort it first, so it's 3, 5, 6, 7, and you're counting with a target of 9.
Step 2 / 6

nums
30lo516273hi
count0
3 + 7 = 10 is over 9. Even with the smallest value left 7 doesn't fit, so hi comes down.
Step 3 / 6

nums
30lo5162hi73
count4
3 + 6 fits, so 3 goes with any subset of the 2 values after it up to hi. That's 2^2 = 4 more and lo moves up.
Step 4 / 6

nums
3051lo62hi73
count4
5 + 6 = 11 is over 9. Even with the smallest value left 6 doesn't fit, so hi comes down.
Step 5 / 6

nums
3051lo/hi6273
count4
5 + 5 = 10 is over 9. Even with the smallest value left 5 doesn't fit, so hi comes down.
Step 6 / 6

nums
30516273
count4
lo has passed hi and the count is 4.

How to think about it

Trying every subsequence is O(2ⁿ), so that's out. The thing to notice first is that the condition only looks at the smallest and largest values, and a subsequence is just a set of positions, so the order of the array doesn't matter and you can sort it.

After the sort I'd put lo at the start and hi at the end and count the subsequences whose smallest element is nums[lo]. If nums[lo] + nums[hi] ≤ target then you can take nums[lo] together with any subset at all of positions lo + 1, …, hi, because whatever you pick, the max is at most nums[hi]. That's 2^(hi − lo) subsequences, and then lo moves up. If the sum's too big then nums[hi] can't be in anything with the smallest value that's left, so hi comes down.

You'll want the powers of two ready in an array taken mod 10⁹ + 7, because 2^(10⁵) is far too big for any integer type. The sort's O(n log n) and the scan is O(n).

Complexity. Time O(n log n) · Space O(n) for the powers of two

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def num_subseq(nums, target):
    MOD = 10**9 + 7
    a = sorted(nums)
    n = len(a)
    pow2 = [1] * n
    for i in range(1, n):
        pow2[i] = pow2[i - 1] * 2 % MOD
    lo, hi, count = 0, n - 1, 0
    while lo <= hi:
        if a[lo] + a[hi] <= target:
            count = (count + pow2[hi - lo]) % MOD   # any subset of lo+1..hi goes with a[lo]
            lo += 1
        else:
            hi -= 1
    return count

#include <vector>
#include <algorithm>

long long solve(std::vector<int> a, int target) {
    const long long MOD = 1000000007;
    std::sort(a.begin(), a.end());
    int n = (int)a.size();
    std::vector<long long> pow2(n, 1);
    for (int i = 1; i < n; ++i) pow2[i] = pow2[i - 1] * 2 % MOD;
    int lo = 0, hi = n - 1;
    long long count = 0;
    while (lo <= hi) {
        if (a[lo] + a[hi] <= target) { count = (count + pow2[hi - lo]) % MOD; ++lo; }   // any subset of lo+1..hi goes with a[lo]
        else --hi;
    }
    return count;
}

import java.util.Arrays;

class Solution {
    public int numSubseq(int[] nums, int target) {
        final int MOD = 1_000_000_007;
        int[] a = nums.clone();
        Arrays.sort(a);
        int n = a.length;
        int[] pow2 = new int[n];
        pow2[0] = 1;
        for (int i = 1; i < n; i++) pow2[i] = (int) (pow2[i - 1] * 2L % MOD);
        int lo = 0, hi = n - 1, count = 0;
        while (lo <= hi) {
            if (a[lo] + a[hi] <= target) { count = (count + pow2[hi - lo]) % MOD; lo++; }   // any subset of lo+1..hi goes with a[lo]
            else hi--;
        }
        return count;
    }
}

function numSubseq(nums, target) {
  const MOD = 1000000007, a = nums.slice().sort((x, y) => x - y), n = a.length;
  const pow2 = new Array(n).fill(1);
  for (let i = 1; i < n; i++) pow2[i] = pow2[i - 1] * 2 % MOD;
  let lo = 0, hi = n - 1, count = 0;
  while (lo <= hi) {
    if (a[lo] + a[hi] <= target) { count = (count + pow2[hi - lo]) % MOD; lo++; }   // any subset of lo+1..hi goes with a[lo]
    else hi--;
  }
  return count;
}

fn solve(nums: &[i64], target: i64) -> i64 {
    const MOD: i64 = 1_000_000_007;
    let mut a = nums.to_vec();
    a.sort();
    let n = a.len();
    let mut pow2 = vec![1i64; n];
    for i in 1..n { pow2[i] = pow2[i - 1] * 2 % MOD; }
    let (mut lo, mut hi) = (0i64, n as i64 - 1);
    let mut count = 0i64;
    while lo <= hi {
        if a[lo as usize] + a[hi as usize] <= target {
            count = (count + pow2[(hi - lo) as usize]) % MOD;   // any subset of lo+1..hi goes with a[lo]
            lo += 1;
        } else { hi -= 1; }
    }
    count
}

import Data.Array
import Data.List (sort)

solve :: [Int] -> Int -> Int
solve nums target = go 0 (n - 1) 0
  where
    md = 1000000007
    n = length nums
    a = listArray (0, n - 1) (sort nums)
    pow2 = listArray (0, n) (iterate (\x -> x * 2 `mod` md) 1) :: Array Int Int
    go lo hi acc
      | lo > hi                  = acc
      | a ! lo + a ! hi <= target = go (lo + 1) hi ((acc + pow2 ! (hi - lo)) `mod` md)   -- any subset of lo+1..hi goes with a ! lo
      | otherwise                = go lo (hi - 1) acc

Variants to try

If you're asked to count the subsequences where max − min ≤ k you'd do the same sort, and then it's a window with a pointer that only ever moves forward.
If you're asked for the sum of max − min over every subsequence, you'll find that after sorting nums[i] is the max of 2^i of them and the min of 2^(n−1−i), so one pass is enough.

Next problems

Easy10 min

Subsequences whose smallest and largest fit a target

Examples

Constraints

Hints

Where people lose marks

Dry run on `[3,5,6,7],9`

How to think about it

The solution, in six languages

Variants to try

Next problems

Pair with a given sum in a sorted array

Count the pairs whose sum is below a target

A palindrome, ignoring punctuation and case

Keep going

Pair with a given sum in a sorted array

Count the pairs whose sum is below a target

A palindrome, ignoring punctuation and case

The pattern behind it

Subsequences whose smallest and largest fit a target

Examples

Constraints

Hints

Where people lose marks

Dry run on [3,5,6,7],9

How to think about it

The solution, in six languages

Variants to try

Next problems

Pair with a given sum in a sorted array

Count the pairs whose sum is below a target

A palindrome, ignoring punctuation and case

Keep going

Pair with a given sum in a sorted array

Count the pairs whose sum is below a target

A palindrome, ignoring punctuation and case

The pattern behind it

Dry run on `[3,5,6,7],9`