Happy Students

Med

#2557Time: 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.

Patterns

Enumeration

Algorithms

Sorting

Data structures

Array

Prompt

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 i^th 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 <= 10⁵
0 <= nums[i] < nums.length

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

Calculate the size of the group, k = |S|.
Initialize a flag all_happy = true.
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.
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.

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1import java.util.Collections;2import java.util.List;3 4class Solution {5    public int happyStudents(List<Integer> nums) {6        int n = nums.size();7        Collections.sort(nums);8        9        int count = 0;10        11        // Case k = 0: select 0 students12        // Condition: 0 < nums.get(i) for all i.13        // After sorting, this is equivalent to 0 < nums.get(0).14        if (nums.get(0) > 0) {15            count++;16        }17        18        // Case 1 <= k <= n-1: select k students19        // Select students at indices 0..k-1.20        // Condition for selected: k > nums.get(k-1).21        // Condition for not selected: k < nums.get(k).22        for (int k = 1; k < n; k++) {23            if (nums.get(k-1) < k && k < nums.get(k)) {24                count++;25            }26        }27        28        // Case k = n: select all n students29        // Condition: n > nums.get(i) for all i.30        // After sorting, this is equivalent to n > nums.get(n-1).31        if (nums.get(n-1) < n) {32            count++;33        }34        35        return count;36    }37}

Complexity

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.

Trade-offs

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).

Solutions

Solution

1class Solution {2public3  int countWays(List<Integer> nums) {4    Collections.sort(nums);5    int n = nums.size();6    int ans = 0;7    for (int i = 0; i <= n; i++) {8      if ((i == 0 || nums.get(i - 1) < i) && (i == n || nums.get(i) > i)) {9        ans++;10      }11    }12    return ans;13  }14}

1class Solution {2public:3  int countWays(vector<int> &nums) {4    sort(nums.begin(), nums.end());5    int ans = 0;6    int n = nums.size();7    for (int i = 0; i <= n; ++i) {8      if ((i && nums[i - 1] >= i) || (i < n && nums[i] <= i)) {9        continue;10      }11      ++ans;12    }13    return ans;14  }15};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem