We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Happy Students

Number: 3104

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an integer array nums representing the thresholds of n students, a teacher needs to select a subset of students such that every student is happy. A student is happy if either: • They are selected and the total number of selected students (k) is strictly greater than nums[i], or • They are not selected and k is strictly less than nums[i].

Return the number of valid ways (i.e. valid k choices) to select students so that everyone is happy.

Key Insights

  • For a fixed group size k, the following forced assignments occur: • Any student with threshold < k must be selected. • Any student with threshold > k must not be selected. • A student with threshold exactly equal to k can never be happy.
  • Thus, for a fixed k to be valid, two conditions must hold: • The number of students with threshold strictly less than k equals k. • No student has threshold exactly equal to k.
  • Iterate k from 0 to n to count all valid selections.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting and binary search per candidate k. Space Complexity: O(n), primarily used for sorting.

Solution

We solve the problem by first sorting the nums array, which allows us to quickly count how many elements are less than a given k using binary search (lower_bound). For each possible group size k (from 0 to n), we:

  1. Count the number of students with threshold < k.
  2. Ensure that no student has threshold == k.
  3. Check if the count equals k. If these conditions are met, then k is a valid selection and we increment our count.

Code Solutions

# Python solution for the Happy Students problem
class Solution:
    def happyStudents(self, nums):
        # First, sort the array to efficiently count thresholds
        nums.sort()
        n = len(nums)
        validSelections = 0
        
        # Helper function: count numbers strictly less than x using binary search
        def count_less_than(x):
            lo, hi = 0, n
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < x:
                    lo = mid + 1
                else:
                    hi = mid
            return lo
        
        # Check for every possible k from 0 to n
        for k in range(n + 1):
            count = count_less_than(k)
            # Check if any student has threshold exactly equal to k
            lo, hi = 0, n
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < k:
                    lo = mid + 1
                else:
                    hi = mid
            foundEqual = lo < n and nums[lo] == k
            
            # k is valid if count of students with threshold less than k equals k
            # and there is no student with threshold equal to k
            if count == k and not foundEqual:
                validSelections += 1
                
        return validSelections

# Example usage:
solution = Solution()
print(solution.happyStudents([1,1]))  # Expected Output: 2
print(solution.happyStudents([6,0,3,3,6,7,2,7]))  # Expected Output: 3
← Back to All Questions