Problem Description

You are given two integer arrays: students and sandwiches, both of the same length. Each element in students represents a student's sandwich preference: 0 for circular and 1 for square. The sandwiches array represents a stack of sandwiches in order, where the first element is at the top of the stack.

The serving process is as follows:

• Each student in the queue (in order) checks the top sandwich.
• If their preference matches, they take the sandwich and leave the queue.
• If not, they move to the end of the queue.
• This process repeats until either everyone has eaten or no student wants the top sandwich (in which case the process stops).

Key constraints:

• Each student and sandwich is used at most once.
• There is only one valid solution per input (no ambiguity).

Thought Process

At first glance, the problem seems to suggest simulating the entire process: moving students to the back of the queue if they can't eat, and removing sandwiches as they are taken. This would involve repeatedly rotating the queue and checking preferences, which could be inefficient for large inputs.

However, upon closer inspection, we notice that if no one in the queue wants the top sandwich, the process must stop, and all remaining students are unable to eat. Thus, we only need to keep track of the students' preferences and match them to the sandwiches in order, stopping as soon as a sandwich is encountered that no student wants.

This insight allows us to shift from a brute-force simulation to a more efficient approach, where we simply count preferences and compare them to the sandwiches in order.

Solution Approach

We can solve the problem efficiently by following these steps:

1. Count the number of students preferring each type of sandwich:
   • Count how many students want circular (0) and square (1) sandwiches.
2. Iterate through the sandwiches stack from top to bottom:
   • For each sandwich, check if there is at least one student who prefers it.
   • If yes, decrement the corresponding count and move to the next sandwich.
   • If not, stop the process. All remaining sandwiches cannot be taken, and the remaining students are unable to eat.
3. Return the number of students left who cannot eat:
   • This is the sum of the remaining counts of students preferring each sandwich type.

This approach avoids unnecessary rotations and checks, leading to a much more efficient solution.

Example Walkthrough

Let's consider an example:
Input:
students = [1,1,0,0]
sandwiches = [0,1,0,1]

Step-by-step process:

1. Count student preferences:
   • Students wanting circular (0): 2
   • Students wanting square (1): 2
2. Check sandwiches one by one:
   • First sandwich is 0 (circular): There are 2 students who want it. Serve one, decrement count to 1.
   • Next sandwich is 1 (square): There are 2 students who want it. Serve one, decrement count to 1.
   • Next sandwich is 0 (circular): 1 student left who wants it. Serve, decrement count to 0.
   • Next sandwich is 1 (square): 1 student left who wants it. Serve, decrement count to 0.
3. All sandwiches served, all students have eaten. The answer is 0.

If at any point there are no students left who want the current sandwich, the process stops and the remaining students are counted as unable to eat.

Time and Space Complexity

Brute-force approach:

• Simulating the queue can take O(n²) time in the worst case since each student could be moved to the end of the queue multiple times.
• Space is O(n) for the queue and sandwich stack.

• Counting preferences is O(n).
• Iterating through sandwiches is O(n).
• Total time complexity: O(n).
• Space complexity: O(1) (since we only store two counts, regardless of input size).

Summary

The key insight is recognizing that once no student wants the top sandwich, the process must stop. By counting student preferences and matching them directly to the sandwich stack, we avoid unnecessary simulation and achieve an efficient O(n) solution. This approach is both elegant and practical, especially for large inputs.

Code Implementation

class Solution:
    def countStudents(self, students, sandwiches):
        from collections import Counter
        pref = Counter(students)
        for s in sandwiches:
            if pref[s] == 0:
                return pref[0] + pref[1]
            pref[s] -= 1
        return 0
      

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

class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int[] count = new int[2];
        for (int s : students) count[s]++;
        for (int s : sandwiches) {
            if (count[s] == 0)
                return count[0] + count[1];
            count[s]--;
        }
        return 0;
    }
}
      

var countStudents = function(students, sandwiches) {
    let count = [0, 0];
    for (let s of students) count[s]++;
    for (let s of sandwiches) {
        if (count[s] === 0)
            return count[0] + count[1];
        count[s]--;
    }
    return 0;
};