💬 Discord
Sign In
NeetCode #85LC-1700EasyArrays & Hashing
← Back to All Problems

#85 · #1700 · Number of Students Unable to Eat Lunch(无法吃午餐的学生数量)

📌 Problem Statement & Constraints

Students queue for lunch. students[i] is the sandwich preference of the i-th student (0 or 1) and sandwiches[j] is the type of the j-th sandwich in the stack (top first). Each student at the front either takes the top sandwich if it matches, or goes to the back. Return the number of students unable to eat. Constraints: 1 <= students.length == sandwiches.length <= 100.

💡 Core Algorithmic Approaches

  1. Simulating the queue literally is O(n^2) in the worst case, because a student may cycle through the queue many times.
  2. The key insight: if the top sandwich matches nobody in the queue, nobody will ever eat again, and the process halts.
  3. So count how many students prefer each type, then consume sandwiches from the top: decrement the matching count, and stop as soon as the top sandwich's type has zero remaining students.
  4. The answer is the number of students still left, which is the sum of the remaining counts.

💻 Benchmark Python3 Implementation

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        from collections import Counter
        cnt = Counter(students)
        for s in sandwiches:               # top of the stack first
            if cnt[s] == 0:                # no student wants this sandwich -> stuck
                break
            cnt[s] -= 1
        return sum(cnt.values())

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass to count and one pass over the sandwiches, with no queue simulation.
💾 Space Complexity
O(1): the counter has at most two entries.

⚠️ Interview Pitfalls & Follow-ups

  • Simulating the queue with a deque: correct but O(n^2) worst case; the counting insight makes it linear.
  • Continuing past an unconsumable sandwich: once the top sandwich has no taker, the process is permanently stuck, so break immediately.
  • Counting the sandwiches instead of the students: you need to know which preferences remain.
  • Returning the number of consumed sandwiches: the answer is the number of students unable to eat.