{x}
blog image

Number of Subsequences That Satisfy the Given Sum Condition

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

Solution Explanation

This problem asks to find the number of non-empty subsequences of a given array nums where the sum of the minimum and maximum elements in the subsequence is less than or equal to a given target. The solution uses a two-pointer approach combined with binary search (or its equivalent) for efficient computation.

Approach:

  1. Sort: The input array nums is sorted in ascending order. This is crucial for efficiently finding subsequences that meet the criteria.

  2. Precompute Powers of 2: An array f is precomputed where f[i] stores 2i modulo 109 + 7. This is because for each element, we need to consider all possible subsequences that include it. The number of subsequences that can be formed using i elements is 2i.

  3. Two-Pointer Iteration: The code iterates through the sorted array using i as a pointer. For each element nums[i], it performs the following:

    • Check Condition: It checks if 2 * nums[i] is greater than target. If it is, then no subsequence starting from nums[i] can satisfy the condition (since the minimum and maximum would both be at least nums[i]), so it breaks the loop.

    • Binary Search (or equivalent): It finds the index j such that nums[j] is the largest element which satisfies nums[i] + nums[j] <= target. Binary search (or upper_bound in C++ and bisect_right in Python) is used for efficient searching.

    • Count Subsequences: The number of subsequences that can be formed using elements from nums[i] to nums[j] (inclusive) is 2(j-i). This is calculated using f[j - i].

    • Update Result: The count is added to the ans variable, which accumulates the total count modulo 109 + 7.

Time Complexity: O(N log N), where N is the length of nums. Sorting takes O(N log N) time. The loop iterates through the sorted array once, and the binary search (or its equivalent) within the loop takes O(log N) time, leading to an overall time complexity of O(N log N).

Space Complexity: O(N) The space complexity comes from the array f used to store the precomputed powers of 2, and potentially the space used for sorting depending on the sorting algorithm used.

Code Explanation (Python):

The Python code utilizes bisect_right from the bisect module, which efficiently finds the rightmost insertion point of a value in a sorted array. This is equivalent to binary search for finding the largest index j satisfying the condition. The rest of the logic follows the approach described above.

Code Explanation (Java & C++):

The Java and C++ codes use Arrays.binarySearch or upper_bound (a standard library function for efficient searching in sorted ranges) respectively to perform the same binary search operation as Python's bisect_right.

Code Explanation (Go):

The Go code uses sort.SearchInts which is Go's built-in binary search function to efficiently search for the index j. The rest of the algorithm is the same as in other languages.