Leetcode – Number of Students Unable to Eat Lunch Solution

The “Number of Students Unable to Eat Lunch” problem is a fascinating task that challenges your algorithmic thinking and data structure skills, specifically involving queues. This Leetcode problem is not only interesting but also relevant to real-world scenarios, as it simulates a classic queue-based allocation problem. This extensive guide aims to explore various ways to tackle this problem, analyze their time and space complexities.

Problem Statement

You are given two integer arrays students and sandwiches where:

• students[i] is the initial hunger level of the ith student in the queue (0-indexed).
• sandwiches[j] is the type of the jth sandwich in the sandwich queue (0-indexed).

A student with hunger level 0 will eat a square sandwich, and a student with hunger level 1 will eat a circular sandwich. The students and sandwiches are both ordered in a queue. The hunger levels are immutable.

Write a function to return the number of students who will not be able to eat lunch.

Example:

Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0

Basic Approach: Simulation using Queues

One approach to solving this problem is to simulate the process using queues.

Python Code

from collections import deque

def countStudents(students, sandwiches):
    students = deque(students)
    sandwiches = deque(sandwiches)
    
    count = 0  # Counter to track the number of unsuccessful attempts to feed a student
    
    while students:
        if students[0] == sandwiches[0]:
            students.popleft()
            sandwiches.popleft()
            count = 0  # Reset counter
        else:
            students.rotate(-1)  # Move the student to the end of the queue
            count += 1  # Increment the unsuccessful attempts counter
            
        if count == len(students):
            break  # All remaining students cannot eat
            
    return len(students)

Time Complexity

The time complexity for this approach is O(n), where n is the length of the students or sandwiches array.

Optimized Approach: Counting Student Types

A more efficient way to solve this problem is to count the number of students who prefer each type of sandwich and use this information to quickly determine the number of students who will not be able to eat lunch.

Python Code

def countStudents(students, sandwiches):
    count = [0, 0]
    
    for student in students:
        count[student] += 1
        
    for sandwich in sandwiches:
        if count[sandwich] == 0:
            return sum(count)
        count[sandwich] -= 1
        
    return 0

Time Complexity

The time complexity is O(n), where n is the length of the students or sandwiches array. However, this approach is generally faster in practice because it avoids the need for queue rotations.

Testing Your Solution

Before you submit your code on Leetcode, you should test it against some test cases to ensure its correctness.

assert countStudents([1, 1, 0, 0], [0, 1, 0, 1]) == 0
assert countStudents([1, 1, 1, 0, 0, 1], [1, 0, 0, 0, 1, 1]) == 3

Conclusion

The “Number of Students Unable to Eat Lunch” problem is a great example that tests your understanding of queues and array manipulation. Two approaches have been discussed: one involving direct simulation using queues, and the other, a more optimized approach that counts student types.