Abstract / Summary

Count how many students cannot eat lunch when some students share their sandwiches with others based on rules.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 80% (400k+ submissions).

Typical patterns to solve this problem:

• Array
• Queue
• Simulation
• Stack

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method countStudents. The method receives two lists: students, representing the preferences of a line of students (0 for circular, 1 for square), and sandwiches, representing the order of sandwiches in the stack (0 for circular, 1 for square). The goal is to determine how many students will remain unable to eat because the sandwich at the top of the stack never matches any remaining student's preference.

The algorithm simulates the process by repeatedly examining the first student and the first sandwich. If they match, both are removed from their respective lists; otherwise, the student is moved to the end of the line. The loop terminates when a full pass through the current student line occurs without any match, at which point the remaining number of students is returned.

Key Steps

Initialization

pick = 0  # last time someone got a matching sandwich

The variable pick counts how many consecutive students have been examined without a successful match. It starts at zero, indicating that no student has yet been served.

Main Loop

while True:
    if pick >= len(students):
        break
    pick += 1

The loop runs indefinitely until the termination condition is met. The condition pick >= len(students) checks whether the algorithm has examined every student in the current line without finding a match. When this happens, the loop exits because no further progress is possible.

Matching Case

if students[0] == sandwiches[0]:
    students.pop(0)
    sandwiches.pop(0)
    pick = 0

When the first student's preference equals the type of the sandwich on top of the stack, both are removed using pop(0). The pick counter is reset to zero because a successful match has occurred, allowing the algorithm to start a fresh count of consecutive mismatches from the next iteration.

Rotation Case

else:
    s = students.pop(0)
    students.append(s)

If the first student does not like the current sandwich, the student is removed from the front of the list and appended to the end, effectively rotating the queue. The pick counter is not reset, so the algorithm continues counting mismatches.

Return Value

return len(students)

After the loop terminates, the length of the remaining students list is returned, representing the number of students who cannot be served.

Edge Cases Handled

When the students list is empty at the start, the condition pick >= len(students) evaluates to True immediately because len(students) is zero, causing the loop to break and the method to return zero. This correctly reflects that no students are left to serve.

If every student’s preference matches the sandwich at the top of the stack on each iteration, the matching block removes both elements and resets pick to zero each time. The loop continues until either list becomes empty, and the final return yields zero, indicating that all students have been served.

When none of the remaining students ever match the current sandwich, the rotation case moves each student to the back of the line. After len(students) rotations without a match, pick reaches the length of the list, triggering the break condition. The algorithm then returns the full size of the students list, correctly indicating that no further sandwiches can be consumed.

Performance Optimizations Observed

The algorithm avoids an explicit infinite loop by using the pick counter as a sentinel that detects a full pass without progress. By resetting pick to zero only after a successful match, the code ensures that the loop terminates as soon as it becomes impossible for any remaining student to obtain a sandwich, preventing unnecessary additional rotations.

The use of pop(0) and append directly manipulates the underlying list structures without creating auxiliary collections. Although each pop(0) operation shifts elements, the early exit condition limits the number of such operations to the minimum required to reach a stable state, thereby reducing overall work compared to a naïve simulation that would continue indefinitely.

Overall, the method provides a concise simulation that terminates promptly once the outcome is determinable.

Imagine a long line of hungry children waiting to eat. Each child wants a specific kind of snack, and there is a big stack of snacks waiting for them at the front of the line. The first child in line looks at the snack on top of the pile.

If the child loves that snack, they take it and leave the line happily. When that happens, the snack is gone, and the next snack is ready for the person behind them. Because the child was happy, the counting starts all over again for the next person in line.

If the child does not like the snack, they have to go all the way to the back of the line to wait for another turn. This keeps shuffling around as long as there is someone who might want to eat the snack that is currently waiting on top of the pile.

The process continues over and over until everyone left in line has already had a turn to look at the snack but decided they did not want it. Once everyone in line has tried and failed to find a snack they like, the waiting comes to an end.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java			Go	C	Rust	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	DimitrisJim			JS
	everthis			JS
	fartem						Ruby
	fsq	C++
	halfrost							Go
	haoel	C++
	JoshCrozier			JS
	lkwq007		Python
	shreymehul					C#
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	JavaScript
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality