2557. Maximum Number of Integers to Choose From a Range II

MediumGreedyArrayBinary SearchSorting
Leetcode Link

Problem Description

We are given an integer array banned, a positive integer n indicating the upper limit of an integer range starting from 1, and a positive integer maxSum which serves as the cap for the sum of integers we can select. The task is to choose a collection of distinct integers within this range from 1 to n, ensuring two conditions: first, that none of the integers are present in the banned array, and second, that the cumulative sum of all chosen integers does not exceed maxSum. The objective is to maximize the number of integers chosen while adhering to the stated constraints.

Intuition

To maximize the number of chosen integers, while considering the maxSum limitation and banned list, we must take a strategic approach in picking the integers. A naive approach might be to start from 1 and keep adding the next non-banned integer until we reach or exceed maxSum. However, this might not optimize for the maximum number of integers since larger values will use up the allowed sum more quickly.

Instead, the intuition is to proceed in a way that we try to include as many small non-banned numbers as possible because smaller numbers have smaller sums, enabling us to pick more numbers while staying under maxSum.

We can achieve this by:

  • Extending the banned list with two sentinel values, 0 and n+1, which represent the lower and upper boundaries beyond which we can't select integers.
  • Sorting the extended banned list to be able to iterate through banned ranges efficiently.
  • Using binary search to find the maximum count of integers that can be selected between each pair of consecutive banned numbers, without exceeding maxSum.

This can be seen in the provided solution code where the banned list is augmented and then sorted. The pairwise function (assumed to be similar to itertools.pairwise) iterates through adjacent elements providing pairs of banned integers so we can calculate the potential numbers between them.

The binary search within the loop efficiently finds the maximum number of selectable integers in each range. If adding one more integer exceeds maxSum, the binary search moves left, else it moves right to expand the count. Once the range is found, we add it to the ans tally and deduct the sum of those integers from maxSum to ensure we don't exceed the overall allowed sum.

The answer is returned as soon as maxSum is not enough to add more integers, guaranteeing the focus on maximizing quantity with the smallest possible numbers while adhering to maxSum.

Learn more about Greedy, Binary Search and Sorting patterns.

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

Depth first search is equivalent to which of the tree traversal order?

Solution Approach

The code below implements a strategic method to solve the problem by maximizing the number of integers chosen within the given constraints. Here's a deeper dive into the solution's methodology:

First, the solution uses both the concept of sorting and binary search, combining these algorithms for efficient computation. The banned list is modified to include two extra elements, 0 and n + 1, to handle edge cases seamlessly.

The data structures used include:

  • A list (banned) that contains the original banned numbers plus the two sentinels (0 and n + 1).
  • A set, to ensure all elements in banned are unique.
  • A sorted list version of that set, to allow for binary search operations.

The code then traverses the sorted banned list, searching for the maximum number of selectable integers between each pair of consecutive banned numbers (now including the sentinels). This is done using the pairwise iteration which is assumed to yield a tuple (i, j) where i and j are adjacent banned numbers.

For each pair (i, j), the algorithm finds the potential gap (j - i - 1) between them to determine the number of selectable integers. It then employs binary search within this gap to find the maximum count of integers (left) which can be chosen without exceeding maxSum. The binary search checks if the sum of an arithmetic series from i + 1 to i + mid is less than or equal to maxSum.

The arithmetic series sum is calculated with the formula:

1(i + 1 + i + mid) * mid / 2

This sum formula computes the sum of the first mid terms of the natural numbers starting at i + 1.

After finding the left value for each range, the algorithm updates the answer (ans) with the count of new integers added, and subtracts the sum of those integers from maxSum.

The process stops when maxSum becomes zero or negative, indicating that no additional integers can be chosen without exceeding the maximum sum constraint at which point the current value of ans is returned.

Through this approach, the solution efficiently maximizes the number of integers chosen without exceeding maxSum and while respecting the banned list.

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

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Example Walkthrough

Let's consider an example to illustrate the solution approach.

Suppose we are given the following parameters:

  • banned = [3, 6, 10]
  • n = 15
  • maxSum = 25

Now, let's use the solution approach step by step:

  1. Extend and Sort the banned List: The banned array is extended to include two sentinel values, which here would be 0 and n+1 = 16. After including these, the banned array is sorted. The updated banned list looks like this: [0, 3, 6, 10, 16].

  2. Iterate Using Pairwise: Using the pairwise function, we obtain the adjacent pairs of banned numbers: (0, 3), (3, 6), (6, 10), and (10, 16).

  3. Binary Search on Each Range: For each pair (i, j), we perform a binary search to find the maximum count of integers that can be selected between i+1 and j-1 without exceeding maxSum. Here's how it works for each pair:

    • For (0, 3), the selectable range is 1 and 2. Since the sum 1 + 2 is 3, which is less than maxSum, we include both numbers. Now, maxSum is reduced to 22.

    • For (3, 6), the selectable range is 4 and 5. The sum 4 + 5 is 9, which is within the remaining maxSum of 22. We include these, and maxSum reduces to 13.

    • Next, for (6, 10), the selectable range is 7, 8, and 9. The binary search finds that we can only take 7 and 8 without exceeding the new maxSum of 13, because their sum is 15, and adding 9 would bring the total to 24, over the cap. So we add 7 and 8 and reduce maxSum to 13 - (7 + 8) = -2. Now maxSum is negative.

    • At this point, we cannot choose any more numbers because the remaining maxSum is not enough to include more integers. We stop and do not proceed to the pair (10, 16).

  4. End Result: The maximum number of integers chosen without exceeding maxSum and avoiding the banned list is [1, 2, 4, 5, 7, 8]. The ans would be 6, which is the count of these chosen integers.

