Skip to main content
Talentd

Happy Students - Solution & Explanation

MediumArraySortingEnumeration18 min readAsked at: Amazon
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Sorting and Evaluating Possible Cut Points

We can solve this problem by first sorting the array. After sorting, we evaluate the possible cut points where we can split students into selected and unselected groups while keeping everyone happy.

Iterate through the sorted list and count valid cut points that can serve as the number of selected students. We consider the edge cases of selecting everyone and selecting no one separately.

This C implementation first sorts the array and then iterates through possible cut points. It checks conditions where students can be happy based on their position compared to their expectations in the sorted list. If a valid condition is found, it increments the count of happy configurations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as the algorithm mainly sorts in place.

Try this approach in the editor →

Approach 2: Counting Using Binary Search

After sorting the array, we can utilize binary search to find the critical points directly where the number of selected students could make students happy. This approach leverages the sorted property to quickly check the count of elements less than or greater than potential boundary conditions.

The C implementation uses binary search on sorted elements to efficiently find the number of ways to segment the students into either groups. By searching for each possible number of students, it ensures students' happiness conditions are respected without redundant operations.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) for sorting and O(log n) per search, resulting in O(n log n) overall.
Space Complexity: O(1) in terms of additional memory.

Try this approach in the editor →

Approach 3: Sorting + Enumeration

Assume that k students are selected, then the following conditions hold:

  • If nums[i] = k, then there is no grouping method;
  • If nums[i] > k, then student i is not selected;
  • If nums[i] < k, then student i is selected.

Therefore, the selected students must be the first k elements in the sorted nums array.

We enumerate k in the range [0,..n]. For the current number of selected students i, we can get the maximum student number in the group i-1, which is nums[i-1]. If i > 0 and nums[i-1] \ge i, then there is no grouping method; if i < n and nums[i] \le i, then there is no grouping method. Otherwise, there is a grouping method, and the answer is increased by one.

After the enumeration ends, return the answer.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Evaluating Possible Cut Points

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as the algorithm mainly sorts in place.

Counting Using Binary Search

Time Complexity: O(n log n) for sorting and O(log n) per search, resulting in O(n log n) overall.
Space Complexity: O(1) in terms of additional memory.

Sorting + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting and Evaluating Cut PointsO(n log n)O(1)Best general solution; simple logic after sorting and commonly expected in interviews
Enumeration with Binary SearchO(n log n)O(1)Useful when reasoning directly about candidate group sizes and validating counts via binary search

Video Solution

🔴 2860. Happy Students II Weekly Contest 363 II Leetcode 2860 • Aryan Mittal • 4,320 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Happy Students easy or hard?
Happy Students is rated Medium difficulty. The challenge is recognizing that only boundary positions in the sorted array can produce valid group sizes. Once that insight is clear, the implementation becomes straightforward.
Happy Students Python/Java solution
Most implementations follow the same pattern: sort the array, iterate through possible cut points, and check boundary conditions. The logic is identical across Python, Java, C++, and JavaScript, with differences only in syntax and built-in sorting functions.
How to solve Happy Students in O(n)?
A strict O(n) solution is generally not used because the ordering of values matters. Sorting simplifies the constraints and leads to a clean O(n log n) solution. After sorting, checking candidate group sizes only requires a single pass through the array.
What is the best approach for Happy Students?
The most common approach is sorting the array and evaluating valid cut points. After sorting, check each possible group size k and verify boundary conditions: nums[k-1] < k and nums[k] > k (with edge cases for k=0 and k=n). This runs in O(n log n) time due to sorting and O(1) extra space.
Is Happy Students asked at Google/Amazon/Meta?
Problems involving sorting with boundary conditions and counting valid configurations are common in interviews at companies like Google, Amazon, and Meta. While the exact question may vary, the pattern of sorting and validating constraints appears frequently in coding interviews.
What data structure is used in Happy Students?
The problem primarily uses arrays along with sorting. Some variants of the solution also rely on binary search to count how many elements are less than a given threshold when testing candidate group sizes.
What is the time complexity of Happy Students?
The optimal solution runs in O(n log n) time because the array must be sorted first. After sorting, a single linear scan checks valid boundaries in O(n) time. Space complexity is O(1) if the sort is in-place.

Ready to solve this problem?

Practice Happy Students with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays