Number of Students Unable to Eat Lunch

1. Define the problem

Number of Students Unable to Eat Lunch

Students stand in a queue and sandwiches sit in a stack. Each student wants either type 0 or type 1. The student at the front looks at the sandwich on top: if it matches they take it and leave, otherwise they go to the back of the queue . Return how many students never get to eat . Simulate it exactly as described. The only thing you need to watch for is a stuck queue: if every student in the queue has gone to the back once without a single match, nobody left can ever eat, so stop.

Constraints

1 ≤ students.length ≤ 100
students.length === sandwiches.length
Every value is either 0 or 1
students_i is what that student wants, sandwiches_i is the sandwich at position i in the stack

Example

Inputstudents = [1, 1, 0], sandwiches = [0, 0, 1]

Output2

Explanation The student wanting 0 eats the first sandwich. The next sandwich on top is also 0, but both remaining students want 1, so they circle forever and 2 students go hungry.

2. Know the words first

In plain terms

Queue: A line where you only remove from the front and only add at the back. A student who refuses a sandwich rejoins at the back.
Stack of sandwiches: A pile where only the top sandwich is available. It never changes unless a student actually takes the top one.
Stuck queue: The state where a full lap of the queue happens with no match. Since the top sandwich never changed, another lap would give the same result, so the simulation can stop.

3. Visualize the solution

One row of cells is the student queue, front on the left

0 · front1

2 · back0

Statusinit

Three students want 1, 1, 0. The sandwich stack from the top is 0, 0, 1.

What happens in this step

queue = [1, 1, 0]
sandwich index = 0, top sandwich = 0
rotations without a match = 0

The front student wants 1 but the top sandwich is 0, so no match yet.

Step 1 of 7

Steps to visualize

The front student compares their choice with the sandwich on top of the stack.
If they match, the student leaves and everyone shifts one slot to the left.
If they do not match, that student moves to the back and the row rotates.
A counter tracks how many students in a row have refused. When it reaches the queue length, stop.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One row of cells is the student queue, front on the left

0 · front1

2 · back0

Statusinit

Three students want 1, 1, 0. The sandwich stack from the top is 0, 0, 1.

What happens in this step

queue = [1, 1, 0]
sandwich index = 0, top sandwich = 0
rotations without a match = 0

The front student wants 1 but the top sandwich is 0, so no match yet.

Step 1 of 7

5. Solution

Solution

solution.tsTypeScript

function countStudents(students, sandwiches) {
  const queue = students.slice();
  let index = 0;
  let rotations = 0;

  while (queue.length > 0 && rotations < queue.length) {
    if (queue[0] === sandwiches[index]) {
      queue.shift();
      index++;
      rotations = 0;
    } else {
      queue.push(queue.shift());
      rotations++;
    }
  }

  return queue.length;
}

Time: O(n^2) in the worst case
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`students = [1, 1, 0], sandwiches = [0, 0, 1]`	`2`	example from the docstring, the queue gets stuck
`students = [1, 1, 0, 0], sandwiches = [0, 1, 0, 1]`	`0`	rotations eventually let every student eat
`students = [1, 1, 1, 0, 0, 1], sandwiches = [1, 0, 0, 0, 1, 1]`	`3`	a larger queue where some students are left over
`students = [0, 0], sandwiches = [1, 1]`	`2`	no student ever matches, the degenerate case
`students = [1], sandwiches = [1]`	`0`	smallest possible input
`students = [0, 1, 0, 1], sandwiches = [0, 1, 0, 1]`	`0`	every student matches straight away, no rotation needed

Number of Students Unable to Eat Lunch