1498. Number of Subsequences That Satisfy the Given Sum Condition

MediumArrayTwo PointersBinary SearchSorting
Leetcode Link

Problem Description

We are given an array nums of integers and another integer target. Our goal is to compute the number of non-empty subsequences from the nums array such that the sum of the smallest and largest number in each subsequence is less than or equal to the target. Since the answer could be very large, we only require the answer modulo 10^9 + 7. It's noteworthy to mention that a subsequence does not have to consist of consecutive elements and can be formed by deleting some or no elements without changing the order of the remaining elements.

Intuition

To solve this problem, we should think about certain properties of subsequences and constraints. A critical observation is that for a given smallest element, if we can fix the largest element that would satisfy the target constraint, then all combinations of elements between the smallest and largest one will also satisfy the property (because adding elements in between will not affect the smallest and largest values of the subsequence).

So, the steps we might consider are:

  1. Sort the array to efficiently manage the smallest and largest elements.
  2. Initialize an array f to precompute the powers of 2, which represent the number of combinations of elements in between two fixed points, since those can freely be included or excluded.
  3. Iterate over the sorted array with a pointer i to find a valid smallest element.
  4. For each i, use binary search (bisect_right) to find the largest permissible element j where nums[i] + nums[j] is still not greater than target.
  5. The power of 2 at f[j - i] now tells us the count of valid subsequences between i and j because all in-between elements give us that many combinations. We use modular arithmetic for this calculation.
  6. We continue until the smallest element alone exceeds half the target, since no viable pair (as smallest + largest) will then satisfy the sum constraint.
  7. Sum all these counts to get the answer.

This approach minimizes the computation by reducing the problem to a series of binary searches and combinations (powers of 2) within the sorted bounds of the array, leveraging the property of subsequences in a sorted array.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Solution Approach

The solution primarily makes use of sorting, binary search, pre-computed powers of two, and modular arithmetic. Here is the step-by-step explanation:

  1. Sorting: The first step is to sort the nums array. Sorting is essential as it allows us to treat the first element of any subsequence we consider as the minimum and the last as the maximum. This makes it simple to enforce the constraint that the sum of the minimum and maximum elements is less than or equal to target.

  2. Precomputing Powers of Two: Before entering the main loop, we initialize an array f where f[i] is meant to store 2^i % mod. This array is filled up to n (the length of nums) plus one to account for an empty subsequence. The reason for this is that for any fixed pair of minimum and maximum, there are 2^(number of elements between them) possible subsequences including or excluding these middle elements.

  3. Main Loop: The main loop iterates over each element x in the sorted array nums. This element is sampled as a candidate for the minimum value in our subsequence.

  4. Binary Search: For each candidate minimum element, we use bisect_right from the bisect module to efficiently find the rightmost index j such that the sum of nums[i] and nums[j] is less than or equal to target. The function bisect_right(nums, target - x, i + 1) is used to find an index just beyond the largest element that can be paired with nums[i] to form a valid subsequence.

  5. Counting Valid Subsequences: After finding j, we calculate the number of valid subsequences that have nums[i] as the smallest and nums[j] as the largest element. This number is f[j - i], which is the count of all subsequences formed by the elements in between i and j. This value is added to our running total ans, using modular arithmetic to prevent overflow.

  6. Modular Arithmetic: All arithmetic operations are done modulo 10^9 + 7 (mod), as the problem statement requests the final answer to be given modulo this prime number. This ensures that intermediate results and the final answer stay within the bounds of an int and do not cause overflow.

  7. Break Condition: We can break early out of our loop when the minimum element itself is greater than half of the target. Since the array is sorted and any pair will at least double the minimum value, no subsequent pairs can have a valid sum, optimizing our solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Example Walkthrough

Let's say the nums array is [1, 2, 3, 4, 5], and the target is 7. Here's how the solution approach would be applied to this example:

  1. Sorting: First, we sort the array, but since it is already sorted [1, 2, 3, 4, 5], there's no change.

  2. Precomputing Powers of Two: Suppose we precompute powers of two modulo 10^9+7 up to n+1 where n is length of nums. Our array f for powers of 2 will look like this: [1, 2, 4, 8, 16, ...] because f[0] = 2^0 % mod, f[1] = 2^1 % mod, and so on.

  3. Main Loop: We iterate i from the start of the array. Starting with i=0, our minimum candidate value is nums[0] = 1.

  4. Binary Search: We perform a binary search to find the border j. Using bisect_right, we find the largest j such that nums[i] + nums[j] <= target. For i=0 and target=7, the largest pairable value with 1 is 5, so j=4 (index of 5).

  5. Counting Valid Subsequences: There are j - i - 1 elements between nums[i] and nums[j], which means 4 - 0 - 1 = 3 elements. Thus, there are 2^3 = 8 possible subsequences. After processing i=0, our ans is 8 % mod.

  6. Modular Arithmetic: We continue the loop and perform the same computations. As we continue, all operations are done modulo 10^9 + 7.

  7. Break Condition: We reach a point where the smallest element nums[i] is greater than half the target. Here, when i reaches 4 (nums[i]=5), we can break out of the loop, as no subsequent pairs from the sorted array will satisfy the sum condition. The loop condition saves us from going through unnecessary elements.

