Count Subsequences by Minimum and Maximum

Interview Problem Interview Medium Two Pointers Array Modular Arithmetic

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.numSubseq(nums, target). Return the number of non-empty subsequences whose minimum plus maximum is at most target, modulo 1_000_000_007.

Starter code

class Solution:
    def numSubseq(self, nums, target):
        pass

Test cases

simple

{
  "args": [
    [
      3,
      5,
      6,
      7
    ],
    9
  ]
}

Expected: 4

Wizard outline

Step 1: Initialize Solution.numSubseq
Replace the empty starter with the first real state owned by Solution.numSubseq. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Single Valid case
Complete the readable core algorithm for one representative Interview case. After sorting, fix the minimum and count every subset of eligible middle values as a power of two.
Step 4: Harden the Simple boundary
Repair the reviewed boundary and pass the complete submission contract. For a fitting pair, every selection between left and right with left included has minimum nums[left] and maximum no larger than nums[right], so all are valid and counted once by their smallest selected index. If the pair fails, nums[right] cannot pair with the current or any larger minimum.

Footguns and prerequisites

The problem counts subsequences by chosen indices, so duplicate values can contribute distinct choices.
arrays strings two pointers sliding window
operators and expressions

Reviewed references

LeetCode 1498 — Number of Subsequences That Satisfy the Given Sum Condition

Practice prerequisites

Discard Pairs with Two Pointers(opens in a new tab)
Discard Pairs with Two Pointers isolates every pair outside [left, right] has already been counted or proven too large, and no unresolved pair is skipped. That focused state discipline is required when implementing subsequences min max target as a complete Interview Problem.

Recommended approach and implementation

Sort values and use left/right. When nums[left]+nums[right] fits, count all 2^(right-left) subsequences that include left and choose any subset between; otherwise decrement right.

Why it works: For a fitting pair, every selection between left and right with left included has minimum nums[left] and maximum no larger than nums[right], so all are valid and counted once by their smallest selected index. If the pair fails, nums[right] cannot pair with the current or any larger minimum.

class Solution:
    def numSubseq(self, nums, target):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        modulus = 1_000_000_007
        nums.sort()
        powers = [1] * len(nums)
        for index in range(1, len(nums)):
            powers[index] = powers[index - 1] * 2 % modulus
        left, right = 0, len(nums) - 1
        total = 0
        while left <= right:
            if nums[left] + nums[right] <= target:
                total = (total + powers[right - left]) % modulus
                left += 1
            else:
                right -= 1
        return total