Problem
You are given a 0-indexed integer array nums
of length n
where n
is the total number of students in the class. The class teacher tries to select a group of students so that all the students remain happy.
The ith
student will become happy if one of these two conditions is met:
- The student is selected and the total number of selected students isstrictly greater than
nums[i]
. - The student is not selected and the total number of selected students is strictly less than
nums[i]
.
Return the number of ways to select a group of students so that everyone remains happy.
Examples
Example 1
|
|
Example 2
|
|
Constraints
1 <= nums.length <= 10^5
0 <= nums[i] < nums.length
Solution
Method 1 – Sort and Count Valid Group Sizes
Intuition
Sort the array. For each possible group size k (from 0 to n), check if all students are happy: those selected (k students) must have k > nums[i], and those not selected (n-k students) must have k < nums[i].
Approach
- Sort nums.
- For k = 0 to n, check:
- If k == 0: all nums[i] > 0 (since no one is selected).
- If k == n: all nums[i] < n (since all are selected).
- For 0 < k < n: nums[k-1] < k < nums[k].
- Count all valid k.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n log n)
(sorting dominates) - 🧺 Space complexity:
O(1)
(in-place sort)