Maximum Number of Integers to Choose From a Range I

MediumArrayHash TableBinary SearchGreedySorting

Solution

export function maxCount(banned: number[], n: number, maxSum: number): number {
  const set = new Set(banned);
 
  let answer = 0;
  let [num, sum] = [1, 0];
  while (num <= n && sum + num <= maxSum) {
    if (!set.has(num)) {
      sum += num;
      answer += 1;
    }
    num += 1;
  }
  return answer;
}

Complexity

  • Time: O(m+n)O(m + n)
  • Space: O(m)O(m)