In the provided array, we keep picking a smallest element x (starting from 1 to 5), and for each x, we find the maximum y such that x+y <= target using binary search. Then, we calculate all possible subsequences using f[j - i]. Summing these counts gives us the total number of valid subsequences whose sum of smallest and largest numbers is less than or equal to the target.

By applying this process to the example given, we successfully count all valid subsequences while efficiently managing the constraints through sorting, binary search, and precomputed powers of two, combined with modular arithmetic to keep the numbers manageable.

Solution Implementation

1from bisect import bisect_right
2
3class Solution:
4    def numSubseq(self, nums: List[int], target: int) -> int:
5        # Constant for modulo operation
6        mod = 10**9 + 7
7        # Sort the input list to make use of binary search later
8        nums.sort()
9        n = len(nums)
10      
11        # Initialize power_of_two array which stores 2^i values modulo mod
12        power_of_two = [1] * (n + 1)
13        for i in range(1, n + 1):
14            # Efficiently precompute powers of 2 mod mod
15            power_of_two[i] = power_of_two[i - 1] * 2 % mod
16      
17        # Initialize the answer to 0
18        ans = 0
19        # Loop through the list
20        for i, num in enumerate(nums):
21            # Stop if the smallest number in a subsequence is too big
22            if num * 2 > target:
23                break
24            # Find the largest number that can be paired with nums[i]
25            # such that their sum does not exceed target.
26            j = bisect_right(nums, target - num, i + 1) - 1
27          
28            # Add the count of valid subsequences starting with nums[i]
29            # The count is the number of different ways to form subsequences 
30            # from i+1 to j (inclusive), which is simply 2 raised to the power
31            # of the number of elements between i and j, modulo mod.
32            # This relies on the fact that for every element between i and j,
33            # we can choose to either include it or not in our subsequence.
34            ans = (ans + power_of_two[j - i]) % mod
35      
36        # Return the total count of valid subsequences modulo mod
37        return ans
38
1class Solution {
2    public int numSubseq(int[] nums, int target) {
3        // Sort the input array to facilitate the two-pointer approach
4        Arrays.sort(nums);
5      
6        // Modulus value for avoiding integer overflow
7        final int MOD = (int) 1e9 + 7;
8
9        // Get the length of the nums array
10        int n = nums.length;
11
12        // Create an array to store powers of 2 mod MOD, up to n
13        int[] powersOfTwoMod = new int[n + 1];
14        powersOfTwoMod[0] = 1;
15      
16        // Precompute the powers of two modulo MOD for later use
17        for (int i = 1; i <= n; ++i) {
18            powersOfTwoMod[i] = (powersOfTwoMod[i - 1] * 2) % MOD;
19        }
20
21        // Variable to store the final answer
22        int answer = 0;
23
24        // Iterate through the numbers in the sorted array
25        for (int i = 0; i < n; ++i) {
26            // If the smallest number in the subsequence is greater than half of the target, stop the loop
27            if (nums[i] * 2L > target) {
28                break;
29            }
30
31            // Find the largest index j such that nums[i] + nums[j] <= target
32            int j = binarySearch(nums, target - nums[i], i + 1) - 1;
33
34            // Add the count of subsequences using the powers of two precomputed values
35            answer = (answer + powersOfTwoMod[j - i]) % MOD;
36        }
37
38        // Return the total number of subsequences that satisfy the condition
39        return answer;
40    }
41
42    // Helper function: binary search to find the rightmost index where nums[index] <= x
43    private int binarySearch(int[] nums, int x, int left) {
44        int right = nums.length;
45      
46        // Continue searching while the search space is valid
47        while (left < right) {
48            int mid = (left + right) >> 1; // Calculate the middle index
49
50            // Narrow the search to the left half if nums[mid] > x
51            if (nums[mid] > x) {
52                right = mid;
53            } else {
54                // Otherwise, narrow the search to the right half
55                left = mid + 1;
56            }
57        }
58
59        // Return the insertion point for x
60        return left;
61    }
62}
63
1class Solution {
2public:
3    int numSubseq(vector<int>& nums, int target) {
4        // Sort the original array to facilitate binary search
5        sort(nums.begin(), nums.end());
6
7        // Define mod as the required modulus
8        const int mod = 1e9 + 7;
9        int n = nums.size();
10      
11        // Initialize a vector for fast exponentiation
12        vector<int> fastExp(n + 1);
13        fastExp[0] = 1;
14
15        // Calculate powers of 2 modulo mod in advance
16        for (int i = 1; i <= n; ++i) {
17            fastExp[i] = (fastExp[i - 1] * 2) % mod;
18        }
19
20        int count = 0; // Initialize count of subsequences
21
22        // Iterate over the nums array to find valid subsequences
23        for (int i = 0; i < n; ++i) {
24            // If the smallest number is already greater than the target when doubled, break
25            if (nums[i] * 2L > target) {
26                break;
27            }
28
29            // Find the index of the largest number that can be paired with nums[i]
30            int j = upper_bound(nums.begin() + i + 1, nums.end(), target - nums[i]) - nums.begin() - 1;
31          
32            // Add the number of valid subsequences with nums[i] as the smallest number
33            count = (count + fastExp[j - i]) % mod;
34        }
35
36        // Return the total count of valid subsequences
37        return count;
38    }
39};
40
1// Define mod as the required modulus
2const MOD = 1e9 + 7;
3
4// Function for fast exponentiation
5const fastExponentiation = (length: number): number[] => {
6    let fastExp: number[] = new Array(length + 1).fill(1);
7    for (let i = 1; i <= length; ++i) {
8        fastExp[i] = (fastExp[i - 1] * 2) % MOD;
9    }
10    return fastExp;
11};
12
13// Function to count number of subsequences with sum of min + max <= target
14const numSubseq = (nums: number[], target: number): number => {
15    // Sort the original array to facilitate binary search
16    nums.sort((a, b) => a - b);
17  
18    const n: number = nums.length;
19    // Initialize vector for fast exponentiation
20    const fastExp = fastExponentiation(n);
21
22    let count = 0; // Initialize count of subsequences
23
24    // Iterate over the nums array to find valid subsequences
25    for (let i = 0; i < n; ++i) {
26        // If the smallest number is already greater than the target when doubled, exit loop
27        if (nums[i] * 2 > target) {
28            break;
29        }
30
31        // Find the index of the largest number that can be paired with nums[i]
32        let j = upperBound(nums, i, n, target - nums[i]) - 1;
33      
34        // Add the number of valid subsequences with nums[i] as the smallest number
35        count = (count + fastExp[j - i]) % MOD;
36    }
37
38    // Return the total count of valid subsequences
39    return count;
40};
41
42// Function that works like C++ upper_bound
43// It finds the first index in nums where nums[index] is greater than value
44const upperBound = (nums: number[], startIndex: number, length: number, value: number): number => {
45    let low = startIndex, high = length;
46    while (low < high) {
47        const mid: number = low + Math.floor((high - low) / 2);
48        if (value >= nums[mid]) {
49            low = mid + 1;
50        } else {
51            high = mid;
52        }
53    }
54    return low;
55};
56
Not Sure What to Study? Take the 2-min Quiz๏ผš

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

