Number of Students Unable to Eat Lunch - Solution & Explanation
Problem Statement
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:
- If the student at the front of the queue prefers the sandwich on the top of the stack, they will take it and leave the queue.
- Otherwise, they will leave it and go to the queue's end.
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]is0or1.students[i]is0or1.
Approach Overview
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 1: Simulate the Process Using a Queue
In this approach, we simulate the exact process of distributing sandwiches using a queue-like structure for the students. We repeatedly check if the student at the front of the queue can take the sandwich at the top of the stack. If not, the student is moved to the back of the queue. This continues until we complete a full cycle without any students taking a sandwich, indicating they can't eat.
This C code defines a function that uses a circular iteration over the student preferences to check each against the current sandwich on the stack. We use two indices: one for students and one for sandwiches, plus a cycle counter to detect when all options are exhausted without making progress. The cycle count control helps to stop the loop when no further matches are possible, making the method more efficient.
Complexity
Time Complexity: O(n^2) in the worst scenario because each student may be checked multiple times.
Space Complexity: O(1) since it only uses a fixed amount of extra space.
Approach 2: Count Preferences and Match with Sandwiches
This approach uses counting to determine if students can satisfy their preferences before iterating over sandwiches. By counting the number of students preferring each type, we can efficiently determine how many students will be unable to eat if sandwiches of their preference run out before they can eat.
The C implementation counts the preferences for circular and square sandwiches. It iterates over the sandwiches and decreases the count of the suitable preference whenever a sandwich is taken. If no more students prefer the top sandwich, it returns the remaining count.
Complexity
Time Complexity: O(n) because it processes each list one time.
Space Complexity: O(1) since it only uses fixed additional space for counting.
Approach 3: Counting
We observe that the positions of the students can be adjusted, but the positions of the sandwiches cannot be adjusted. That is to say, if the sandwich in front is not taken, then all the sandwiches behind cannot be taken.
Therefore, we first use a counter cnt to count the types of sandwiches that students like and their corresponding quantities.
Then we traverse the sandwiches. If we cannot find a student who likes this sandwich in cnt, it means that the sandwiches behind cannot be taken, and we return the current number of remaining students.
If the traversal is over, it means that all students have sandwiches to eat, and we return 0.
The time complexity is O(n), where n is the number of sandwiches. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Simulate the Process Using a Queue | Time Complexity: O(n^2) in the worst scenario because each student may be checked multiple times. |
| Count Preferences and Match with Sandwiches | Time Complexity: O(n) because it processes each list one time. |
| Counting | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Number of Students Unable to Eat Lunch - Leetcode 1700 - Python • NeetCodeIO • 30,691 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Number of Students Unable to Eat Lunch easy or hard?
Number of Students Unable to Eat Lunch Python/Java solution
How to solve Number of Students Unable to Eat Lunch in O(n)?
What is the best approach for Number of Students Unable to Eat Lunch?
Is Number of Students Unable to Eat Lunch asked at Google/Amazon/Meta?
What data structure is used in Number of Students Unable to Eat Lunch?
What is the time complexity of Number of Students Unable to Eat Lunch?
Ready to solve this problem?
Practice Number of Students Unable to Eat Lunch with our built-in code editor and test cases.
Practice on FleetCode