Watch 10 video solutions for Happy Students, a medium level problem involving Array, Sorting, Enumeration. This walkthrough by Aryan Mittal has 4,270 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
nums[i].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 <= 1050 <= nums[i] < nums.lengthProblem Overview: You are given an array nums where nums[i] represents the number of students that must have a higher score than student i for that student to feel satisfied. The task is to count how many ways you can choose a group size k such that exactly k students are selected and every student is happy with the number of higher-ranked students.
Approach 1: Sorting and Evaluating Possible Cut Points (O(n log n) time, O(1) extra space)
The key observation is that only the count of selected students matters. After sorting nums, you can treat the array as a sequence of potential cut points. Suppose you choose k students. For the configuration to work, every selected student must tolerate fewer than k higher-ranked students (nums[i] < k for selected ones), while every unselected student must require more than k higher-ranked students (nums[i] > k). Sorting lets you check these conditions efficiently at boundaries. Iterate through the sorted array and test whether a cut between index k-1 and k forms a valid configuration: nums[k-1] < k and nums[k] > k. Also handle edge cases such as k = 0 and k = n. This approach is straightforward, uses a single pass after sorting, and is typically the cleanest solution in interviews. It relies heavily on ideas from sorting and array traversal.
Approach 2: Counting Using Binary Search (O(n log n) time, O(1) space)
Another way to reason about the problem is to iterate over all possible group sizes k from 0 to n. For each candidate k, determine how many students have nums[i] < k. If that count equals exactly k, the configuration is valid. Because the array is sorted, you can find the boundary where values become >= k using lower_bound or a standard binary search. This gives the count of elements strictly less than k. If the count equals k, all selected students tolerate the ranking and all others require more than k higher-ranked students. This method explicitly enumerates possible group sizes while using binary search to verify the condition quickly.
Recommended for interviews: The sorting + cut point method is the most common solution interviewers expect. It shows you recognize that the only meaningful states occur at boundaries in the sorted array. Starting with the enumeration idea helps demonstrate understanding, while the sorted boundary check shows stronger algorithmic insight and leads to a concise implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Evaluating Cut Points | O(n log n) | O(1) | Best general solution; simple logic after sorting and commonly expected in interviews |
| Enumeration with Binary Search | O(n log n) | O(1) | Useful when reasoning directly about candidate group sizes and validating counts via binary search |