Number of Students Unable to Eat Lunch - Practice Coding Problems

Number of Students Unable to Eat Lunch - 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 ith sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the jth student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.

Input & Output

Example 1 — All Students Get Fed

$ Input: students = [1,1,0,0], sandwiches = [0,1,0,1]

› Output: 0

💡 Note: First student (wants 1) goes to back. Second student (wants 1) goes to back. Third student (wants 0) takes sandwich 0. Fourth student (wants 0) goes to back. Now sandwich 1 is available, first student takes it. Continue until all are fed.

Example 2 — Some Students Stuck

$ Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]

› Output: 3

💡 Note: After some students get their preferred sandwiches, remaining students all want type 1 but only type 0 sandwiches remain on top, so 3 students cannot eat.

Constraints

1 ≤ students.length, sandwiches.length ≤ 100
students.length == sandwiches.length
sandwiches[i] is 0 or 1
students[i] is 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input

Students queue [1,1,0,0] and sandwich stack [0,1,0,1]

Process

Students either take matching sandwich or go to back of queue

Output

Count of students who remain unable to eat

Key Takeaway

🎯 Key Insight: Count preferences instead of simulating queue operations for O(n) efficiency

Asked in

a Amazon 15 M Microsoft 8

The key insight is that we don't need to simulate the actual queue - we can just count preferences and match them against available sandwiches. The count-based approach is optimal with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Queue Simulation	O(n²)	O(n)	Simulate the actual queue and stack operations step by step
Count-Based Optimization	O(n)	O(1)	Count student preferences and match against sandwich availability

Queue Simulation — Algorithm Steps

Use queue for students and stack index for sandwiches
If front student wants current sandwich, both advance
Otherwise move student to back of queue
Stop when no matches occur in full queue cycle

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Queue of students and stack of sandwiches

Process

Students either take sandwich or go to back

Result

Count remaining students who can't eat

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* students, int studentsSize, int* sandwiches, int sandwichesSize) {
    int* queue = (int*)malloc(studentsSize * sizeof(int));
    for (int i = 0; i < studentsSize; i++) {
        queue[i] = students[i];
    }
    
    int queueStart = 0, queueEnd = studentsSize;
    int sandwichIdx = 0;
    
    while (queueStart < queueEnd && sandwichIdx < sandwichesSize) {
        int cycles = 0;
        int queueSize = queueEnd - queueStart;
        
        while (cycles < queueSize) {
            if (queue[queueStart] == sandwiches[sandwichIdx]) {
                queueStart++;
                sandwichIdx++;
                break;
            } else {
                queue[queueEnd] = queue[queueStart];
                queueStart++;
                queueEnd++;
                cycles++;
            }
        }
        
        if (cycles == queueSize) {
            break;
        }
    }
    
    int result = queueEnd - queueStart;
    free(queue);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse students array
    int students[1000];
    int studentsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        students[studentsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    // Parse sandwiches array
    int sandwiches[1000];
    int sandwichesSize = 0;
    token = strtok(line + 1, ",]");
    while (token != NULL) {
        sandwiches[sandwichesSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(students, studentsSize, sandwiches, sandwichesSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

In worst case, each student may cycle through queue n times

⚠ Quadratic Growth

Space Complexity

O(n)

Queue data structure stores up to n students

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Queue Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler