### View *Number of Students Unable to Eat Lunch* on LeetCode

## Statistics

**Time Spent Coding**

15 minutes

**Time Complexity**

O(n) - The expected time complexity is some multiple of n; the multiple varies depending on the input lists. However, since multiples of n do not increase the big-O complexity, the reported time complexity is O(n).

**Space Complexity**

O(n) - Every student must be stored in the queue, resulting in the O(n) space complexity.

**Runtime Beats**

48.79% of other submissions

## Explanation

The program follows the following pattern:

- Record the length of the queue before iteration and store it in
`before_loop`

- Iterate through
`before_loop`

elements

**For each element, execute the following steps** - Check if the first element in the queue is equal to the sandwich at the top of the stack
- If they are equal, remove the student from the queue and the sandwich from the stack
- Else, remove the student from the front of the queue and place him in the back of the queue

- When the for loop of
`before_loop`

ends, check`if before_loop == line (queue):`

If no elements were removed, then return`before_loop,`

since this number equals the number of students unable to eat.`else:`

Go to step 1

- If the queue is depleted, the while loop will fail to execute, meaning all students could eat,
`return 0`

.

## Data Structures Used

**Queue -** A container that holds elements and follows the First In First Out (FIFO) principle, only allowing removal from the front of the container and additions to the back.

**Stack -** A stack is similar to an array, except you are only allowed to push/pop (add/remove) from the end of the stack. A stack follows the first in, last out, or FILO theme.

Since Python already has O(1) push (append) and pop (pop) operations, we do not need to use any libraries; simply reverse `sandwiches.`

**Visual Examples**

Visual representation of a queue, click to view.

Visual of a stack being mutated, click to view

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
queue = deque()
for s in students: queue.append(s)
sandwiches.reverse()
before_loop = len(queue)
while queue:
for _ in range(before_loop):
if queue[0] == sandwiches[-1]:
sandwiches.pop()
queue.popleft()
else:
queue.append(queue.popleft())
else:
if before_loop == len(queue):
return before_loop
else:
before_loop = len(queue)
return 0