DDSA Solutions

1700. Number of Students Unable to Eat Lunch

EasyView on LeetCode
ArrayStackQueueSimulation
Time: O(n)
Space: O(1)

Problem Overview

Count students who cannot get their sandwich preference.

Intuition

Count students who cannot get their sandwich preference. After sandwiches in queue are exhausted for students wanting front sandwich, simulation ends.

Algorithm

  1. 1Count preference[0] and preference[1] students.
  2. 2Process sandwiches in order. If top sandwich matches count > 0: count--. Else: if both counts > 0, cycle. Return remaining students.
  3. 3Simplified: remaining = students who want opposite of remaining sandwiches.

Common Pitfalls

  • •When count for current top sandwich is 0 and count for other is >0: all remaining students are unsatisfied.
1700.cs
C#
// Approach: Count student preferences; simulate serving sandwiches top-of-stack; stop when no match possible.
// Time: O(n) Space: O(1)

public class Solution
{
    public int CountStudents(int[] students, int[] sandwiches)
    {
        int[] count = new int[2];

        foreach (int student in students)
            ++count[student];

        for (int i = 0; i < sandwiches.Length; ++i)
        {
            if (count[sandwiches[i]] == 0)
                return sandwiches.Length - i;
            --count[sandwiches[i]];
        }

        return 0;
    }
}
Was this solution helpful?

Related Problems