Вот и разбор ААА алгосов! Для подготовки к собесам советую присмотреться к нашему курсу по алгоритмам.

@algoses

Задача с собеседования в Яндекс

Реализовать функцию fuzzy pussy search как в редакторе sublime text 3.

Для незнакомых с редактором - по факту требуется проверить, является ли первая строка подпоследовательностью второй

fuzzysearch('car', 'cartwheel') -> true

наш чат алгоритмистов

Решение:
Один проход по символам строки

def fuzzysearch(needle, haystack):
if not needle:
return True
if not haystack:
return False

i = 0 # индекс в needle
for char in haystack:
if char == needle[i]:
i += 1
if i == len(needle):
return True
return False

Асимптотика O(N)

@algoses

Задача с собеседования в Яндекс

Дана строка из десятичных цифр (длинное число, младшие разряды расположены по младшему индексу). Написать код, который умножит это число на число 1 <= n <= 9.

Ограничения по памяти: О(1) доп памяти, т.е. надо использовать исходную строку (считаем, что возможное увеличение длины на 1 разряд не приведет к реаллокации)

наш чат алгоритмистов

Решение:
Пройдемся по строке с разрядами и столбиком умножим число на n. Поддерживаем остаток и считаем так до конца

def multiply_digit_inplace(num_str, n):
if not (1 <= n <= 9):
raise ValueError("n должен быть от 1 до 9")

num = list(num_str) # строка как список символов (можно считать, что это изменяемый массив)
carry = 0

for i in range(len(num)):
digit = int(num[i])
prod = digit * n + carry
num[i] = str(prod % 10)
carry = prod // 10

if carry:
num.append(str(carry))

return ''.join(num)

Асимптотика O(N)

@algoses

Задача с собеседования в Яндекс

На входе дана непустая строка. Требуется вяснить, можно ли удалить из нее ровно один символ так, чтобы получился палиндром.

Требуется решение за линейное время с константой дополнительной памяти.

наш чат алгоритмистов

Решение:
Несложно заметить следующее
Если строка уже является палиндромом, то ответ всегда положительный (достаточно удалить центральный или один из центральных символов)
В противном случае, если начать проверку строки на палиндромность с левого и правого концов - можно найти первое несовпадение abcX....Ycba. Можно заметить, что в случае положительного ответа на задачу один из символов X или Y в данном несовпадении должен быть удален и что после этого палиндромом должна быть строка .....Y или X.....

Таким образом, решение задачи сводится к поиску такого несовпадения и проверки двух случаев

def can_be_palindrome_by_removing_one_char(s):
def is_palindrome_range(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True

left, right = 0, len(s) - 1
while left < right and s[left] == s[right]:
left += 1
right -= 1

if left >= right:
return True # строка уже палиндром или можно удалить любой символ

# Проверяем два варианта: пропустить символ слева или справа
return (is_palindrome_range(left + 1, right) or
is_palindrome_range(left, right - 1))

@algoses

Задача с собеседования в Яндекс

Дан вектор, надо удалить из него нули, сохранив порядок остальных элементов. Интересует как с использованием стандартных средств, так и без них.

наш чат алгоритмистов

Решение:
Линейно пройдемся по элементам массива, поддерживая указатель на записываемый элемент. Затем удалим лишние индексы

def remove_zeros(arr):
write = 0
for read in range(len(arr)):
if arr[read] != 0:
arr[write] = arr[read]
write += 1
# обрезаем хвост (если надо)
del arr[write:]

Асимптотика O(N)

@algoses

Задача с собеседования в Т-банк

Условие:
Определим понятие хорошей последовательности - абсолютная разница между любыми двумя элементами этой последовательности должна быть больше либо равна максимальному элементу. То есть (i, j) | a_i - a_j | > max(a[l:r+1]). Вам даётся массив длины 10^5 и требуется определить наибольшую длину хорошей подпослдеовательности.

наш чат алгоритмистов

Решение:
Очевидно, что если в подпоследовательности будет больше двух положительных элементов, то x - y > x (x = max(x, y)) верно лишь в том случае, когда y < 0. Соответственно длина последовательности будет точно хотя бы равняться количеству отрицательных элементов. При построении последовательности возьмем один положительный элемент (потому что иначе с двумя положительными не будет выполняться условие |a_i - a_j| > max(a_i, a_j) и возьмем жадно аименьший положительный. Тогда можно будет проверить, получится ли этот положительный элемент добавить в последовательность отрицательных так чтобы не нарушалось то условие (для этого достаточно перебрать наименьшую абсолютную разницу, то есть просто перебрать пары соседних в отсортированном порядке).


int n;
cin >> n;
vector<int> a(n);
int ans = 0;
for (int i = 0; i < n; i++ ){
cin >> a[i];
ans += (a[i] <= 0);
}
sort(a.begin(), a.end());
int mn = inf;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
mn = min(a[i], mn);
}
}
bool flag = (mn != inf);
for (int i = 1; i < n; i++) {
if (a[i] <= 0) {
flag &= (a[i] - a[i - 1] >= mn)
}
}
cout << ans + flag;

