algoadvance

Leetcode 1700. Number of Students Unable to Eat Lunch

Problem Statement

You are given two integer arrays students and sandwiches where students[i] is the type of the i-th student and sandwiches[j] is the type of the j-th sandwich. The ith student in the queue prefers students[i] sandwich, and the jth sandwich in the queue is of type sandwiches[j].

The students are standing in a queue waiting to be served, and they are served in the order they appear in the queue, while the sandwiches are given out in the order they appear in the stack (from the top of the stack to the bottom).

If a student at the front of the queue cannot eat the sandwich at the top of the stack, they must move to the end of the queue. This keeps happening until the student at the front of the queue is able to eat the sandwich at the top of the stack.

You need to find the number of students that are unable to eat lunch.

Clarifying Questions

Before diving into coding, let’s ask some clarifying questions:

  1. Will the students array contain only values of 0 (circular sandwich) and 1 (square sandwich)?
    • Yes.
  2. Can we assume that the length of both students and sandwiches arrays is the same?
    • Yes.
  3. Are there any constraints on the length of these arrays?
    • Yes, the length of the arrays will be between 1 and 100.

Strategy

We can approach this problem with the following steps:

  1. Use two counters to keep track of the number of students preferring each type of sandwich (students_count).
  2. Iterate through the sandwiches array and for each sandwich, check the corresponding counter in students_count.
  3. If the current sandwich has a corresponding student who prefers it (i.e., the counter for that sandwich type is greater than zero), decrement the counter and move to the next sandwich.
  4. If there is no corresponding student, break out of the loop early, as no further sandwiches can be taken by the remaining students.
  5. Return the total number of remaining students who were unable to eat.

Code

#include <vector>
using namespace std;

int countStudents(vector<int>& students, vector<int>& sandwiches) {
    int students_count[2] = {0, 0}; // [0]: circular, [1]: square
    
    // Count the number of students preferring each type of sandwich
    for (int student : students) {
        students_count[student]++;
    }
    
    // Try to give out each sandwich in the order they are stacked
    for (int sandwich : sandwiches) {
        if (students_count[sandwich] > 0) {
            students_count[sandwich]--;
        } else {
            break; // No more students wanting this type of sandwich
        }
    }
    
    // Sum the remaining students that could not get their sandwich
    return students_count[0] + students_count[1];
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the students (or sandwiches, as they are of equal length) array. This is because we perform a constant time operation (increment/decrement) for each element in these arrays.

The space complexity is O(1) since we only use a constant amount of additional space for the students_count array.

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