9. Squares of Sorted Array

«Вместо того чтобы двигаться от начала к концу, порой достаточно взглянуть на концы задачи и идти внутрь».
— Брайан Керниган

LeetCode 977. Squares of a Sorted Array

Сложность: Easy
Тема: Встречные указатели, обратное заполнение (Reverse Filling), сортировка за $O(N)$
Ссылки: Теория: Два указателя, Варианты применения, Merge Sorted Array

1. Введение и физическая интуиция

Дан отсортированный по неубыванию массив чисел: например, [-4, -1, 0, 3, 10].
Если мы просто возведем каждое число в квадрат, то получим: [16, 1, 0, 9, 100].
Сортировка нарушилась: отрицательные числа с большими по модулю значениями дали огромные квадраты в начале среза!

Математически функция $f(x) = x^2$ представляет собой параболу с вершиной в точке $0$. Значения убывают при приближении к нулю слева и возрастают при удалении от нуля вправо.

Это значит, что самые большие квадраты гарантированно находятся на краях массива — либо у крайнего левого отрицательного числа, либо у крайнего правого положительного.

Отсюда рождается элегантнейший алгоритм:
Мы ставим указатели на оба конца массива (left = 0, right = n - 1) и начинаем заполнять результирующий срез с самого конца (pos = n - 1):

• Сравниваем квадраты чисел на концах: $nums[left]^2$ против $nums[right]^2$.
• Тот, чей квадрат больше, забирает почетное место в конце среза.
• Соответствующий указатель сдвигается внутрь массива.

Никаких логарифмических сортировок за $O(N \log N)$! Мы получаем идеальный отсортированный результат за строго один линейный проход $O(N)$.

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    A["nums = [-4, -1, 0, 3, 10]"]:::entry --> B["res = make([]int, n)<br>left=0, right=4, pos=4"]:::process
    B --> C{"pos >= 0?"}:::warning
    C -->|"Да"| D{"nums[left]^2 > nums[right]^2?"}:::warning
    D -->|"Да"| E["res[pos] = nums[left]^2<br>left++"]:::process
    D -->|"Нет"| F["res[pos] = nums[right]^2<br>right--"]:::process
    E --> G["pos--"]:::process
    F --> G
    G --> C
    C -->|"Нет"| H["Возвращаем res"]:::success
  

2. Формулировка задачи и вопросы интервьюеру

Дан целочисленный массив nums, отсортированный по неубыванию. Вернуть массив квадратов каждого числа, также отсортированный по неубыванию. Решение должно работать за $O(N)$ по времени.

Вопросы интервьюеру (Senior-стиль):

1. Каков размер входных данных?
   «$1 \le len(nums) \le 10^4$, значения в диапазоне $[-10^4, 10^4]$. Квадрат максимального числа равен $10^8$, что с огромным запасом помещается в стандартный целочисленный тип.»
2. Можно ли использовать вспомогательный массив?
   «Да, возвращаемое значение []int требует новой памяти $O(N)$. Попытка перезаписать входной срез in-place разрушит еще не обработанные значения.»
3. Может ли массив содержать только положительные или только отрицательные числа?
   «Да, алгоритм двух указателей обязан корректно отрабатывать любые граничные комбинации знаков.»

3. Разбор подходов

Подход 1: Возведение в квадрат + сортировка (Наивный)

func sortedSquaresNaive(nums []int) []int {
    res := make([]int, len(nums))
    for i, v := range nums {
        res[i] = v * v
    }
    slices.Sort(res)
    return res
}

• Сложность: $O(N \log N)$ по времени, $O(N)$ по памяти.
• Вердикт: Решение работает, но полностью игнорирует главное свойство — отсортированность входа. На собеседовании такое решение показывает непонимание задачи.

Подход 2: Встречные указатели с обратным заполнением (Эталонный)

Заполняем результирующий буфер с конца, выбирая максимальный квадрат за один шаг. Сложность строго $O(N)$ по времени и $O(1)$ вспомогательной памяти (за исключением возвращаемого результата).

4. Эталонная реализация на Go

package main

// SortedSquares возвращает срез квадратов элементов, отсортированный по неубыванию.
// Временная сложность: O(N) — каждый элемент просматривается ровно один раз.
// Пространственная сложность: O(N) под результирующий срез (0 лишних аллокаций).
func SortedSquares(nums []int) []int {
    n := len(nums)
    result := make([]int, n)

    left := 0
    right := n - 1

    // Заполняем массив с конца: от самого большого квадрата к наименьшему
    for pos := n - 1; pos >= 0; pos-- {
        leftSquare := nums[left] * nums[left]
        rightSquare := nums[right] * nums[right]

        if leftSquare > rightSquare {
            result[pos] = leftSquare
            left++
        } else {
            result[pos] = rightSquare
            right--
        }
    }

    return result
}

5. Пошаговая трассировка (Walkthrough)

Вход: nums = [-4, -1, 0, 3, 10] ($n = 5$).

Ровно 5 итераций. Массив безупречно отсортирован!

6. Mechanical Sympathy: предвыделение памяти и кэш

1. Единственная аллокация make([]int, n):
   Мы создаем срез точного размера n. В коде нет ни единого вызова append(), а значит:
   • Нет проверок вместимости (cap).
   • Нет повторных реаллокаций и копирований буфера в куче.
   • Исключена фрагментация памяти кучи.
2. Аппаратный Prefetcher при обратной записи:
   Современные процессоры одинаково эффективно предугадывают как прямой последовательный доступ (pos++), так и обратный (pos--). Запись в непрерывный буфер result[pos] наполняет кэш-линию L1d последовательно справа налево, минимизируя задержки шины памяти.

7. Вопросы для собеседования

8. Инварианты и чек-лист самопроверки

• [x] Размер среза: make([]int, n) строго равен длине входа.
• [x] Условие цикла: pos >= 0 выполняется ровно $N$ раз.
• [x] Случай одного элемента: при $n = 1$ цикл срабатывает на pos = 0, корректно записывая квадрат единственного числа.

Переходим к финальной задаче кластера «Два указателя» — избирательному реверсу гласных символов в строке: 10. Reverse Vowels of String.