@algoses

Задача с собеседования в лабораторию Т-банка

Задача:
Нам даны две последовательности A и B из 0 и 1 (длиной до 10^6). У вас есть две операции:
1. Выбрать последовательность и поменять местами элементы на позициях (i, j) - стоимость такой операции будет |i-j|
2. Выбрать элемент последовательности и поменять значение бита на противоположное, стоимость в таком случае будет 1
Требуется за минимальную стоимость сделать последовательности равными

наш чат алгоритмистов

Решение:
Заметим, что операцию 1 нет смысла использовать когда |i - j| > 1, а выигрышь стоимости в 1 достигается только при |i - j| = 1. Тогда можно решать задачу с помощью dp, dp_i - минимальный ответ для того чтобы сделать префиксы последовательностей длинной i равным.
Тогда пересчёта будет два:
Первый - это прийти в состояние i, воспользовавшись операцией 2 и тогда стоимость для префикса длины будет считаться как dp{i-1} + (a[i] != b[i])
Второй - это воспользоваться операцией 2 и поменять символы на позициях (i - 1, i), но в таком случае нужно проверить, что строки станут равными после этой операции (если быть точнее, то префиксы строк).

int n;
cin >> n;
string a, b;
cin >> a;
cin >> b;
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + (a[i - 1] != b[i - 1]);
if (i >= 2 && a[i - 2] == b[i - 1] && a[i - 1] == b[i - 2]) {
dp[i] = min(dp[i], dp[i - 2] + 1);
}
}
cout << dp[n] << '\n';

@algoses

Задача с собеса Авито

На вход дана строка, требуется вернуть строку отсортированную по частоте встречаемости символов.


Ограничения:
- длина строки от 1 до 5 * 10 ** 5
- строка состоит из английских букв в верхнем и нижнем регистре

наш чат алгоритмистов

Решение:
С помощью словаря подсчитаем частоты символов— O(N).Создадим массив корзин (bucket), где индекс — это частота символа.
(Максимальная возможная частота символа = N, если вся строка из одного символа.)
Разложим символы по корзинам в соответствии с их частотой — O(M), где M — число уникальных символов (M ≤ N). В конце пройдемся по корзине от самой высокой частоты к низкой и соберем результат — O(N)


def frequencySort(s):
    freq = {}
    for char in s:
         if chat not in freq:
              freq[char] = 0
        freq[char] += 1 
   

    buckets = [[] for _ in range(len(s) + 1)] 
    for char, count in freq.items():
        buckets[count].append(char) 
   
   
    result = []
    for count in range(len(buckets) - 1, -1, -1):
        for char in buckets[count]:
            result.append(char * count)
   
    return ''.join(result)

@algoses

Задача с собеседования в Яндекс

Дан массив целых чисел nums и целое число k. Необходимо найти количество смежных подмассивов, произведение элементов которых строго меньше k.

nums = [10, 5, 2, 6], k = 100 
Ответ: 8 
Объяснение: 8 подмассивов удовлетворяют условию: 
[10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6].

Ограничения:
длина от 1 до  3 *10^ 4
значения от 1 до 1000
k от 1 до 10 ^ 6

наш чат алгоритмистов

Решение:
Используем метод скользящего окна с двумя указателями (left и right). product = 1 (текущее произведение), count = 0 (счётчик подмассивов), left = 0 (левый указатель). Для каждого right от 0 до n-1. Умножаем product на nums[right]. Если product >= k, сдвигаем left, деля product на nums[left], пока product снова не станет < k. Добавляем к count количество новых подмассивов: right - left + 1.

def num_subarrays_product_less_than_k(nums, k):
    if k <= 1:
        return 0
    product = 1
    count = left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k:
            product /= nums[left]
            left += 1
        count += right - left + 1
    return count

