▲

3

▼

🦀 Отслеживание времени первой полной закраски строки/столбца

leetcoder, 20-01-2025 , 29

В следующей задаче - 2661. First Completely Painted Row or Column можно не симулировать в лоб, и за счёт этого сэкономить память при решении (хоть и не получится асимптотически лучше).

📋 Описание задачи

• Нам дан массив arr и матрица mat, содержащие числа от 1 до m * n.
• Массив arr задаёт порядок закраски ячеек матрицы mat (закрашивается ячейка, содержащая указанное число).
• В следующем примере: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]

Необходимо найти первый такой индекс i в массиве arr, при котором:

• Либо вся строка, либо весь столбец матрицы окажется закрашенным.

💡 Идея

Задачу можно переформулировать:

• Каждая строка и каждый столбец закрашиваются, если все элементы строки/столбца обработаны в порядке массива arr.
• Получается, что для решения задачи нужно:
  • Найти максимальный индекс появления значений из arr для каждой строки/столбца.
  • Определить минимальное значение среди этих максимумов.

🛠 Детали подхода

1. Подготовка индексов:
   • Создаём массив pos_index, где для каждого числа x сохраняем его индекс в arr.
     Это обеспечивает доступ к порядковому индексу числа за O(1).
2. Обработка строк:
   Для каждой строки с помощью итераторов:
   • Преобразуем значения строки в их индексы из pos_index.
   • Находим максимальный индекс.
3. Обработка столбцов:
   Для каждого столбца:
   • Перебираем значения столбца и преобразуем их в индексы из pos_index.
   • Находим максимальный индекс.
4. Итог:
   • Минимальный из максимумов по всем строкам и столбцам — это ответ.

⏱ Асимптотика

• Временная сложность: O(m * n)
  • Построение pos_index: O(m * n).
  • Обработка строк: O(m * n).
  • Обработка столбцов: O(m * n).
• Пространственная сложность: O(m * n)
  • Дополнительное пространство на pos_index: O(m * n).
  • Итераторы используют O(1) дополнительной памяти.

✍️ Исходный код

impl Solution {
    pub fn first_complete_index(arr: Vec<i32>, mat: Vec<Vec<i32>>) -> i32 {
        let m = mat.len();
        let n = mat[0].len();
        let mut pos_index = vec![0; (m * n + 1) as usize];

        // Map values in arr to their indices
        for (i, &val) in arr.iter().enumerate() {
            pos_index[val as usize] = i as i32;
        }

        let mut best = i32::MAX;

        // Check rows
        for row in &mat {
            if let Some(max_index) = row.iter().map(|&val| pos_index[val as usize]).max() {
                best = best.min(max_index);
            }
        }

        // Check columns
        for col in 0..n {
            if let Some(max_index) = (0..m).map(|row| pos_index[mat[row][col] as usize]).max() {
                best = best.min(max_index);
            }
        }

        best
    }
}