# 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 == sandwiches:
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.

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