@algoses

Задача с собеседования Яндекс

Задача 
Дана последовательность a и последовательность a'. Вам требуется найти такие l, r, что отсортировав подмассив a[l:r+1], можно получить массив a'. Если ответов несколько, выберите отрезок наибольшей длины. По условию такая операция всегда существует.

Чат алгоритмистов

Решение 
Найдем первое отличающееся вхождение, позицию i: a[i]!= a'[i](то есть самое левое) и найдем последнее (самое правое). Далее расширим эти границы: до тех пор, пока левее от левой границы в приведенном массиве a стоит меньше или равный a'[l-1]<= a'[l], будем двигать его влево. Аналогично и с правым указателем, расширим его вправо.

Код
l,r=-1,-1
for i in range(n):
  if a[i]!=aa[i]:
   r=i
   if l==-1:
    l=i
while l>0 and aa[l-1]<=aa[l]:
  l-=1
while r<n-1 and aa[r+1]>=aa[r]:
  r+=1
print(l+1,r+1)

@algoses

Задача с собеседования в Яндекс

Дано бинарное дерево (не поиска):
struct Node {
Node* parent;
Node* left;
Node* right;
}

Нужно написать функцию, которая для двух данных вершин будет возвращать их наименьшего (ближайшего) общего предка:

Node* lca(Node* a, Node* b);

Ограничения: память O(1)

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение:
Считаем глубину для каждой вершины, потом идем двумя указателями вверх от вершин, пока они не встретятся. O(h) по времени, где h - высота дерева.
#include <unordered_map>

struct Node {
Node* parent;
Node* left;
Node* right;
};

std::unordered_map<Node*, int> depth_map;

void compute_depths(Node* node, int depth = 0) {
if (!node) return;
depth_map[node] = depth;
if (node->left) {
node->left->parent = node;
compute_depths(node->left, depth + 1);
}
if (node->right) {
node->right->parent = node;
compute_depths(node->right, depth + 1);
}
}

Node* lca(Node* a, Node* b) {
int da = depth_map[a];
int db = depth_map[b];

while (da > db) {
a = a->parent;
--da;
}
while (db > da) {
b = b->parent;
--db;
}

while (a != b) {
a = a->parent;
b = b->parent;
}

return a;
}

@algoses

Один день из жизни стажера-аналитика в Т-банке

Выпускника прошлых потоков наших продвинутых курсов, на которые идут последние часы 50% скидки, не упусти свой шанс забрать разбор Т-банка и уже осенью получить заветный оффер.

Мой рабочий день начинается с планирования. Первым делом я проверяю календарь и список задач. Сегодня запланирована важная встреча с наставником, так что я принимаю решение поехать в офис — там коммуникация с командой эффективнее. Офис Т-банка расположен в центре Москвы, на Белорусской, что очень удобно: рядом сразу две станции метро и ветки МЦД.

Обычно, когда езжу в офис, я начинаю день с зала. Для сотрудников здесь доступен полноценный клуб с тренажерным залом, там есть всё и кардио, и все популярные тренажеры, и залы для групповых занятий. После тренировки сходил в баню и с отличным настроением пошел, встретился коллег-стажеров с нашего потока - мы обсудили подготовку к предстоящему ИТ-пикнику.

К 11:00 я уже сел за свое рабочее место. Изучил бэклог и расставляю приоритеты на день. Моя главная цель на стажировке - выполнить все задачи для последующего перевода в штат. Сегодня в фокусе - продолжение работы над ML-моделью для классификации клиентов из сегмента малого и среднего бизнеса. Это нужно для автоматизации работы с бизнесами и выявления некорректной регистрации бизнесов. После приоритизации задач, заглянул в кофе поинт позавтракать. Здесь всегда есть кофе, чай, свежие фрукты и выпечка. Это хорошая возможность на несколько минут переключиться и пообщаться с коллегами из других отделов. Затем наконец сел за решение задачи, покопался в подборе параметров модели для разметки бизнесов, получилось улучшить скор и сел дописывать тест в другой задаче, там были проблемы с мощностью теста и бадди посоветовал использовать cuped.

Около 13:00 отправляюсь в столовую. Для сотрудников организовано полноценное бесплатное питание (шведский стол). Выбрал котлеты, гречку, крем-суп и салат с моцареллой. Как мне кажется система бесплатной столовой получше решение, чем 1000 рублей в день на рестораны (еды значительно больше, ну и столовая в т-банке вкуснее).

