▲ 3 ▼ leetcoder 19-12-2024 к записи «Shortest write-up ever!»

Честный разбор с решением, которое не стыдно показать на собеседовании, я всё же сделаю :)

Идея 💡

Задача состоит в том, чтобы разделить массив на максимальное количество блоков, так чтобы сортировка каждого блока и их объединение давали отсортированный массив. Ключевая идея заключается в том, что элементы из одного цикла перестановки

arr₁ → arr₂ → arr₃ → ... → arr_n → arr₁

обязательно должны находиться в одном блоке, так как они взаимозависимы.

Описание подхода 🛠️

Создаём массив chunk_assignment, чтобы отслеживать принадлежность каждого индекса к определённому блоку.
Используем функцию assign_chunk для рекурсивного назначения всех индексов, связанных с текущим индексом, в один блок. Она:
- Обновляет максимальный индекс текущего блока.
- Помечает все посещённые индексы текущим номером блока.
Внешний цикл:
- Перебирает индексы массива.
- Увеличивает счётчик блоков при обнаружении нового блока.
- Завершает обработку текущего блока, когда все его элементы покрыты.
Возвращаем общее количество блоков

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

Время: O(n), так как каждый элемент обрабатывается один раз.
Память: O(n), для хранения массива chunk_assignment.

Исходный код решения 📜

impl Solution {
    pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut chunk_assignment = vec![0; n]; // Tracks which chunk each index belongs to
        let mut chunk_count = 0; // Counter for the number of chunks

        // Helper function to assign indices to a chunk
        let mut assign_chunk = |start_idx: usize, chunk: i32, max_idx: &mut usize| {
            let mut current_idx = start_idx;
            while chunk_assignment[current_idx] == 0 {
                *max_idx = (*max_idx).max(current_idx);
                chunk_assignment[current_idx] = chunk;
                current_idx = arr[current_idx] as usize;
            }
        };

        let mut start_idx = 0;
        while start_idx < n {
            chunk_count += 1; // Start a new chunk
            let mut max_idx = start_idx;

            // Process the current chunk until all related indices are covered
            loop {
                assign_chunk(start_idx, chunk_count, &mut max_idx);
                if start_idx == max_idx {
                    break; // The current chunk is complete
                }
                start_idx += 1; // Move to the next index
            }
            start_idx += 1; // Move to the next unprocessed index
        }

        chunk_count // Return the total number of chunks
    }
}