algoadvance

Leetcode 1700. Number of Students Unable to Eat Lunch

Problem Statement

The problem is defined on LeetCode as follows:

The school cafeteria offers circular and square sandwiches at lunch break, referred to as 0s and 1s respectively. All students stand in a queue. Each student either prefers square sandwiches 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:

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.

Clarifying Questions

  1. Q: Are the students and sandwiches arrays guaranteed to have the same length?
    • A: Yes, the problem states that the number of sandwiches is equal to the number of students.
  2. Q: Can we assume all input values are valid and within the problem’s constraints?
    • A: Yes, you can assume valid inputs within the described constraints.
  3. Q: What are the possible values in students and sandwiches arrays?
    • A: Both arrays contain only the integers 0 and 1 representing the types of sandwiches and student preferences.

Strategy

  1. Initialize Count Variables:
    • We will count the number of 0s and 1s in the student’s preference list.
  2. Iterate Through Sandwiches:
    • For each sandwich on top of the stack, check if there’s a student to take it based on the counted preferences.
    • If a student takes a sandwich, decrement the respective count.
  3. Stopping Condition:
    • The iteration stops early if no more students can take the current top sandwich, i.e., when no students of the preferred type are left.

Code

public class Solution {
    public int countStudents(int[] students, int[] sandwiches) {
        int count0 = 0, count1 = 0;
        
        // Count preference of students
        for (int student : students) {
            if (student == 0) count0++;
            else count1++;
        }

        // Iterate through the sandwiches stack.
        for (int sandwich : sandwiches) {
            if (sandwich == 0) {
                if (count0 > 0)
                    count0--;
                else
                    return count1; // no students who prefer 0 left, return remaining students
            } else {
                if (count1 > 0)
                    count1--;
                else
                    return count0; // no students who prefer 1 left, return remaining students
            }
        }

        return 0; // All students could eat
    }
}

Time Complexity

Thus, the total time complexity is O(n).

This solution efficiently uses counting and directly processes the sandwich stack, optimizing for both clarity and performance.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI