LeetCode #1700 Number of Students Unable to Eat Lunch Solution & Explanation

LeetCode Problem

The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers 0 and 1 respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.

The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a stack. At each step:

• If the student at the front of the queue prefers the sandwich on the top of the stack, they will take it and leave the queue.
• Otherwise, they will leave it and go to the queue’s end.

This continues until none of the queue students want to take the top sandwich and are thus unable to eat.

You are given two integer arrays students and sandwiches where sandwiches[i] is the type of the i^{​​​​​​th} sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the j^{​​​​​​th} student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.

Example 1:

Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0 
Explanation:
- Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1].
- Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0].
- Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,1].
- Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1].
- Front student takes the top sandwich and leaves the line making students = [] and sandwiches = [].
Hence all students are able to eat.

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.length == sandwiches.length
• sandwiches[i] is 0 or 1.
• students[i] is 0 or 1.

Solution

In our initial solution, we leveraged the FIFO (First In, First Out) property of the Queue data structure to simulate the scenario where students, unable to eat their preferred sandwich, move to the end of the queue.

The outer loop of our solution was implemented using a foreach loop to iterate through the current state of the sandwiches.

C# Solution

Solution1 – Queue

public class Solution {
    public int CountStudents(int[] students, int[] sandwiches) {
        Queue<int> queue = new Queue<int>(students);
        int tmp = 0;

        foreach(var sandwich in sandwiches){
            while (queue.Count>0){
                var student = queue.Dequeue();
                if(sandwich==student){
                    tmp=0;
                    break;
                }
                else{
                    if(tmp==queue.Count){
                        return queue.Count+1;
                    }
                    tmp+=1;
                    queue.Enqueue(student);
                }
            }
        }

        return 0;
    }
}

The variable tmp serves as a counter to track the number of students checked during one iteration of the loop.

queue.Count represents the current number of students in the queue who have not yet been checked. When tmp equals queue.Count, it means all queued students have inspected the current top sandwich, and none of them prefer this type of sandwich.

Therefore, we need to return queue.Count + 1. This is because we already used queue.Dequeue() earlier to remove the first student from the queue, indicating that this student cannot eat the sandwich, so we need to include this student in the count.

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks a lot

✅If you got any problem about the explanation, please feel free to let me know

The problem link : Number of Students Unable to Eat Lunch – LeetCode

Some Random LeetCode posts