Happy Students

Medium

Asked by:

12 views

Topics:

ArraysBinary Search

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the student preferences (numbers in the `students` array)? Can they be negative or zero?
How large can the input `students` array be? Is there a practical upper bound?
If there are multiple ways to make all students happy, is any valid configuration acceptable, or is there a specific one I should prioritize finding (e.g., the one with the fewest happy students beyond the minimum)?
If no arrangement makes all students happy, what should I return? Is there a specified return value for this scenario?
Are the student preferences guaranteed to be distinct, or can there be duplicates?

Brute Force Solution

Approach

The brute force approach to this student happiness problem involves trying every possible combination of student selections. We examine each combination to see if it meets our happiness criteria.

Here's how the algorithm would work step-by-step:

Consider all possible groups of students. Start with an empty group, then groups with one student, then groups with two, and so on, until we have a group containing all the students.
For each group, check if the students in that group are 'happy'. A student is happy if their aptitude is less than or equal to the number of students selected in the group.
Count how many happy students there are in each group.
If the number of happy students in a group is the same as the number of students we chose for that group, then it is a good combination.
Count the total number of good combinations that we found during our process.
The final count of good combinations represents our answer.

Code Implementation

def happy_students(aptitudes):
    number_of_students = len(aptitudes)
    good_combinations_count = 0

    for i in range(1 << number_of_students):
        selected_students = []
        for j in range(number_of_students):
            if (i >> j) & 1:
                selected_students.append(aptitudes[j])

        number_of_selected_students = len(selected_students)
        happy_students_count = 0

        # Determine if student is happy with the current group
        for aptitude in selected_students:

            if aptitude <= number_of_selected_students:
                happy_students_count += 1

        # Only count as valid if all selected students are happy
        if happy_students_count == number_of_selected_students:

            good_combinations_count += 1

    return good_combinations_count

Big(O) Analysis

Time Complexity

O(2^n * n) – The solution explores all possible subsets of the n students, which results in 2^n combinations. For each of these combinations, it iterates through the selected students to check if they are happy, taking O(n) time in the worst case (when all students are selected). Thus, the overall time complexity is O(2^n * n), where 2^n represents the number of subsets and n is the cost of checking the happiness of each student in a subset.

Space Complexity

O(N) – The brute force approach, as described, implicitly uses recursion to generate all possible combinations of students. The depth of the recursion can go up to N, where N is the total number of students. Each level of recursion stores variables related to the current group being examined (selected students and happy student count), and in the worst case, all N students could be part of the current combination, leading to storing up to N variables at each level. Therefore, the space complexity due to the recursion stack is O(N).

Optimal Solution

Approach

The goal is to find the largest number of students who are 'happy'. A student is happy if their chosen number is no larger than their position in the sorted list of numbers. To maximize happy students, sort the numbers first and then count how many students are happy in that order.

Here's how the algorithm would work step-by-step:

First, arrange all the numbers from smallest to largest.
Now, go through the numbers one by one, keeping track of the current position.
For each number, check if it's less than or equal to the current position.
If it is, that student is happy! Count them.
Continue this process for all the numbers.
The final count is the maximum number of happy students you can have.

Code Implementation

def happy_students(student_choices):
    student_choices.sort()
    happy_student_count = 0

    # We iterate through the sorted list
    for index, choice in enumerate(student_choices):
        # Add one to index to represent position
        student_position = index + 1

        # Check if the student is happy.
        if choice <= student_position:
            
            happy_student_count += 1

    return happy_student_count

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation in this algorithm is sorting the input array of size n. Efficient sorting algorithms like merge sort or quicksort typically have a time complexity of O(n log n). The subsequent iteration through the sorted array to count happy students takes O(n) time. Since O(n log n) grows faster than O(n) as n increases, the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(1) – The provided algorithm sorts the input array in-place and iterates through it using a loop, keeping track of the current position and a happy student count. No auxiliary data structures, such as additional arrays or hash maps, are used. Therefore, the space used is constant regardless of the input size N, where N is the number of students.

Edge Cases

Case	How to Handle
Empty array	Return 0, as there are no students and thus no happy students.
Array with a single element	If the single element is <= 1, return 1, otherwise return 0.
All elements in the array are identical	The solution should still correctly determine the number of happy students based on the sorted position and value.
Array with all 0s	After sorting, any student placed at index i where i >= 0 will be happy, so return n if n is the array size
Array with all numbers greater than or equal to the array size	Return 0, because no student can be happy since arr[i] will always be greater than i+1.
Array is already sorted in ascending order	The algorithm should still produce the correct result regardless of pre-existing order.
Array is sorted in descending order	The algorithm should still correctly determine happy students after properly sorting the input.
Maximum-sized array (constraints not specified, but assume large)	Ensure the sorting algorithm used has a time complexity of O(n log n) to prevent timeouts.

Empty array

How to Handle:

Return 0, as there are no students and thus no happy students.

Array with a single element

How to Handle:

If the single element is <= 1, return 1, otherwise return 0.

All elements in the array are identical

How to Handle:

The solution should still correctly determine the number of happy students based on the sorted position and value.

Array with all 0s

How to Handle:

After sorting, any student placed at index i where i >= 0 will be happy, so return n if n is the array size

Array with all numbers greater than or equal to the array size

How to Handle:

Return 0, because no student can be happy since arr[i] will always be greater than i+1.

Array is already sorted in ascending order

How to Handle:

The algorithm should still produce the correct result regardless of pre-existing order.

Array is sorted in descending order

How to Handle:

The algorithm should still correctly determine happy students after properly sorting the input.

Maximum-sized array (constraints not specified, but assume large)

How to Handle:

Ensure the sorting algorithm used has a time complexity of O(n log n) to prevent timeouts.