This example walk-through demonstrates how the problem is solved using the described approach, ensuring that we maximize the number of integers chosen within the constraints.

Solution Implementation

1class Solution:
2    def maxCount(self, banned: List[int], n: int, maxSum: int) -> int:
3        # Extend the banned list to include 0 and n+1 to simplify range calculations
4        banned.extend([0, n + 1])
5        # Ensure the banned list is unique and sorted
6        banned = sorted(set(banned))
7      
8        # Initialize the answer to 0
9        answer = 0
10      
11        # Loop through each pair of consecutive banned numbers (Using pairwise requires itertools in Python 3.8+)
12        for lower_bound, upper_bound in zip(banned, banned[1:]):
13            # We use binary search to find the maximum count of numbers
14            # between a pair of banned numbers that we can sum without exceeding maxSum
15            left, right = 0, upper_bound - lower_bound - 1
16          
17            while left < right:
18                # Calculate the midpoint for binary search
19                mid = (left + right + 1) // 2
20              
21                # Calculate the sum of an arithmetic series from lower_bound+1 to lower_bound+mid
22                if ((lower_bound + 1 + lower_bound + mid) * mid) // 2 <= maxSum:
23                    # If the sum is less than or equal to maxSum, move the left bound up
24                    left = mid
25                else:
26                    # Otherwise, move the right bound down
27                    right = mid - 1
28          
29            # Add the count of numbers found to the answer
30            answer += left
31            # Decrease maxSum by the sum of numbers we've added to the answer
32            maxSum -= ((lower_bound + 1 + lower_bound + left) * left) // 2
33          
34            # If maxSum becomes zero or negative, we cannot add any more numbers
35            if maxSum <= 0:
36                break
37      
38        # Return the total count of numbers we can sum
39        return answer
40
1class Solution {
2    // Method to calculate the maximum count of consecutive numbers not exceeding maxSum
3    // with the given constraints.
4    public int maxCount(int[] banned, int n, long maxSum) {
5        // Create a hash set to store banned numbers along with the boundaries.
6        Set<Integer> bannedIndicesSet = new HashSet<>();
7        bannedIndicesSet.add(0);        // Add lower boundary
8        bannedIndicesSet.add(n + 1);    // Add upper boundary
9      
10        // Add all banned numbers to the set
11        for (int bannedNumber : banned) {
12            bannedIndicesSet.add(bannedNumber);
13        }
14      
15        // Convert the set to a list and sort it to process intervals between banned numbers.
16        List<Integer> bannedIndicesList = new ArrayList<>(bannedIndicesSet);
17        Collections.sort(bannedIndicesList);
18      
19        // Initialize the answer which will store the maximum count of consecutive numbers
20        int maxCount = 0;
21      
22        for (int k = 1; k < bannedIndicesList.size(); ++k) {
23            // Get the interval boundaries from the sorted list
24            int intervalStart = bannedIndicesList.get(k - 1);
25            int intervalEnd = bannedIndicesList.get(k);
26          
27            // Initialize binary search bounds
28            int left = 0;
29            int right = intervalEnd - intervalStart - 1;
30          
31            while (left < right) {
32                // Use unsigned right shift for division by 2 to avoid negative overflow
33                int mid = (left + right + 1) >>> 1;
34              
35                // Check if the sum of consecutive numbers from intervalStart+1 to intervalStart+mid
36                // fits in the maxSum using the arithmetic progression sum formula
37                if ((intervalStart + 1 + intervalStart + mid) * 1L * mid / 2 <= maxSum) {
38                    left = mid;
39                } else {
40                    right = mid - 1;
41                }
42            }
43          
44            // Update maxCount and decrease maxSum by the sum of consecutive numbers found
45            maxCount += left;
46            maxSum -= (intervalStart + 1 + intervalStart + left) * 1L * left / 2;
47          
48            // If maxSum is exhausted, break out of the loop
49            if (maxSum <= 0) {
50                break;
51            }
52        }
53      
54        // Return the calculated maximum count
55        return maxCount;
56    }
57}
58
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // This function calculates the maximum count of numbers that can be added
7    // to the intervals between banned numbers without exceeding maxSum.
8    int maxCount(std::vector<int>& banned, int n, long long maxSum) {
9        // Add boundary markers for the start and end of possible number range.
10        banned.push_back(0);           // Add a banned number at the start.
11        banned.push_back(n + 1);       // Add a banned number at the end.
12      
13        // Sort the banned numbers to process them in order.
14        std::sort(banned.begin(), banned.end());
15      
16        // Remove duplicate entries if any, to handle only unique banned numbers.
17        banned.erase(std::unique(banned.begin(), banned.end()), banned.end());
18      
19        int answer = 0;  // Initialize the answer to zero.
20      
21        // Iterate through the intervals between banned numbers.
22        for (int index = 1; index < banned.size(); ++index) {
23            int start = banned[index - 1], end = banned[index];
24            int low = 0, high = end - start - 1;  // Low and high limits for current interval.
25          
26            // Perform binary search within the interval to find the max count.
27            while (low < high) {
28                int mid = low + ((high - low + 1) / 2);
29                // Calculate the sum of arithmetic progression.
30                if ((start + 1 + start + mid) * 1LL * mid / 2 <= maxSum) {
31                    low = mid;  // If the sum is within limit, search right side.
32                } else {
33                    high = mid - 1;  // If sum exceeds limit, search left side.
34                }
35            }
36          
37            answer += low;  // Add the found count to the answer.
38            // Subtract the sum of the found numbers from maxSum.
39            maxSum -= (start + 1 + start + low) * 1LL * low / 2;
40          
41            if (maxSum <= 0) {  // If there's no sum left to add numbers, break out.
42                break;
43            }
44        }
45      
46        return answer;  // Return the total count of numbers that can be added.
47    }
48};
49
1function maxCount(banned: number[], n: number, maxSum: number): number {
2  // Add boundary markers for the start and end of the possible number range.
3  banned.push(0);        // Add a banned number at the start.
4  banned.push(n + 1);    // Add a banned number at the end.
5
6  // Sort the banned numbers to process them in order.
7  banned.sort((a, b) => a - b);
8
9  // Remove duplicate entries if any, to handle only unique banned numbers.
10  banned = Array.from(new Set(banned));
11
12  let answer = 0;  // Initialize the answer to zero.
13
14  // Iterate through the intervals between banned numbers.
15  for (let index = 1; index < banned.length; ++index) {
16      let start = banned[index - 1], end = banned[index];
17      let low = 0, high = end - start - 1;  // Low and high limits for the current interval.
18
19      // Perform binary search within the interval to find the max count.
20      while (low < high) {
21          let mid = low + Math.floor((high - low + 1) / 2);
22          // Calculate the sum of the arithmetic progression.
23          if ((start + 1 + start + mid) * mid / 2 <= maxSum) {
24              low = mid;  // If the sum is within the limit, search the right side.
25          } else {
26              high = mid - 1;  // If sum exceeds the limit, search the left side.
27          }
28      }
29
30      answer += low;  // Add the found count to the answer.
31      // Subtract the sum of the found numbers from maxSum.
32      maxSum -= (start + 1 + start + low) * low / 2;
33
34      if (maxSum <= 0) {  // If there's no sum left to add numbers, break out.
35          break;
36      }
37  }
38
39  return answer;  // Return the total count of numbers that can be added.
40}
41
42// Example usage:
43// let bannedNumbers = [3, 6, 14];
44// let n = 15;
45// let maxSum = 25;
46// console.log(maxCount(bannedNumbers, n, maxSum)); // Should print the result of the function.
47
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following uses divide and conquer strategy?

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by mainly two operations: sorting the banned list and performing a binary search for each pair in the list after incorporating the additional elements and removing duplicates.

  1. Sorting the banned list has a time complexity of O(K * log(K)), where K is the number of elements in the banned list after extending it with [0, n + 1]. Since ban is constructed by converting banned to a set and sorting, the number of elements K is at most the original length of banned plus 2.

  2. The pairwise function results in O(K - 1) iterations since it will create pairs of adjacent elements in the sorted ban list.

  3. For each pair (i, j) produced by pairwise, there is a binary search running to determine how many integers can be counted between i and j without exceeding maxSum. The binary search runs in O(log(N)) time in the worst case, where N is the difference (j - i - 1).

Therefore, if M is the maximum value in the list before sorting (and after adding 0 and n + 1), then the worst-case scenario for the binary search is O(log(M)) time for each of K - 1 iterations.

Combining these, the total time complexity is O(K * log(K) + (K - 1) * log(M)) = O(K * log(K) + K * log(M)). Since K can be at most n + 2, the time complexity in terms of n is O((n + 2) * log(n + 2) + (n + 1) * log(n)).

Space Complexity

The space complexity of the code involves the additional space used by the ban list and the space for the variables used in the binary search.

  1. The ban list stores at most K elements, which is at most the length of banned plus 2, thus giving us a space complexity of O(K).

  2. The variables used in the binary search (left, right, mid, ans, and maxSum) require constant space O(1).

Therefore, the space complexity of the algorithm is O(K). This is O(n) in terms of the maximum possible length of the ban list when n is large compared to the number of banned elements.

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

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

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 ๐Ÿ‘จโ€๐Ÿซ