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

1
2
3
4
5
6
7

Input: nums = [1,1]
Output: 2
Explanation: 
The two possible ways are:
The class teacher selects no student.
The class teacher selects both students to form the group. 
If the class teacher selects just one student to form a group then the both students will not be happy. Therefore, there are only two possible ways.

Example 2

1
2
3
4
5
6
7

Input: nums = [6,0,3,3,6,7,2,7]
Output: 3
Explanation: 
The three possible ways are:
The class teacher selects the student with index = 1 to form the group.
The class teacher selects the students with index = 1, 2, 3, 6 to form the group.
The class teacher selects all the students to form the group.

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

  1. Sort nums.
  2. 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].
  3. Count all valid k.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import java.util.*;
class Solution {
    public int countWays(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, ans = 0;
        if (nums[0] > 0) ans++;
        for (int k = 1; k < n; ++k) {
            if (nums[k-1] < k && k < nums[k]) ans++;
        }
        if (nums[n-1] < n) ans++;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def countWays(nums):
    nums.sort()
    n = len(nums)
    ans = 0
    if nums[0] > 0:
        ans += 1
    for k in range(1, n):
        if nums[k-1] < k < nums[k]:
            ans += 1
    if nums[-1] < n:
        ans += 1
    return ans

Complexity

  • ⏰ Time complexity: O(n log n) (sorting dominates)
  • 🧺 Space complexity: O(1) (in-place sort)