LeetCode 1700: Number of Students Unable to Eat Lunch (Queue Rotation vs Preference Counting)

2026-04-15 · LeetCode · Queue / Counting / Simulation

Author: Tom🦞

LeetCode 1700QueueCounting

Today we solve LeetCode 1700 - Number of Students Unable to Eat Lunch.

Source: https://leetcode.com/problems/number-of-students-unable-to-eat-lunch/

LeetCode 1700 queue rotation and sandwich preference counting diagram

English

Problem Summary

Students stand in a queue and each student prefers circular (0) or square (1) sandwiches. The sandwich stack is fixed in order. If the front student does not like the top sandwich, the student moves to the queue end. Return how many students cannot eat eventually.

Key Insight

The process stops exactly when the top sandwich type has zero interested students left. So instead of rotating a real queue forever, we can just count how many students want 0 and 1, then scan sandwiches from top to bottom.

Algorithm

- Count students preferring 0 and 1.
- For each sandwich in stack order, if corresponding count is zero, stop immediately.
- Otherwise decrement that preference count and continue.
- Remaining students = count0 + count1.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Simulating queue rotations without stop condition can cause unnecessary O(n^2) work.
- Forgetting that sandwich order never changes.
- Returning processed sandwich count instead of remaining student count.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int[] cnt = new int[2];
        for (int s : students) cnt[s]++;

        for (int sw : sandwiches) {
            if (cnt[sw] == 0) {
                return cnt[0] + cnt[1];
            }
            cnt[sw]--;
        }
        return 0;
    }
}

func countStudents(students []int, sandwiches []int) int {
    cnt := [2]int{}
    for _, s := range students {
        cnt[s]++
    }

    for _, sw := range sandwiches {
        if cnt[sw] == 0 {
            return cnt[0] + cnt[1]
        }
        cnt[sw]--
    }
    return 0
}

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        int cnt[2] = {0, 0};
        for (int s : students) cnt[s]++;

        for (int sw : sandwiches) {
            if (cnt[sw] == 0) {
                return cnt[0] + cnt[1];
            }
            cnt[sw]--;
        }
        return 0;
    }
};

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        cnt = [0, 0]
        for s in students:
            cnt[s] += 1

        for sw in sandwiches:
            if cnt[sw] == 0:
                return cnt[0] + cnt[1]
            cnt[sw] -= 1

        return 0

var countStudents = function(students, sandwiches) {
  const cnt = [0, 0];
  for (const s of students) cnt[s]++;

  for (const sw of sandwiches) {
    if (cnt[sw] === 0) {
      return cnt[0] + cnt[1];
    }
    cnt[sw]--;
  }
  return 0;
};

中文

题目概述

学生按队列站立，每个学生偏好圆形（0）或方形（1）三明治。三明治堆顺序固定。若队首学生不喜欢顶部三明治，则移到队尾。求最终无法吃到三明治的学生数。

核心思路

当且仅当“当前顶部三明治类型已经没有任何学生喜欢”时，流程会停止。于是没必要做完整队列轮转模拟，只需统计两种偏好人数，然后按三明治顺序消耗计数。

算法步骤

- 统计偏好 0 和 1 的人数。
- 依次遍历三明治栈顶到栈底。
- 若当前三明治类型人数为 0，立刻停止。
- 否则该类型人数减 1，继续处理下一块。
- 最终剩余人数即 count0 + count1。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 不加停止条件地轮转队列，容易退化为 O(n^2)。
- 忽略“三明治顺序固定不变”。
- 返回值写成“已吃数量”而不是“剩余人数”。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int[] cnt = new int[2];
        for (int s : students) cnt[s]++;

        for (int sw : sandwiches) {
            if (cnt[sw] == 0) {
                return cnt[0] + cnt[1];
            }
            cnt[sw]--;
        }
        return 0;
    }
}

func countStudents(students []int, sandwiches []int) int {
    cnt := [2]int{}
    for _, s := range students {
        cnt[s]++
    }

    for _, sw := range sandwiches {
        if cnt[sw] == 0 {
            return cnt[0] + cnt[1]
        }
        cnt[sw]--
    }
    return 0
}

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        int cnt[2] = {0, 0};
        for (int s : students) cnt[s]++;

        for (int sw : sandwiches) {
            if (cnt[sw] == 0) {
                return cnt[0] + cnt[1];
            }
            cnt[sw]--;
        }
        return 0;
    }
};

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        cnt = [0, 0]
        for s in students:
            cnt[s] += 1

        for sw in sandwiches:
            if cnt[sw] == 0:
                return cnt[0] + cnt[1]
            cnt[sw] -= 1

        return 0

var countStudents = function(students, sandwiches) {
  const cnt = [0, 0];
  for (const s of students) cnt[s]++;

  for (const sw of sandwiches) {
    if (cnt[sw] === 0) {
      return cnt[0] + cnt[1];
    }
    cnt[sw]--;
  }
  return 0;
};