В 13:30 у меня созвон с наставником. Мы проводили еженедельную оценку работы, проделанной на стажировке, он дает мне советы: я докладываю о прогрессе по модели, обсуждаю проблемные места и получаю обратную связь. Наставник отмечает, что я успешно справился с предыдущей задачей по классификации, и ставит новую - с дизайном АБ.

Вторая половина дня уходит на подготовку и запуск A/B-теста для нового сценария взаимодействия с клиентами малого бизнеса. Мне нужно проверить гипотезу, что измененная механика отправки email-уведомлений увеличит конверсию в отклик. В начале сегментировал клиентскую базу и сформировао тестовую и контрольную группы. Особое внимание уделяю исключению пересечений с другими текущими экспериментами в банке. К концу дня мне удается подготовить код для запуска теста, но дашборд сделать не успел.

В 17:30 рабочий день кончился и пошёл перед уходом поиграл с товарищем в настольный теннис.

@postypashki_old

Задача с собеседования в Яндекс

Дан массив prices, где prices[i] — цена акции в день i. Нужно выбрать один день для покупки и позже другой день для продажи так, чтобы прибыль была максимальна. Если прибыли получить нельзя — вернуть 0.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение:

Проходим массив один раз, поддерживая:
min_price — минимальную цену, встреченную слева (лучшая покупка до текущего дня);
best — максимальную прибыль на данный момент.
На каждом шаге обновляем best = max(best, prices[i] - min_price) и затем min_price = min(min_price, prices[i]).
Это даёт O(n) по времени и O(1) по памяти.

Код:

#include <bits/stdc++.h>
using namespace std;

int maxProfit(const vector<int>& prices) {
int min_price = INT_MAX;
int best = 0;
for (int p : prices) {
if (p > min_price) {
best = max(best, p - min_price);
}
min_price = min(min_price, p);
}
return best;
}

@algoses

Задача с собеседования в Яндекс

Дана скобочная грамматика: в круглых скобках записано выражение, следом за ними идут квадратные скобки с неотрицательным целым числом. Разворачивается в виде конкатенации строки в круглых скобках на саму себя N раз, где N - число в квадратных скобках

Чуть более формально, грамматика -
term ::= a-z*
term ::= (term)[\d+]
term ::= term1term2 - разворачивается в конкатенацию двух выражений

На вход подается строка со скобочным выражением. Необходимо развернуть его в строку и вернуть. Предлагается считать, что скобочная последовательность на входе всегда корректна

Примеры:
"ab" -> "ab"
"(ab)[3]" -> "ababab"
"((ab)[2])[2]" -> "abababab"
"(a)[2](b)[2]" -> "aabb"
"()[1]bc" -> "bc"

Наш чат алгоритмистов

Решение:
Аккуратная рекурсия

def parse_expression(s: str) -> str:
def helper(i):
res = ""
while i < len(s):
if s[i] == '(':
# Рекурсивно разбираем внутреннее выражение
inner, i = helper(i + 1)
# После этого должен идти [
assert s[i] == '[', f"Ожидалась [ на позиции {i}, а найдено {s[i]}"
i += 1
num_start = i
while s[i].isdigit():
i += 1
repeat = int(s[num_start:i])
assert s[i] == ']', f"Ожидалась ] на позиции {i}, а найдено {s[i]}"
i += 1
res += inner * repeat
elif s[i] == ')':
return res, i + 1
else:
res += s[i]
i += 1
return res, i

result, _ = helper(0)
return result

Подводные камни:
1) выход за границы строки при разборе, неточное вычленение содержимого подвыражений в скобках
2) остаются куски грамматики в выводе
3) некорректно парсится число в квадратных скобках, если имеет более одного разряда - например, парсится задом наперед или только один разряд

@algoses

Задача с собеседования в Яндекс

Дана следующая структура мероприятий, имеющих временное начало и конец

struct Meeting {
    long long from;
    long long to;
}

vector<Meeting> crossing(const vector<Meeting>& meetings) ...

Необходимо найти пересекающиеся встречи

Наш чат алгоритмистов

Решение:
Сортируем встречи по времени начала, затем проходим слева направо, поддерживая наибольший правый конец max_end среди уже просмотренных интервалов и индекс того интервала, который даёт max_end. Если следующий интервал начинается раньше max_end, то он пересекается с каким-то предыдущим (в частности — с тем, чьё max_end), помечаем оба как пересекающиеся. В конце возвращаем (или выводим) все исходные встречи, помеченные как пересекающиеся.

