We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Students Unable to Eat Lunch

Difficulty: Easy

Problem Description

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.

Key Insights

  • Students only take sandwiches if their preference matches the top sandwich.
  • If a student does not take a sandwich, they go to the end of the queue.
  • The process continues until a student does not want the sandwich on top, and they cannot get another one.
  • The problem can be efficiently solved using a queue to simulate the students' behavior.

Space and Time Complexity

Time Complexity: O(n), where n is the number of students (or sandwiches). Space Complexity: O(n), for storing the queue of students.

Solution

The solution involves simulating the queue behavior of students using a list. We can maintain a count of the number of sandwiches each type (0 and 1) available and the number of students who prefer each type. We iterate through the students, checking if they want the top sandwich. If they do, they take it; if not, they move to the end of the queue. This continues until we have a situation where no student wants the sandwich on top. The remaining students in the queue at that point are the ones who cannot eat.

Code Solutions

def countStudents(students, sandwiches):
    from collections import deque

    queue = deque(students)
    top = 0
    count = len(sandwiches)
    
    while count > 0:
        # If the student at the front of the queue takes the sandwich
        if queue[0] == sandwiches[top]:
            queue.popleft()  # Student takes the sandwich
            top += 1  # Move to the next sandwich
            count -= 1  # Decrease the count of sandwiches
        else:
            queue.append(queue.popleft())  # Move the student to the end of the queue
        
        # If a full cycle has occurred without taking a sandwich
        if len(queue) == count:
            break

    return len(queue)  # Students who are unable to eat
← Back to All Questions