2554. Maximum Number of Integers to Choose From a Range I
Approach
HashSet for banned; accumulate integers 1..n skipping banned until maxSum exceeded.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
Binary search reduces search space by half each step, giving O(log n) time. Beyond sorted arrays, apply it on the answer space ("binary search on result") when you can define a monotonic predicate — e.g., "can we achieve X with k resources?"
// Approach: HashSet for banned; accumulate integers 1..n skipping banned until maxSum exceeded.
// Time: O(n) Space: O(banned)
public class Solution
{
public int MaxCount(int[] banned, int n, int maxSum)
{
int answerCount = 0;
int currentSum = 0;
HashSet<int> bannedNumberSet = new HashSet<int>(banned);
for (int currentNumber = 1; currentNumber <= n; ++currentNumber)
{
if (!bannedNumberSet.Contains(currentNumber) && currentSum + currentNumber <= maxSum)
{
++answerCount;
currentSum += currentNumber;
}
}
return answerCount;
}
}