Код:
vector<Meeting> crossing(const vector<Meeting>& meetings) {
int n = (int)meetings.size();
if (n == 0) return {};

// Соберём (from, to, orig_index) и отсортируем по from
struct Node { long long from, to; int idx; };
vector<Node> v;
v.reserve(n);
for (int i = 0; i < n; ++i) v.push_back({meetings[i].from, meetings[i].to, i});
sort(v.begin(), v.end(), [](const Node& a, const Node& b) {
if (a.from != b.from) return a.from < b.from;
return a.to < b.to;
});

vector<char> overlapped(n, 0); // пометки для исходных индексов

long long max_end = v[0].to;
int idx_max_sorted = 0; // индекс в v, который даёт max_end

// Считаем, что пересечение происходит если start < max_end (строгое пересечение).
// Если нужно считать касание по границе пересечением, менять на <= .
for (int i = 1; i < n; ++i) {
if (v[i].from < max_end) {
// v[i] пересекается с тем, у кого max_end
overlapped[v[i].idx] = 1;
overlapped[v[idx_max_sorted].idx] = 1;
}
if (v[i].to > max_end) {
max_end = v[i].to;
idx_max_sorted = i;
}
}

// Собираем результат в исходном порядке
vector<Meeting> res;
for (int i = 0; i < n; ++i) {
if (overlapped[i]) res.push_back(meetings[i]);
}
return res;
}

Время O(NlogN), память O(N)

@algoses

Задача с собеседования в Яндекс

Написать функцию, которая меняет порядок слов в строке на противоположный, при этом не меняя расположение пробелов
Например: __hello_my___dear_world_ -> __world_dear___my_hello_

Наш чат алгоритмистов

Решение:
Мы сохраняем следующую инфу из строки: слова (подряд идущие непробельные символы) и пробелы (их количество после каждого слова + отдельно ведущие и конечные пробелы).
После этого мы можем взять все слова в обратном порядке, а пробелы вставить ровно так, как они шли в исходной строке.

Код:
string reverseWordsKeepSpaces(const string &s) {
int n = (int)s.size();
int i = 0;

// 1) leading spaces
int leading = 0;
while (i < n && s[i] == ' ') { ++leading; ++i; }

vector<string> words;
vector<int> spacesAfter; // spaces after each word; последний элемент = trailing spaces

// 2) collect words and following spaces counts
while (i < n) {
int j = i;
while (j < n && s[j] != ' ') ++j;
words.emplace_back(s.substr(i, j - i));

int cnt = 0;
int k = j;
while (k < n && s[k] == ' ') { ++cnt; ++k; }
spacesAfter.push_back(cnt);

i = k;
}

// если никаких слов (только пробелы или пустая строка) — вернуть как есть
if (words.empty()) return s;

// trailing spaces — последний элемент spacesAfter
int trailing = spacesAfter.back();
spacesAfter.pop_back(); // теперь spacesAfter.size() == words.size()-1

// 3) формируем результат: leading + reversed words interleaved с spacesAfter (в том же порядке) + trailing
string res;
res.reserve(n);
res.append(leading, ' ');

int m = (int)words.size();
for (int idx = 0; idx < m; ++idx) {
// берем слова с конца: words[m-1], words[m-2], ...
res += words[m - 1 - idx];
if (idx < (int)spacesAfter.size()) {
res.append(spacesAfter[idx], ' ');
}
}
res.append(trailing, ' ');
return res;
}

Асимптотика O(N)

@algoses

Задача с собеседования в Яндекс

Даны два массива, состоящих из элементов типа (id, val), отсортированных по неубыванию id Нужно их объединить в один массив, удовлетворяющий следующим условиям
1) В итоговом массиве каждый id входит ровно один раз и элементы массива отсортированы по неубыванию id
2) val, имеющие одинаковые id, суммируются и их сумма будет в итоговом массиве под тем же id

Требуется решение с линейной скоростью и константной памятью

Наш чат алгоритмистов

Решение:
Пройдемся по обоим массивам параллельно, поддерживая текущий айдишник и сумму для него

def merge_sum_list(a: List[Pair], b: List[Pair]) -> List[Pair]:
i = 0
j = 0
na = len(a)
nb = len(b)

res: List[Pair] = []
cur_id: Optional[int] = None
cur_sum: float = 0.0

