Number of Students Unable to Eat Lunch solution and explanation
Google
9 more videos on this problem
Number of Students Unable to Eat Lunch - Leetcode 1700 - PythonNeetCodeIO · 8:22 · 30K views
Number of Students Unable to Eat Lunch | 2 Approaches | Leetcode 1700 | codestorywithMIKcodestorywithMIK · 19:01 · 9K views
1700. Number of Students Unable to Eat Lunch (Leetcode Easy)Programming Live with Larry · 5:23 · 6K views
LeetCode 1700 Number of Students Unable to Eat Lunch - PythonRan Fang · 10:58 · 4K views
1700. Number of Students Unable to Eat Lunch | Stack & Queue | Simulation | Adhoc | Time ComplexityAryan Mittal · 18:16 · 4K views
1700. Number of Students Unable to Eat Lunch || LEETCODE SOLUTION || IN C++ || DS AND ALGOAbhishweta Gupta · 2:57 · 1K views
Leetcode 1700. Number of Students Unable to Eat LunchFraz · 17:44 · 1K views
Number of Students Unable to Eat Lunch | Approaches | Leetcode 1700 | CodeRebel.CodeRebel · 6:16 · 385 views
LeetCode 1700 - Number of Students Unable to Eat Lunch - JavaAlpha-Code · 8:49 · 368 views
LeetCode - 1700.Number Of Students Unable To Eat Lunch- explained In JavaYourFavProgrammer · 5:08 · 232 views
The problem
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.
from collections import deque
def count_students(students, sandwiches):
queue = deque(students)
j = 0
cycle_count = 0
while queue and cycle_count < len(queue):
if queue[0] == sandwiches[j]:
queue.popleft()
j += 1
cycle_count = 0
else:
queue.append(queue.popleft())
cycle_count += 1
return len(queue)
students = [1, 1, 0, 0]
sandwiches = [0, 1, 0, 1]
print(count_students(students, sandwiches))import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int countStudents(int[] students, int[] sandwiches) {
Queue<Integer> queue = new LinkedList<>();
for (int student : students) {
queue.offer(student);
}
int j = 0, cycle_count = 0;
while (!queue.isEmpty() && cycle_count < queue.size()) {
if (queue.peek() == sandwiches[j]) {
queue.poll();
j++;
cycle_count = 0;
} else {
queue.offer(queue.poll());
cycle_count++;
}
}
return queue.size();
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] students = {1, 1, 0, 0};
int[] sandwiches = {0, 1, 0, 1};
System.out.println(solution.countStudents(students, sandwiches));
}
}#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int countStudents(vector<int>& students, vector<int>& sandwiches) {
queue<int> studentQueue;
for (int student : students) {
studentQueue.push(student);
}
int j = 0, cycle_count = 0;
while (!studentQueue.empty() && cycle_count < studentQueue.size()) {
if (studentQueue.front() == sandwiches[j]) {
studentQueue.pop();
j++;
cycle_count = 0;
} else {
studentQueue.push(studentQueue.front());
studentQueue.pop();
cycle_count++;
}
}
return studentQueue.size();
}
int main() {
vector<int> students = {1, 1, 0, 0};
vector<int> sandwiches = {0, 1, 0, 1};
int result = countStudents(students, sandwiches);
cout << result << endl;
return 0;
}function countStudents(students, sandwiches) {
let queue = students.slice();
let j = 0;
let cycle_count = 0;
while (queue.length > 0 && cycle_count < queue.length) {
if (queue[0] === sandwiches[j]) {
queue.shift();
j++;
cycle_count = 0;
} else {
queue.push(queue.shift());
cycle_count++;
}
}
return queue.length;
}
const students = [1, 1, 0, 0];
const sandwiches = [0, 1, 0, 1];
console.log(countStudents(students, sandwiches));#include <stdio.h>
#include <stdbool.h>
int countStudents(int* students, int studentsSize, int* sandwiches, int sandwichesSize) {
int count = 0;
int i = 0, j = 0;
int cycle_count = 0;
while (j < sandwichesSize && cycle_count < studentsSize) {
if (students[i] == sandwiches[j]) {
j++;
cycle_count = 0; // Reset cycle counter when a match happens
} else {
cycle_count++;
}
i = (i + 1) % studentsSize;
}
return studentsSize - j;
}
int main() {
int students[] = {1, 1, 0, 0};
int sandwiches[] = {0, 1, 0, 1};
int result = countStudents(students, 4, sandwiches, 4);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int CountStudents(int[] students, int[] sandwiches) {
Queue<int> queue = new Queue<int>(students);
int j = 0, cycle_count = 0;
while (queue.Count > 0 && cycle_count < queue.Count) {
if (queue.Peek() == sandwiches[j]) {
queue.Dequeue();
j++;
cycle_count = 0;
} else {
queue.Enqueue(queue.Dequeue());
cycle_count++;
}
}
return queue.Count;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] students = {1, 1, 0, 0};
int[] sandwiches = {0, 1, 0, 1};
Console.WriteLine(solution.CountStudents(students, sandwiches));
}
}This Python solution utilizes a deque for efficient pop and append operations to simulate the queue operations. It keeps track of cycle counts to detect when no further matches can be made, breaking when necessary.
Time Complexity: O(n^2) in the worst-case.
Space Complexity: O(n) due to deque implementation.
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.
def count_students(students, sandwiches):
studentTypes = [0, 0]
for student in students:
studentTypes[student] += 1
for sandwich in sandwiches:
if studentTypes[sandwich] > 0:
studentTypes[sandwich] -= 1
else:
return sum(studentTypes) # Number of students who can't eat
return 0
students = [1, 1, 0, 0]
sandwiches = [0, 1, 0, 1]
print(count_students(students, sandwiches))public class Solution {
public int countStudents(int[] students, int[] sandwiches) {
int[] studentTypes = new int[2];
for (int student : students) {
studentTypes[student]++;
}
for (int sandwich : sandwiches) {
if (studentTypes[sandwich] > 0) {
studentTypes[sandwich]--;
} else {
return studentTypes[0] + studentTypes[1];
}
}
return 0;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] students = {1, 1, 0, 0};
int[] sandwiches = {0, 1, 0, 1};
System.out.println(solution.countStudents(students, sandwiches));
}
}#include <iostream>
#include <vector>
using namespace std;
int countStudents(vector<int>& students, vector<int>& sandwiches) {
int studentTypes[2] = {0, 0};
for (int student : students) {
studentTypes[student]++;
}
for (int sandwich : sandwiches) {
if (studentTypes[sandwich] > 0) {
studentTypes[sandwich]--;
} else {
return count(studentTypes, studentTypes + 2, 0);
}
}
return 0;
}
int main() {
vector<int> students = {1, 1, 0, 0};
vector<int> sandwiches = {0, 1, 0, 1};
int result = countStudents(students, sandwiches);
cout << result << endl;
return 0;
}function countStudents(students, sandwiches) {
let studentTypes = [0, 0];
students.forEach(student => studentTypes[student]++);
for (let sandwich of sandwiches) {
if (studentTypes[sandwich] > 0) {
studentTypes[sandwich]--;
} else {
return studentTypes.reduce((a, b) => a + b, 0);
}
}
return 0;
}
const students = [1, 1, 0, 0];
const sandwiches = [0, 1, 0, 1];
console.log(countStudents(students, sandwiches));#include <stdio.h>
int countStudents(int* students, int studentsSize, int* sandwiches, int sandwichesSize) {
int studentTypes[2] = {0};
for (int i = 0; i < studentsSize; i++) {
studentTypes[students[i]]++;
}
for (int i = 0; i < sandwichesSize; i++) {
if (studentTypes[sandwiches[i]] > 0) {
studentTypes[sandwiches[i]]--;
} else {
return studentsSize - i; // Remaining students can't eat
}
}
return 0;
}
int main() {
int students[] = {1, 1, 0, 0};
int sandwiches[] = {0, 1, 0, 1};
int result = countStudents(students, 4, sandwiches, 4);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int CountStudents(int[] students, int[] sandwiches) {
int[] studentTypes = new int[2];
foreach (int student in students) {
studentTypes[student]++;
}
foreach (int sandwich in sandwiches) {
if (studentTypes[sandwich] > 0) {
studentTypes[sandwich]--;
} else {
return studentTypes[0] + studentTypes[1];
}
}
return 0;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] students = {1, 1, 0, 0};
int[] sandwiches = {0, 1, 0, 1};
Console.WriteLine(solution.CountStudents(students, sandwiches));
}
}The Python solution tallies the food type preferences using a list of size 2. It uses a for loop to decrease the count of available preferences upon each sandwich distribution. If all choices are exhausted, it sums the remaining students.
Time Complexity: O(n) for traversing both arrays.
Space Complexity: O(1) for maintaining fixed-space counts.
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).
function countStudents(students: number[], sandwiches: number[]): number {
const count = [0, 0];
for (const v of students) {
count[v]++;
}
for (const v of sandwiches) {
if (count[v] === 0) {
return count[v ^ 1];
}
count[v]--;
}
return 0;
}func countStudents(students []int, sandwiches []int) int {
cnt := [2]int{}
for _, v := range students {
cnt[v]++
}
for _, v := range sandwiches {
if cnt[v] == 0 {
return cnt[v^1]
}
cnt[v]--
}
return 0
}impl Solution {
pub fn count_students(students: Vec<i32>, sandwiches: Vec<i32>) -> i32 {
let mut count = [0, 0];
for &v in students.iter() {
count[v as usize] += 1;
}
for &v in sandwiches.iter() {
let v = v as usize;
if count[v as usize] == 0 {
return count[v ^ 1];
}
count[v] -= 1;
}
0
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simulate the Process Using a Queue | Time Complexity: O(n^2) in the worst-case. |
| Count Preferences and Match with Sandwiches | Time Complexity: O(n) for traversing both arrays. |
| Counting | – |
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 |
Frequently asked questions
Is Number of Students Unable to Eat Lunch easy or hard?
Number of Students Unable to Eat Lunch is classified as an Easy problem on LeetCode with a high acceptance rate. The challenge mainly tests understanding of queue simulation and recognizing the optimization that converts the process into simple counting.
Number of Students Unable to Eat Lunch Python/Java solution
Python and Java implementations typically follow either the queue simulation using collections like deque/Queue or the optimal counting approach using simple integer counters. The counting method is shorter, runs in O(n) time, and uses constant extra space.
How to solve Number of Students Unable to Eat Lunch in O(n)?
Count how many students prefer sandwich type 0 and type 1. Iterate through the sandwiches stack from top to bottom. If the sandwich type still has students who want it, decrement the corresponding counter. If not, stop immediately because the remaining students cannot eat. The number of remaining students is the answer.
What is the best approach for Number of Students Unable to Eat Lunch?
The best approach counts how many students prefer each sandwich type (0 or 1) and then scans the sandwich stack. If the current sandwich type has no students left who prefer it, the remaining students cannot eat. This method runs in O(n) time and O(1) space and avoids unnecessary queue rotations.
Is Number of Students Unable to Eat Lunch asked at Google/Amazon/Meta?
This problem represents a common queue and simulation pattern frequently used in technical interviews. Variations of queue processing and preference matching have appeared in interviews at companies like Amazon and Google, especially for entry-level and mid-level roles.
What data structure is used in Number of Students Unable to Eat Lunch?
The direct simulation uses a queue to represent the line of students and processes sandwiches from a stack-like structure. The optimized solution reduces the problem to counting values in an array, eliminating the need for explicit queue operations.
What is the time complexity of Number of Students Unable to Eat Lunch?
The optimal counting solution runs in O(n) time because you count student preferences once and iterate through the sandwiches once. The queue simulation approach can degrade to O(n^2) in the worst case due to repeated rotations of students in the queue.