Number of Students Unable to Eat Lunch

How it works

The key insight is that student order does not matter. Since students can rotate indefinitely, what matters is whether there exists any student who wants the current top sandwich. If we track how many students want each type (0 or 1), we can quickly check availability without simulating the queue.

Steps

1. Count the number of students preferring each sandwich type.
2. Process sandwiches in order:
   • If at least one student wants the current sandwich, decrement that count and the total remaining.
   • If no student wants it, stop immediately since those behind cannot be served either.
3. Return the remaining count.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Simulating Instead of Counting

The naive approach of simulating the full queue rotation process leads to O(n^2) time complexity. The key insight is that student order does not matter since they can rotate indefinitely. Simply counting how many students prefer each sandwich type is sufficient.

Not Recognizing the Stopping Condition

The process stops when the top sandwich cannot be taken by any remaining student, not when all sandwiches are processed. If no student wants the current top sandwich, all remaining students will be unable to eat, even if later sandwiches in the stack match their preferences.

from typing import List
from collections import Counter

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        res = len(students)
        cnt = Counter(students)

        for s in sandwiches:
            if cnt[s] > 0:
                res -= 1
                cnt[s] -= 1
            else:
                break

        return res

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        int res = students.size();
        vector<int> cnt(2);
        for (int& student : students) {
            cnt[student]++;
        }

        for (int& s : sandwiches) {
            if (cnt[s] > 0) {
                cnt[s]--;
                res--;
            } else {
                break;
            }
        }
        return res;
    }
};