while i < na or j < nb:
if i < na and (j >= nb or a[i][0] < b[j][0]):
next_id, next_val = a[i]
i += 1
else:
next_id, next_val = b[j]
j += 1

if cur_id is None:
cur_id = next_id
cur_sum = next_val
elif next_id == cur_id:
cur_sum += next_val
else:
res.append((cur_id, cur_sum))
cur_id = next_id
cur_sum = next_val

if cur_id is not None:
res.append((cur_id, cur_sum))

return res

@algoses

Собеседование по алгоритмам в ШАД 2025

Идут последние 6 часов скидки на нашу новую линейку легендартных курсов. В честь этого события делимся и разбираем задачи в прикрепленном файле с собеса по алгосам 2025 года. Задачи 2023-2024 года ниже, еще больше эксклюзивных задач на наших курсах.

https://news.1rj.ru/str/algoses/6
https://news.1rj.ru/str/algoses/12
https://news.1rj.ru/str/algoses/19
https://news.1rj.ru/str/algoses/39
https://news.1rj.ru/str/algoses/194
https://news.1rj.ru/str/botalkaaa/82748
https://leetcode.com/problems/find-all-anagrams-in-a-string/denoscription/
https://news.1rj.ru/str/algoses/137

Никаких изменений с форматом в этом году почти не было, все также одна задача на пол часа, нужно решение и код, но могли быть доп вопросы и как бонус предлагался чужой код на оценку. А вот с форматом по математике были небольшие изменения, о них мы расскажем как только будет 300 огоньков 🔥 на этом посте.

@postypashki_old

Задача с собеседования в Яндекс

В функцию подается две строки: s и t, где t это непустой алфавит, состоящий из уникальных символов
Надо найти наикратчайшую подстроку в s такую, что она содержит все символы из алфавита t

Наш чат алгоритмистов

Решение должно быть линейно по времени

Решение:
Для удобства заведем хешмапу для быстрой проверки символа в алфавите и поддержания его индекса
Линейно пройдемся правым указателем по строке, поддерживая количество покрытых символов в алфавите, и двигаем левый указатель вправо, пока наша подстрока удовлетворяет условиям

def min_window_with_alphabet(s: str, t: str) -> str:
if not s:
return ""

k = len(t)
mapping = {ch: i for i, ch in enumerate(t)} # char -> index 0..k-1

need = [1] * k
window = [0] * k

required = k
formed = 0

l = 0
best_len = float('inf')
best_l = 0

for r, ch in enumerate(s):
idx = mapping.get(ch)
if idx is not None:
window[idx] += 1
if window[idx] == 1:
formed += 1

while formed == required and l <= r:
cur_len = r - l + 1
if cur_len < best_len:
best_len = cur_len
best_l = l

left_ch = s[l]
idx_l = mapping.get(left_ch)
if idx_l is not None:
window[idx_l] -= 1
if window[idx_l] == 0:
formed -= 1
l += 1

return "" if best_len == float('inf') else s[best_l: best_l + best_len]

@algoses

Задача с собеседования в Amazon

Дан массив целых чисел. Необходимо посчитать сумму минимумов каждого подмассива исходного массива. Ответ вывести по модулю 1e9

Пример:
[3, 1, 2, 4]
Ответ: 17

Наш чат алгоритмистов

Решение:
Для каждого элемента A[i] посчитать, в скольких подмассивах он будет минимальным. Найдём индекс предыдущего элемента строго меньше (prev) и следующий элемент меньше или равный (next) с помощью монотонного стека. Тогда вклад A[i] в сумму равен A[i] * (i - prev[i]) * (next[i] - i). Время O(n), память O(n).

def sumSubarrayMins(A: List[int]) -> int:
n = len(A)
if n == 0:
return 0

# prev: индекс предыдущего элемента, который строго меньше A[i]
prev = [-1] * n
stack = []
for i in range(n):
while stack and A[stack[-1]] >= A[i]:
stack.pop()
prev[i] = stack[-1] if stack else -1
stack.append(i)

# nxt: индекс следующего элемента, который меньше или равен A[i]
nxt = [n] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and A[stack[-1]] > A[i]:
stack.pop()
nxt[i] = stack[-1] if stack else n
stack.append(i)

res = 0
for i in range(n):
left_count = i - prev[i]
right_count = nxt[i] - i
res = (res + A[i] * left_count * right_count) % MOD

return res

@algoses