Разбор задачи про замену 0 и максимальную последовательность 1
Эту задачу можно эффективно решить за линейное время и константную память. Мне известно как минимум 3 таких решения. Но приведу, на мой взгляд, наиболее элегантное и понятное из них.
Идея решения состоит в том, чтобы обходить исходный список и сохранять индекс предыдущего 0, который мы встретили. Так мы можем легко узнать общее количество 1 между текущим и предыдущим 0 для каждого последующего 0.
Временная сложность приведенного на скриншоте выше решения составляет O(n) и не требует дополнительной памяти.
Готовишься к собеседованиям?
В сборнике 190+ тестовых заданий для аналитиков: SQL, продуктовые кейсы, статистика, A/B и задачи на логику. Можно тренироваться по темам и разбирать реальные форматы собеседований.