Scale Engineer

Number of Subsequences That Satisfy the Given Sum Condition

Med
#1382Time: O(N * 2^N), where N is the length of `nums`. There are `2^N` subsequences, and for each one, finding the minimum and maximum elements takes O(K) time, where K is the length of the subsequence (up to N).Space: O(N), where N is the length of `nums`. This space is used by the recursion stack and to store the current subsequence being built.1 company
Patterns
Two Pointers
Algorithms
Binary SearchSorting
Data structures
Array
Companies
Turing

Prompt

You are given an array of integers nums and an integer target.

Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal to target. Since the answer may be too large, return it modulo 109 + 7.

 

Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them do not satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 106
  • 1 <= target <= 106

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating every possible non-empty subsequence of the input array nums. For each subsequence, we find its minimum and maximum elements and check if their sum is less than or equal to the target. If the condition is met, we increment a counter. This method is the most straightforward to conceptualize but is computationally infeasible for the given constraints.

Algorithm

  • Initialize a counter count to 0.
  • Generate all non-empty subsequences of nums using a recursive or iterative approach.
  • For each generated subsequence:
    • Find its minimum element min_val and maximum element max_val.
    • If min_val + max_val <= target, increment count.
  • Return count modulo 10^9 + 7.

Walkthrough

The core idea is to explore all possibilities. We can write a recursive function that, at each step, decides whether to include the current element in the subsequence or not. This builds a decision tree that covers all 2^n possible subsequences. For each complete subsequence, we then perform a check.

// This is a conceptual implementation and will time out.class Solution {    int count = 0;    int target;    int[] nums;    final int MOD = 1_000_000_007;     public int numSubseq(int[] nums, int target) {        this.target = target;        this.nums = nums;        generateSubsequences(0, new java.util.ArrayList<>());        return count;    }     private void generateSubsequences(int index, java.util.List<Integer> current) {        if (index == nums.length) {            if (!current.isEmpty()) {                int min = Integer.MAX_VALUE;                int max = Integer.MIN_VALUE;                for (int num : current) {                    min = Math.min(min, num);                    max = Math.max(max, num);                }                if (min + max <= target) {                    count = (count + 1) % MOD;                }            }            return;        }         // Decision 1: Exclude nums[index]        generateSubsequences(index + 1, current);         // Decision 2: Include nums[index]        current.add(nums[index]);        generateSubsequences(index + 1, current);        current.remove(current.size() - 1); // Backtrack    }}

This method is too slow because the number of subsequences grows exponentially with the size of the input array nums.

Complexity

Time

O(N * 2^N), where N is the length of `nums`. There are `2^N` subsequences, and for each one, finding the minimum and maximum elements takes O(K) time, where K is the length of the subsequence (up to N).

Space

O(N), where N is the length of `nums`. This space is used by the recursion stack and to store the current subsequence being built.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' error on any reasonably sized input.

Solutions

class Solution {public  int numSubseq(int[] nums, int target) {    Arrays.sort(nums);    final int mod = (int)1 e9 + 7;    int n = nums.length;    int[] f = new int[n + 1];    f[0] = 1;    for (int i = 1; i <= n; ++i) {      f[i] = (f[i - 1] * 2) % mod;    }    int ans = 0;    for (int i = 0; i < n; ++i) {      if (nums[i] * 2L > target) {        break;      }      int j = search(nums, target - nums[i], i + 1) - 1;      ans = (ans + f[j - i]) % mod;    }    return ans;  }private  int search(int[] nums, int x, int left) {    int right = nums.length;    while (left < right) {      int mid = (left + right) >> 1;      if (nums[mid] > x) {        right = mid;      } else {        left = mid + 1;      }    }    return left;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem