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

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

✓ Count-Based Optimization

⏱️ Time: O(n) Space: O(1)

Instead of simulating the queue, count how many students want each type of sandwich. Process sandwiches in order and decrease counts. When we can't satisfy current sandwich, remaining students are stuck.

Queue Simulation

⏱️ Time: O(n²) Space: O(n)

Use actual queue and stack data structures to simulate the process. Keep moving students to back of queue until either they get their sandwich or no progress is made.

Count-Based Optimization — Algorithm Steps

Count students who want type 0 and type 1 sandwiches
Process sandwiches from top to bottom
If current sandwich type has waiting students, serve one
If no students want current sandwich, all remaining are stuck

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Preferences

Count how many students want each sandwich type

Process Stack

Go through sandwiches and decrement counts when possible

Return Remaining

Sum of remaining counts is answer

Code -

solution.c — C

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

int solution(int* students, int studentsSize, int* sandwiches, int sandwichesSize) {
    int count[2] = {0, 0};
    for (int i = 0; i < studentsSize; i++) {
        count[students[i]]++;
    }
    
    for (int i = 0; i < sandwichesSize; i++) {
        if (count[sandwiches[i]] > 0) {
            count[sandwiches[i]]--;
        } else {
            break;
        }
    }
    
    return count[0] + count[1];
}

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse students array
    int students[1000];
    int studentsSize = 0;
    parseArray(line, students, &studentsSize);
    
    fgets(line, sizeof(line), stdin);
    // Parse sandwiches array
    int sandwiches[1000];
    int sandwichesSize = 0;
    parseArray(line, sandwiches, &sandwichesSize);
    
    printf("%d\n", solution(students, studentsSize, sandwiches, sandwichesSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through students to count, single pass through sandwiches

⚠ Quadratic Growth

Space Complexity

O(1)

Only two counters needed for sandwich preferences

⚡ 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

Number of Students Unable to Eat Lunch - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Count-Based Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler