Number of Students Unable to Eat Lunch

Difficulty: Easy | Acceptance: 79.60% | Paid: No Topics: Array, Stack, Queue, Simulation

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 type 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 i​​​​​​th sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the j​​​​​​th student in the queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.

• Examples
• Constraints
• Simulation
• Counting

Examples

Example 1

Input:

students = [1,1,0,0], sandwiches = [0,1,0,1]

Output:

0

Explanation:

• Front student leaves the top sandwich (0) and goes to the back.
• Front student leaves the top sandwich (0) and goes to the back.
• Front student takes the top sandwich (0) and leaves.
• Front student takes the top sandwich (1) and leaves.
• Front student takes the top sandwich (0) and leaves.
• Front student takes the top sandwich (1) and leaves.

Example 2

Input:

students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]

Output:

3

Constraints

n == students.length == sandwiches.length
1 <= n <= 100
students[i] is 0 or 1.
sandwiches[i] is 0 or 1.

Simulation

Intuition We can directly simulate the process using a queue for students and a stack (or list) for sandwiches. We iterate through the queue, checking if the front student matches the top sandwich. If they match, both are removed. If not, the student moves to the back. We track consecutive failures to detect when no one can eat.

Steps

• Initialize a queue with all students and a stack with all sandwiches.
• Loop while the queue is not empty.
• Maintain a counter for the number of consecutive students who couldn’t eat.
• If the counter equals the queue size, it means no one wants the top sandwich, so break.
• If the front student matches the top sandwich, pop both and reset the counter.
• Otherwise, move the front student to the back of the queue and increment the counter.

class Solution:
    def countStudents(self, students: list[int], sandwiches: list[int]) -> int:
        from collections import deque
        q = deque(students)
        s = deque(sandwiches)
        unable_to_eat = 0
        while q:
            if q[0] == s[0]:
                q.popleft()
                s.popleft()
                unable_to_eat = 0
            else:
                q.append(q.popleft())
                unable_to_eat += 1
            if unable_to_eat == len(q):
                break
        return len(q)

Complexity

• Time: O(n²) in the worst case where n is the number of students, as we might rotate the queue many times.
• Space: O(n) to store the queue and stack.
• Notes: Intuitive but can be inefficient for large inputs.

Counting

Intuition The relative order of students doesn’t strictly matter for the final count, only the number of students preferring 0 and 1. We process sandwiches in order. If a sandwich is 0, we need a student who wants 0. If no students want 0, the process stops.

Steps

• Count the number of students who prefer 0 (count0) and 1 (count1).
• Iterate through the sandwiches array.
• If the current sandwich is 0 and count0 > 0, decrement count0.
• If the current sandwich is 1 and count1 > 0, decrement count1.
• If neither condition is met, return count0 + count1 (the remaining students).

class Solution:
    def countStudents(self, students: list[int], sandwiches: list[int]) -> int:
        count0 = students.count(0)
        count1 = len(students) - count0
        for s in sandwiches:
            if s == 0:
                if count0 == 0:
                    return count1
                count0 -= 1
            else:
                if count1 == 0:
                    return count0
                count1 -= 1
        return 0

Complexity

• Time: O(n) where n is the number of students, as we pass through the arrays once.
• Space: O(1) as we only use a few integer variables.
• Notes: Optimal solution with minimal space usage.