Number of Students unable to eat Lunch

Problem Link

1700. Number of Students Unable to Eat Lunch – LeetCode

Problem Statement

The school cafeteria offers lunch with two types of sandwiches:

• Type 0: circular

• Type 1: square

Each student prefers either type 0 or type 1. All students stand in a queue. At each step:

• If the student at the front of the queue prefers the sandwich on the top of the stack, they take it and leave the queue.

• Otherwise, they go to the end of the queue.

This process continues until none of the students want the top sandwich.

Return the number of students unable to eat.

Examples

Example 1:

Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0
Explanation:
- Student 0 (1) doesn't want 0 → move to back
- Student 1 (1) doesn't want 0 → move to back
- Student 2 (0) takes 0 → leaves
- Student 3 (0) takes 0 → leaves
- Student 0 (1) takes 1 → leaves
- Student 1 (1) takes 1 → leaves
All students are served

Example 2:

Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
Output: 3

Constraints

• 1 <= students.length == sandwiches.length <= 100

• students[i] is 0 or 1

• sandwiches[i] is 0 or 1

Intuition

Instead of simulating the entire queue rotation (which could be slow and repetitive), observe that:

• The only time the process halts is when the remaining students do not want the top sandwich.

• So we can just count the number of students who prefer circular (0) or square (1).

• As we iterate through the sandwich stack:

  • If someone prefers the top, we serve them (decrease count).

  • If no one prefers the current sandwich, stop and return remaining students.

Approach: Greedy with Count Tracking

1. Count how many students want:

   • cir → circular sandwiches (0)

   • sqr → square sandwiches (1)

2. Traverse through the sandwiches array:

   • If the current top is 0 and cir > 0, serve one → cir--

   • If the current top is 1 and sqr > 0, serve one → sqr--

   • If the top sandwich has no matching student, return cir + sqr

3. If all are served, return 0

Java Code

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int cir = 0;
        int sqr = 0;

        for (int i : students) {
            if (i == 1) sqr++;
            else cir++;
        }

        for (int i : sandwiches) {
            if (i == 1 && sqr > 0) {
                sqr--;
            } else if (i == 0 && cir > 0) {
                cir--;
            } else {
                return cir + sqr;
            }
        }

        return 0;
    }
}

Time and Space Complexity

Dry Run

Input:

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

Counters:

• sqr = 4

• cir = 2

Processing:

• 1 → sqr = 3

• 0 → cir = 1

• 0 → cir = 0

• 0 → no circular left → stop
  → Remaining = 3 (students who prefer 1)

Conclusion

This problem can be efficiently solved using counting instead of full queue simulation. It teaches a key competitive programming insight:

If a simulation involves only matching of types, frequency counting often leads to linear-time solutions.