Leetcode # 2860. Happy Students

Problem

https://leetcode.com/contest/weekly-contest-363/problems/happy-students/

1. if i ∈ selected ∧ len(selected) > nums[i] => i^th student is happy
2. if i ∉ selected ∧ len(selected) < nums[i] => i^th student is happy

Solution

將 nums 排序
selected := nums[:k + 1] ⇒ is_not_selected ← nums[k + 1:]
尋找滿足「max(selected) == nums[k] < len(selected) == k + 1
且 min(is_not_selected) == nums[k + 1] > len(selected) == k + 1」
≡「nums[k] < k + 1 且 nums[k + 1] > k + 1」的 k 有多少
※ 當 k == len(nums) – 1 時，is_not_selected ← ∅
⇒ 條件2 恆成立

Time Complexity: O(n * log(n) + n) = O(n * log(n))
Space Complexity: O(n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def countWays(self, nums: List[int]) -> int:
    nums.sort()
    return (1 if nums[0] > 0 else 0) + sum(1 for k in range(len(nums)) if nums[i] < k + 1 and (k == len(nums) - 1 or nums[k + 1] > k + 1))

Last Updated on 2023/09/19 by A1go