Задача "Number of Students Unable to Eat Lunch"

Уровень: easy

Начала прорешивать задачи на очереди. Делюсь решением одной из них.

Итак, задача:
В столовой стоят студенты в очереди за сэндвичами. Каждый студент предпочитает либо круглый, либо квадратный сэндвич. Сэндвичи лежат в стопке. Если предпочтения студентов совпадает с верхним сэндвичем, то он забирает сэндвич и уходит, иначе встает в конец очереди. Количество сэндвичей и студентов одинаковое. Нужно вернуть количество студентов, которые останутся без сэндвича (т.е. когда ни один студент в очереди не захочет взять верхний сэндвич).

На вход мы получаем два массива: студенты и сэндвичи. В массивах хранятся значения 0 и 1. 0 - круглый сэндвич, 1 - квадратный.

Ссылка на задачу, как всегда

Ограничения:
- Кол-во студентов и сэндвичей от 1 до 100
- Кол-во студентов = кол-ву сэндвичей
- sandwiches[i] либо 0, либо 1
- studentes[i] либо 0, либо 1

Пройдемся по алгоритму решения:
1. Заводим две очереди для студентов и сэндвичей и заполняем их.
2. Заводим переменную под хранение неудачных попыток (когда предпочтения студента не совпали с верхним сэндвичем)
3. Проходим по очереди, проверяя, соответствует ли предпочтение первого студента верхнему сэндвичу.
- Если да, удаляем обоих.
- Если нет, перемещаем студента в конец очереди.
4. Если количество неудачных попыток равняется размеру очереди, значит, оставшиеся студенты не могут взять сэндвич, и мы заканчиваем.
5. Если очередь из студентов закончилась (пустая), значит они все взяли сэндвичи, и мы тоже заканчиваем.

public int countStudents(int[] students, int[] sandwiches) {
    Queue<Integer> studentQ = new LinkedList();
    Queue<Integer> sandwichQ = new LinkedList();

    int failedAttempts = 0;

    for (int student: students) {
        studentQ.offer(student);
    }

    for (int sandwich: sandwiches) {
        sandwichQ.offer(sandwich);
    }

    while (!studentQ.isEmpty() && failedAttempts < studentQ.size()) {
        if (studentQ.peek() == sandwichQ.peek()) {
            studentQ.poll();
            sandwichQ.poll();
            failedAttempts = 0;
        } else {
            studentQ.offer(studentQ.poll());
            failedAttempts++;
        }
    }
    return studentQ.size();
}

Временная сложность - O(n), т.к. заполнение очередей сэндвичами и студентами займет O(n), перемещение каждого студента в конец очереди выполняется за O(1), а кол-во таких перемещений может составить n раз. Цикл прекращается, когда количество неудачных попыток достигнет количества студентов n. Это гарантирует, что цикл выполняется не более n раз.
Пространственная сложность - O(n), т.к. потребуется память по две очереди, размер которых будет зависеть от размера входных массивов.

Но есть способ решения без очередей:)
И он даст пространственную сложность O(1), так как в нем понадобится только две примитивные интовые переменные для кол-ва студентов, предпочитающих круглые и квадратные сэндвичи.

public int countStudents(int[] students, int[] sandwiches) {
    int countZero = 0; 
    int countOne = 0; 
        
    for (int student : students) {
        if (student == 0) {
            countZero++;
        } else {
            countOne++;
        }
    }

    for (int sandwich : sandwiches) {
        if (sandwich == 0) {
            if (countZero > 0) {
                countZero--; // Студент взял круглый сэндвич
            } else 
                break; 
        } else {
            if (countOne > 0) {
                countOne--; // Студент взял квадратный сэндвич
            } else 
                break; 
        }
    }
    return countZero + countOne;
}

Пояснения:
1. Вычисляем кол-во студентов предпочитающих круглые и квадратные сэндвичи
2. Идем по стопке сэндвичей, если круглый - уменьшаем кол-во студентов, предпочитающих круглый (так как он возьмет и уйдет в какой-то момент), если квадратный - квадратных.
3. Возвращаем суммарное кол-во оставшихся студентов