The given Python code aims to count the number of subsequnces in an array nums that add up to a sum less than or equal to target, with a constraint that within each subsequence, the maximum plus minimum value should not exceed target. Here's the analysis of its time complexity and space complexity:

Time Complexity

  1. nums.sort(): This line sorts the array in place which, in the worst case, has a time complexity of O(n log n), where n is the length of the array.

  2. The loop to calculate powers of 2 (f[i] = f[i - 1] * 2 % mod) runs n times, hence the time complexity for this loop is O(n).

  3. The main loop, which calculates the answer, iterates over the array once (for i, x in enumerate(nums)), which gives O(n) complexity for the loop's iteration.

  4. Inside the loop, bisect_right is used, which is an algorithm for binary search in Python, and it has a time complexity of O(log n). However, because it runs once for each element in nums, the overall complexity for this part is O(n log n).

The dominating factor in the above analyses is O(n log n). The sort operation and the binary search inside the loop both contribute to this complexity, thus the total time complexity of the function is O(n log n).

Space Complexity

  1. The space allocated for f which stores the increasing powers of 2, up to n, is O(n) since it holds n + 1 elements.

  2. No additional significant space is used, as the sorting is done in place and the other operations use constant space.

Therefore, the overall space complexity of the function is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

In a binary min heap, the minimum element can be found in:

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