Students Unable Eat Lunch LeetCode 1700

LeetCode 1700 — Number of Students Unable to Eat Lunch — presents a cafeteria scenario: n students stand in a queue and n sandwiches are stacked. Each student prefers either a circular sandwich (type 0) or a square sandwich (type 1). At each step, if the front student likes the top sandwich they take it and leave; otherwise, that student goes to the back of the queue. The process continues until no student in the queue wants the top sandwich, at which point all remaining students are unable to eat.

You are given two arrays: students[], where students[i] is the preference of the i-th student in queue order, and sandwiches[], where sandwiches[j] is the type of the j-th sandwich from top to bottom. The function must return the count of students who cannot eat. Constraints are small: both arrays have between 1 and 100 elements and values are 0 or 1 only.

The problem looks like a queue/stack simulation at first glance, which tempts you to rotate the queue in code and track a full-rotation counter. That approach works but runs in O(n^2) worst case and is tricky to terminate correctly. A cleaner, faster approach emerges from a key insight about when students get permanently blocked.

The brute-force simulation mirrors the problem description exactly. Use a deque (double-ended queue) initialized with the students array, and a pointer into the sandwiches array. At each step, check whether the front student matches the current top sandwich. If yes, dequeue the student and advance the sandwich pointer. If no, rotate the student from the front to the back.

The tricky part is knowing when to stop. One common approach is to track how many consecutive students have been rotated past the current sandwich without taking it. When this counter equals the current queue length, no student wants the top sandwich — the loop terminates and the remaining queue size is the answer. This check makes the simulation O(n^2) in the worst case: each sandwich may require a full rotation before being taken.

The simulation has an off-by-one risk in the stopping condition. If you check "rotated >= len(queue)" you are correct; if you check "rotated > len(queue)" you may skip one extra comparison. Despite being O(n^2), the simulation is a valid solution for n ≤ 100 and makes an acceptable first pass in an interview before optimizing.

The O(n) counting approach discards queue simulation entirely. First, count how many students prefer type 0 and how many prefer type 1. In Python this is Counter(students); in Java it is a two-element array count[2] incremented for each student. This pre-processing step runs in O(n).

Next, iterate through the sandwiches array from top (index 0) to bottom. For each sandwich, check whether its type still has at least one student wanting it. If count[sandwich] > 0, that student takes the sandwich — decrement count[sandwich] and continue to the next sandwich. If count[sandwich] == 0, no remaining student wants this sandwich, so the loop terminates immediately.

When the loop terminates (either naturally at the end of sandwiches or by early exit), the total number of unable-to-eat students is count[0] + count[1] — all students who still have unmet preferences. The entire algorithm is O(n) time and O(1) space (only two counters needed regardless of n).

Students rotate past sandwiches they do not want — a student with preference 0 will cycle past every type 1 sandwich until a type 0 appears at the top. Crucially, every student who wants the current top sandwich will eventually reach the front of the queue; the circular rotation guarantees this. Queue order only affects which specific student claims a sandwich, not whether the sandwich gets claimed.

The only time progress halts is when the top sandwich has type t and count[t] is zero — meaning no remaining student wants type t. At that point, no amount of rotation will help: every student will refuse the top sandwich, and the queue will spin forever. This is the termination condition.

This insight is the bridge from O(n^2) simulation to O(n) counting. Instead of tracking which student is at the front, you only need to track whether there exist any students with the right preference. The counts encode exactly that information without knowing order.

Consider students = [1, 1, 0, 0] and sandwiches = [0, 1, 0, 1]. First, count preferences: count[0] = 2 (two students prefer type 0), count[1] = 2 (two students prefer type 1).

Now scan sandwiches. Sandwich 0 (top) is type 0: count[0] = 2 > 0, so decrement → count[0] = 1. Sandwich 1 is type 1: count[1] = 2 > 0, decrement → count[1] = 1. Sandwich 2 is type 0: count[0] = 1 > 0, decrement → count[0] = 0. Sandwich 3 is type 1: count[1] = 1 > 0, decrement → count[1] = 0.

The loop completes all four sandwiches without early exit. count[0] + count[1] = 0 + 0 = 0. All students eat; the answer is 0. If instead sandwiches = [1, 0, 0, 0] and count[1] = 0 before any 1-sandwich is seen, the loop breaks at the first sandwich and returns 4 (all students stuck).

Python implementation using Counter: from collections import Counter; def countStudents(students, sandwiches): count = Counter(students); for s in sandwiches: if count[s] == 0: break; count[s] -= 1; return count[0] + count[1]. The Counter handles initialization automatically; missing keys default to 0. Time complexity O(n), space O(1) since only two distinct keys exist.

Java implementation: public int countStudents(int[] students, int[] sandwiches) { int[] count = new int[2]; for (int s : students) count[s]++; for (int s : sandwiches) { if (count[s] == 0) break; count[s]--; } return count[0] + count[1]; }. The int[2] array tracks both counts; the loop exits early the moment a sandwich type has no remaining takers. Both implementations share identical logic — the difference is only syntactic.

Both solutions achieve O(n) time and O(1) space — far simpler than any queue simulation. There is no deque to manage, no rotation counter, no off-by-one in the stopping condition. The counting approach is not only faster but also shorter and less error-prone, making it the ideal solution to present in a coding interview.

Design Circular Queue — LeetCode 622 — asks you to build a fixed-capacity circular queue using an array with head and tail pointers and wrap-around modular arithmetic. This complements LeetCode 1700 by exploring the data structure mechanics underlying queue rotation, the same rotation that the counting approach renders unnecessary.

Implement Stack using Queues — LeetCode 225 — requires simulating LIFO stack behavior using only FIFO queue operations. The push-expensive rotation trick (rotate size-1 elements so the new element reaches the front) is directly analogous to the rotation in LeetCode 1700 and reinforces why counting is often superior to explicit simulation.

Task Scheduler — LeetCode 621 — also converts a scheduling simulation into a counting and math problem. Given tasks with cooldown intervals, the naive simulation tracks every tick; the optimal solution counts task frequencies and applies a formula. The pattern mirrors LeetCode 1700 exactly: identify the invariant (max frequency task determines idle time), skip the simulation, and compute the answer directly from counts.