# Happy Students
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/happy-students)
Canonical: https://scaleengineer.com/dsa/problems/happy-students
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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 is **strictly 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._

**Example 1:**

**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:**

**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 <= 105`
* `0 <= nums[i] < nums.length`

# Approaches
## Brute Force by Checking All Subsets
This approach exhaustively checks every possible group of students. A group can be represented as a subset of the students. There are `2^n` possible subsets, where `n` is the number of students. For each subset, we determine its size `k` and then verify if every student (both in the subset and not in the subset) is happy according to the given conditions.
**Time:** O(n * 2^n). There are `2^n` subsets to check. For each subset, we iterate through all `n` students to verify the happiness conditions. · **Space:** O(n) to store the current subset being processed.
**Pros:** Conceptually simple and directly follows the problem definition.
**Cons:** Extremely inefficient due to its exponential time complexity.; Not feasible for the given constraints where `n` can be up to `10^5`.
### Explanation
The algorithm iterates through all `2^n` subsets of the `n` students. This can be done using recursion or iteration with bit manipulation (where the `i`-th bit of a number from `0` to `2^n - 1` represents whether student `i` is selected).

For each subset `S`:
1.  Calculate the size of the group, `k = |S|`.
2.  Initialize a flag `all_happy = true`.
3.  Iterate through all `n` students from `i = 0` to `n-1`:
    - If student `i` is in the subset `S` (selected): check if `k > nums[i]`. If not, set `all_happy = false` and break.
    - If student `i` is not in the subset `S` (not selected): check if `k < nums[i]`. If not, set `all_happy = false` and break.
4.  If `all_happy` is still true after checking all students, it means this subset forms a valid group, so we increment our total count of ways.

After checking all `2^n` subsets, the final count is the answer.
### Algorithm
- Initialize a counter `ways` to 0.
- Generate every possible subset of students. There are `2^n` such subsets.
- For each subset `S`:
  - Let `k` be the size of the subset `S`.
  - Assume the group is valid (`all_happy = true`).
  - Iterate through all `n` students:
    - If a student `i` is in `S` (selected), check if `k > nums[i]`. If not, the group is invalid (`all_happy = false`), and we can stop checking this subset.
    - If a student `i` is not in `S` (not selected), check if `k < nums[i]`. If not, the group is invalid (`all_happy = false`), and we can stop checking this subset.
  - If `all_happy` remains true after checking all students, increment `ways`.
- Return `ways`.

## Sorting and Linear Scan
A much more efficient approach is based on the observation that if a valid group of size `k` exists, then the specific group formed by selecting the `k` students with the smallest `nums` values must also be valid. This crucial insight allows us to avoid checking every possible combination of students. By sorting the `nums` array first, we can check just one canonical candidate group for each possible size `k` (from 0 to `n`), leading to a much faster algorithm.
**Time:** O(n log n). Sorting the list takes `O(n log n)`. The subsequent loop to check all `n+1` possible group sizes takes `O(n)`. The total time is dominated by the sorting step. · **Space:** O(log n) or O(n), depending on the implementation of the sorting algorithm. Java's `Collections.sort` on a `List` can take up to O(n) space.
**Pros:** Highly efficient with a polynomial time complexity.; Correctly solves the problem within the given constraints.; The logic is systematic and covers all possible valid group sizes.
**Cons:** The logic is more involved than the brute-force approach.; The time complexity is limited by sorting, which might be suboptimal if a faster-than-sorting method existed (though unlikely for this problem).
### Explanation
First, we sort the `nums` list in non-decreasing order. This allows us to easily identify the students with the smallest `nums` values.

We then iterate through all possible group sizes `k` from `0` to `n` and check if a valid group of that size can be formed by selecting the `k` students with the smallest `nums` values.

- **Case `k = 0` (no students selected):**
  All `n` students are not selected. For every student `i` to be happy, the condition is `0 < nums[i]`. After sorting, we only need to check the smallest value: `0 < nums.get(0)`. If this holds, we count this as one valid way.

- **Case `1 <= k < n` (`k` students selected):**
  We form a group with the first `k` students from the sorted list (indices `0` to `k-1`).
  - For the `k` selected students to be happy, we need `k > nums[i]` for `i` in `[0, k-1]`. This is equivalent to `k > nums.get(k-1)`.
  - For the `n-k` non-selected students to be happy, we need `k < nums[j]` for `j` in `[k, n-1]`. This is equivalent to `k < nums.get(k)`.
  - If both `nums.get(k-1) < k` and `k < nums.get(k)` are true, we count this `k` as a valid way.

- **Case `k = n` (all students selected):**
  All `n` students are selected. For every student `i` to be happy, the condition is `n > nums[i]`. After sorting, we only need to check the largest value: `n > nums.get(n-1)`. If this holds, we count this as one valid way.

The final answer is the total count accumulated from these cases.

```java
import java.util.Collections;
import java.util.List;

class Solution {
    public int happyStudents(List<Integer> nums) {
        int n = nums.size();
        Collections.sort(nums);
        
        int count = 0;
        
        // Case k = 0: select 0 students
        // Condition: 0 < nums.get(i) for all i.
        // After sorting, this is equivalent to 0 < nums.get(0).
        if (nums.get(0) > 0) {
            count++;
        }
        
        // Case 1 <= k <= n-1: select k students
        // Select students at indices 0..k-1.
        // Condition for selected: k > nums.get(k-1).
        // Condition for not selected: k < nums.get(k).
        for (int k = 1; k < n; k++) {
            if (nums.get(k-1) < k && k < nums.get(k)) {
                count++;
            }
        }
        
        // Case k = n: select all n students
        // Condition: n > nums.get(i) for all i.
        // After sorting, this is equivalent to n > nums.get(n-1).
        if (nums.get(n-1) < n) {
            count++;
        }
        
        return count;
    }
}
```
### Algorithm
- Sort the input list `nums` in non-decreasing order.
- Initialize a counter `ways = 0`.
- **Check for group size `k=0`:** If no students are selected, all must be happy. This requires `0 < nums[i]` for all `i`. After sorting, this simplifies to `0 < nums.get(0)`. If true, increment `ways`.
- **Check for group sizes `1 <= k < n`:** For each `k`, we consider the group formed by the first `k` students in the sorted list. This group is valid if:
    - All selected students are happy: `k > nums.get(k-1)`.
    - All non-selected students are happy: `k < nums.get(k)`.
    - If both conditions are met, increment `ways`.
- **Check for group size `k=n`:** If all students are selected, all must be happy. This requires `n > nums[i]` for all `i`. After sorting, this simplifies to `n > nums.get(n-1)`. If true, increment `ways`.
- Return the total `ways`.

# Solutions
### Java

```java
class Solution {
public
  int countWays(List<Integer> nums) {
    Collections.sort(nums);
    int n = nums.size();
    int ans = 0;
    for (int i = 0; i <= n; i++) {
      if ((i == 0 || nums.get(i - 1) < i) && (i == n || nums.get(i) > i)) {
        ans++;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countWays(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int ans = 0;
    int n = nums.size();
    for (int i = 0; i <= n; ++i) {
      if ((i && nums[i - 1] >= i) || (i < n && nums[i] <= i)) {
        continue;
      }
      ++ans;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countWays(self, nums: List[int]) -> int: nums . sort() n = len(nums) ans = 0 for i in range(n + 1): if i and nums[i - 1] >= i: continue if i < n and nums[i] <= i: continue return ans

```