Watch 10 video solutions for Number of Students Unable to Eat Lunch, a easy level problem involving Array, Stack, Queue. This walkthrough by NeetCodeIO has 29,000 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers 0 and 1 respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.
The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a stack. At each step:
This continues until none of the queue students want to take the top sandwich and are thus unable to eat.
You are given two integer arrays students and sandwiches where sandwiches[i] is the type of the ith sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the jth student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.
Example 1:
Input: students = [1,1,0,0], sandwiches = [0,1,0,1] Output: 0 Explanation: - Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1]. - Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1]. - Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1]. - Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0]. - Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1]. - Front student leaves the top sandwich and returns to the end of the line making students = [0,1]. - Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1]. - Front student takes the top sandwich and leaves the line making students = [] and sandwiches = []. Hence all students are able to eat.
Example 2:
Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1] Output: 3
Constraints:
1 <= students.length, sandwiches.length <= 100students.length == sandwiches.lengthsandwiches[i] is 0 or 1.students[i] is 0 or 1.Problem Overview: Students stand in a queue and sandwiches are stacked. Each student prefers either circular (0) or square (1) sandwiches. If the front student does not want the top sandwich, they move to the end of the queue. The process stops when nobody in the queue wants the sandwich on top. Return the number of students who cannot eat.
Approach 1: Simulate the Process Using a Queue (Time: O(n^2), Space: O(n))
This approach models the situation exactly as described. Put all students into a queue and process sandwiches from the stack. If the front student prefers the current sandwich type, they take it and both are removed. Otherwise, move that student to the end of the queue. Track how many consecutive students have been rotated without anyone taking the sandwich. If this count reaches the current queue size, no remaining student wants the sandwich on top, so the process stops. This method directly uses queue operations like pop and push and mirrors the real process step by step. It’s easy to reason about and works well for understanding the simulation aspect of the problem using a queue or simulation pattern.
Approach 2: Count Preferences and Match with Sandwiches (Time: O(n), Space: O(1))
The key observation: the relative order of students does not matter once you know how many students prefer each sandwich type. Count how many students want circular (0) and square (1) sandwiches. Then iterate through the sandwich stack from top to bottom. If the sandwich is type 0 and there are students who want 0, decrement the count and continue. If no students want that type anymore, the remaining students cannot eat because the sandwich on top will never be taken. The same logic applies for type 1. This removes the need for an explicit queue and reduces the simulation to simple counting. The algorithm only scans the arrays once, making it an efficient array-based solution.
Recommended for interviews: The counting approach is the expected optimal solution because it runs in O(n) time with constant space and relies on a key insight about preference counts. Showing the queue simulation first demonstrates you understand the problem mechanics. Then optimizing it using counts shows strong problem-solving and pattern recognition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate the Process Using a Queue | O(n^2) | O(n) | When you want a direct simulation of the queue behavior or when learning queue-based problem modeling |
| Count Preferences and Match with Sandwiches | O(n) | O(1) | Best for interviews and large inputs where an optimal linear scan is preferred |