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

class Solution {
public:
    int countWays(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        sort(nums.begin(), nums.end());
        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
13
14
15
16
17

import "sort"
func countWays(nums []int) int {
    n, ans := len(nums), 0
    sort.Ints(nums)
    if nums[0] > 0 {
        ans++
    }
    for 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
13

import java.util.*;
class Solution {
    public int countWays(int[] nums) {
        int n = nums.length, ans = 0;
        Arrays.sort(nums);
        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
13

class Solution {
    fun countWays(nums: IntArray): Int {
        val n = nums.size
        nums.sort()
        var ans = 0
        if (nums[0] > 0) ans++
        for (k in 1 until n) {
            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
13

class Solution:
    def countWays(self, nums: list[int]) -> int:
        n = len(nums)
        nums.sort()
        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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

struct Solution;
impl Solution {
    pub fn count_ways(nums: Vec<i32>) -> i32 {
        let mut nums = nums;
        nums.sort();
        let n = nums.len();
        let mut ans = 0;
        if nums[0] > 0 { ans += 1; }
        for k in 1..n {
            if nums[k-1] < k as i32 && k as i32 < nums[k] {
                ans += 1;
            }
        }
        if nums[n-1] < n as i32 { ans += 1; }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    countWays(nums: number[]): number {
        nums.sort((a, b) => a - b);
        const n = nums.length;
        let ans = 0;
        if (nums[0] > 0) ans++;
        for (let k = 1; k < n; ++k) {
            if (nums[k-1] < k && k < nums[k]) ans++;
        }
        if (nums[n-1] < n) ans++;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), due to sorting.
  • 🧺 Space complexity: O(1) (ignoring sort space), as only a few variables are used.