Leetcode 1700. Number of Students Unable to Eat Lunch

Problem Explanation:

In this problem, there is a school cafeteria that offers two types of sandwiches: circular (0) and square (1). There is a queue of students, where each student has a preference for either circular or square sandwiches. There are an equal number of students and sandwiches.

The sandwiches are placed in a stack, with the top sandwich denoted as index 0. The students are also given in an array format, with the student at the front of the queue being index 0.

At each step, the student at the front of the queue checks if the top sandwich matches their preference. If it does, they take the sandwich and leave the queue. If it doesn't, they move to the end of the queue.

This process continues until there are no more students wanting to take the top sandwich, in which case they are unable to eat. The goal of the problem is to return the number of students who are unable to eat.

Problem Approach:

A simple approach to solve this problem is to use a while loop that iterates through the students and sandwiches arrays. In each iteration, we check if the front student's preference matches the top sandwich type. If it does, we dequeue the student and pop the sandwich from sandwiches array. Otherwise, the front student moves to the back of the queue.

We also need to keep track of whether there is any progress in the loop to decide if we reached a point where no more students are willing to eat the top sandwich. In such a case, we will break the loop and return the length of the remaining students.

Let's walk through an example:

• students = [1,1,0,0], sandwiches = [0,1,0,1]
  1. First student (1) moves to the end since the top sandwich is 0. ([1,0,0,1], [0,1,0,1])
  2. Second student (0) take top sandwich (0). ([0,1,1], [1,0,1])
  3. Third student (1) takes top sandwich (1). ([0,0], [0,1])
  4. Fourth student (0) takes top sandwich (0). ([1], [1])
  5. Fifth student (1) takes top sandwich (1). ([], [])

Output: 0 as there are no remaining students in the queue.

Now let's implement the solution in different languages.

Python Solution

1class Solution:
2    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
3        while True:
4            progress = False
5            i = 0
6            while i < len(students):
7                if students[i] == sandwiches[0]:
8                    students.pop(i)
9                    sandwiches.pop(0)
10                    progress = True
11                else:
12                    i += 1
13            if not progress:
14                break
15        return len(students)

Java Solution

1import java.util.*;
2
3class Solution {
4    public int countStudents(int[] students, int[] sandwiches) {
5        Queue<Integer> queue = new LinkedList<>();
6        for (int student : students) {
7            queue.add(student);
8        }
9        
10        int i = 0;
11        while (!queue.isEmpty()) {
12            int size = queue.size();
13            boolean progress = false;
14            
15            for (int j = 0; j < size; j++) {
16                int preference = queue.poll();
17                if (preference == sandwiches[i]) {
18                    i++;
19                    progress = true;
20                } else {
21                    queue.add(preference);
22                }
23            }
24            if (!progress) {
25                break;
26            }
27        }
28        return queue.size();
29    }
30}

JavaScript Solution

1var countStudents = function(students, sandwiches) {
2    while (true) {
3        let progress = false;
4        let i = 0;
5        while (i < students.length) {
6            if (students[i] === sandwiches[0]) {
7                students.splice(i, 1);
8                sandwiches.shift();
9                progress = true;
10            } else {
11                i++;
12            }
13        }
14        if (!progress) {
15            break;
16        }
17    }
18    return students.length;
19};

C++ Solution

1#include <vector>
2#include <queue>
3
4using namespace std;
5
6class Solution {
7public:
8    int countStudents(vector<int>& students, vector<int>& sandwiches) {
9        queue<int> queue;
10        for (int student : students) {
11            queue.push(student);
12        }
13
14        int i = 0;
15        while (!queue.empty()) {
16            int size = queue.size();
17            bool progress = false;
18
19            for (int j = 0; j < size; j++) {
20                int preference = queue.front();
21                queue.pop();
22                if (preference == sandwiches[i]) {
23                    i++;
24                    progress = true;
25                } else {
26                    queue.push(preference);
27                }
28            }
29            if (!progress) {
30                break;
31            }
32        }
33        return queue.size();
34    }
35};

C# Solution

1using System.Collections.Generic;
2
3public class Solution {
4    public int CountStudents(int[] students, int[] sandwiches) {
5        Queue<int> queue = new Queue<int>();
6        foreach (int student in students) {
7            queue.Enqueue(student);
8        }
9
10        int i = 0;
11        while (queue.Count > 0) {
12            int size = queue.Count;
13            bool progress = false;
14
15            for (int j = 0; j < size; j++) {
16                int preference = queue.Dequeue();
17                if (preference == sandwiches[i]) {
18                    i++;
19                    progress = true;
20                } else {
21                    queue.Enqueue(preference);
22                }
23            }
24            if (!progress) {
25                break;
26            }
27        }
28        return queue.Count;
29    }
30}

Each of these solutions demonstrates a different way of implementing the same algorithm to solve the problem. Notice that all the solutions follow the same pattern:

1. Create a queue data structure to hold the students' preferences in the order they appear in the input array.
2. Iterate through the queue until it's empty, dequeueing and checking each student's preference against the top sandwich. a. If a match is found, remove the sandwich from the stack and continue with the next student. b. If a match is not found, enqueue the student back to the end of the queue.
3. Break the loop if no progress is made in an entire iteration through the queue.
4. Return the length (or size) of the remaining queue as the number of students unable to eat a sandwich.

Remember that the key to solving this problem is to use a queue data structure and iterate through it while making sure to keep track of progress made in each iteration. This way, we can determine when no more students are willing to eat the top sandwich and need to stop the process.