✅ Java || Beats 100%  || Time O(n) || Space O(1) || Easy Explained || Classic Approach ✅
\n\n---\n# Approach 1 - Time O(n) | Space O(1)\n\n# Intuition\nThe problem involves determining the number of students who won\'t get a sandwich. We can approac
![image.png](https://assets.leetcode.com/users/images/bbab0d05-e7ac-455d-897e-6d2a33bfb6f2_1712539903.7154071.png)\n\n---\n# Approach 1 - Time O(n) | Space O(1)\n\n# Intuition\nThe problem involves determining the number of students who won\'t get a sandwich. We can approach this problem by counting the number of students preferring each type of sandwich and then iterating through the sandwiches array to check if there are enough sandwiches of the preferred type for each student.\n\n# Approach\n1. First, we count the number of students preferring each type of sandwich (0 or 1) by iterating through the students array. We maintain separate counts for type 0 (count of students preferring type 0 sandwiches) and type 1 (count of students preferring type 1 sandwiches).\n2. Next, we iterate through the sandwiches array. While iterating, we check the preference of each sandwich:\n   - If the sandwich preference is 0 and there are no students left who prefer type 0 sandwiches (`cc == 0`), we return the count of students preferring type 1 sandwiches (`sc`). Similarly, if the preference is 1 and there are no students left who prefer type 1 sandwiches (`sc == 0`), we return the count of students preferring type 0 sandwiches (`cc`).\n   - If the sandwich preference is 0 and there are students who prefer type 0 sandwiches (`cc > 0`), we decrement the count of students preferring type 0 sandwiches (`cc--`).\n   - If the sandwich preference is 1 and there are students who prefer type 1 sandwiches (`sc > 0`), we decrement the count of students preferring type 1 sandwiches (`sc--`).\n3. After iterating through all sandwiches, if there are no return statements encountered, it means all students have received sandwiches, and we return 0.\n\n# Complexity\n- Time complexity: O(n), where n is the maximum of the lengths of the students and sandwiches arrays. We iterate through both arrays once.\n- Space complexity: O(1). We use only a constant amount of extra space for storing counts of students preferring each type of sandwich.\n\n# Code\n```java\nclass Solution {\n    public int countStudents(int[] students, int[] sandwiches) {\n        int cc = 0, sc = 0;\n        \n        // Count the number of students preferring each type of sandwich\n        for (int n : students) {\n            if (n == 0) cc++; // Count of students preferring type 0 sandwiches\n            else sc++;       // Count of students preferring type 1 sandwiches\n        }\n        \n        // Iterate through the sandwiches array and serve sandwiches to students\n        for (int s : sandwiches) {\n            // Check the preference of each sandwich\n            if (s == 0 && cc == 0) return sc; // Return count of students preferring type 1 sandwiches if no type 0 sandwiches left\n            if (s == 1 && sc == 0) return cc; // Return count of students preferring type 0 sandwiches if no type 1 sandwiches left\n            \n            // Serve the sandwich based on preference\n            if (s == 0) cc--; // Decrement count of students preferring type 0 sandwiches\n            else sc--;       // Decrement count of students preferring type 1 sandwiches\n        }\n        \n        // Return 0 if all students receive sandwiches\n        return 0;\n    }\n}\n```\n\n---\n# Approach 1 - Time O(n) | Space O(n) Classic Solution (Simulation)\n\n\n## Intuition\nThe problem presents a scenario where there are students standing in a queue, each having a preference for a particular type of sandwich. The sandwiches are represented by an array, and the students are represented by another array. The task is to determine the number of students who will not get a sandwich.\n\n## Approach\nTo solve this problem, we can simulate the process of serving sandwiches to the students using a stack and a queue. Here\'s the step-by-step approach:\n1. Initialize a stack to represent the sandwiches and a queue to represent the students. Both structures will store the preferences in reverse order to facilitate efficient processing.\n2. Iterate through the sandwiches array in reverse order. Push each sandwich preference onto the stack.\n3. Iterate through the students array in reverse order. Enqueue each student preference into the queue.\n4. Initialize a variable `skipCount` to keep track of consecutive students who couldn\'t get their preferred sandwich.\n5. While `skipCount` is less than the size of the stack (remaining sandwiches) and the queue is not empty:\n   - Check if the preference of the student at the front of the queue matches the sandwich at the top of the stack:\n     - If they match, it means the student gets the sandwich. Dequeue the student and pop the sandwich from the stack.\n     - Reset `skipCount` to zero.\n   - If they don\'t match, it means the student doesn\'t get the sandwich. Enqueue the student again to simulate skipping them in the serving process.\n     - Increment `skipCount`.\n6. After the loop, return the size of the queue, which represents the number of students who didn\'t get a sandwich.\n\n## Complexity\n- Time complexity: O(n), where n is the maximum of the lengths of the students and sandwiches arrays. We iterate through both arrays once.\n- Space complexity: O(n) for the stack and queue used in the algorithm. Each student and sandwich is stored once in the respective data structures. \n\n## Code\n```java\nclass Solution {\n    public int countStudents(int[] students, int[] sandwiches) {\n        Stack<Integer> stack = new Stack<>();\n        Queue<Integer> queue = new ArrayDeque<>();\n        \n        // Initialize the stack with sandwich preferences in reverse order\n        for (int i = sandwiches.length - 1; i >= 0; i--) {\n            stack.push(sandwiches[i]);\n        }\n        \n        // Initialize the queue with student preferences in reverse order\n        for (int i = students.length - 1; i >= 0; i--) {\n            queue.offer(students[i]);\n        }\n        \n        int skipCount = 0;\n        // Process the sandwich serving until all sandwiches are served or students are skipped\n        while (skipCount < stack.size() && !queue.isEmpty()) {\n            if (queue.peek() == stack.peek()) {\n                // Serve the sandwich to the student\n                queue.poll();\n                stack.pop();\n                skipCount = 0; // Reset the skip count\n            } else {\n                // Skip the student\n                skipCount++;\n                queue.offer(queue.poll());\n            }\n        }\n        \n        // Return the number of students who couldn\'t get a sandwich\n        return queue.size();\n    }\n}\n```\n\n
['Array', 'Stack', 'Queue', 'Simulation', 'Java']