---
title: Squares of a Sorted Array
difficulty: Easy
category: Two Pointers
leetcode_id: 977
revision_count: 1
last_revision: 2026-09-12
---

# Squares of a Sorted Array

> **LeetCode:** [#977](https://leetcode.com/problems/squares-of-a-sorted-array/)
> **Сложность:** Easy
> **Категория:** Two Pointers

## Условие

Дан отсортированный по неубыванию массив целых чисел `nums`. Вернуть массив квадратов каждого числа, также отсортированный по неубыванию.

```
Input:  nums = [-4, -1, 0, 3, 10]  →  Output: [0, 1, 9, 16, 100]
Input:  nums = [-7, -3, 2, 3, 11]  →  Output: [4, 9, 9, 49, 121]
```

## Ключевая идея

Максимальный квадрат всегда на одном из концов (отрицательные числа дают большие квадраты). Два указателя снаружи внутрь: сравниваем квадраты на `left` и `right`, больший вставляем в конец результата.

## Оценка сложности

- **Время:** O(n) — один проход двумя указателями
- **Память:** O(n) — массив результата (без учёта вывода), указатели O(1)

## Решение (Ruby)

```ruby
# @param {Integer[]} nums
# @return {Integer[]}
def sorted_squares(nums)
  n = nums.length
  result = Array.new(n)
  left = 0
  right = n - 1

  (n - 1).downto(0) do |i|
    if nums[left].abs >= nums[right].abs
      result[i] = nums[left] ** 2
      left += 1
    else
      result[i] = nums[right] ** 2
      right -= 1
    end
  end

  result
end
```

## Разбор на примере

```
Input: nums = [-4, -1, 0, 3, 10]
n = 5, result = [nil, nil, nil, nil, nil]

i=4: left=0(-4, abs=4), right=4(10, abs=10) → 10>4, result[4]=100, right=3
i=3: left=0(-4, abs=4), right=3(3, abs=3)  → 4≥3,  result[3]=16,  left=1
i=2: left=1(-1, abs=1), right=3(3, abs=3)  → 3≥1,  result[2]=9,   right=2
i=1: left=1(-1, abs=1), right=2(0, abs=0)  → 1≥0,  result[1]=1,   left=2
i=0: left=2(0, abs=0),  right=2(0, abs=0)  → 0≥0,  result[0]=0,   left=3

Result: [0, 1, 9, 16, 100]
```

## Edge Cases

- **Все числа неотрицательные**: `nums = [0, 2, 3]` → `[0, 4, 9]` — left всегда меньше right, правый указатель движется.
- **Все числа отрицательные**: `nums = [-5, -3, -1]` → `[1, 9, 25]` — left движется, сравниваем абсолютные значения.
- **Пустой массив**: `nums = []` → `[]` — `n = 0`, downto не выполняется, result пустой.
- **Один элемент**: `nums = [0]` → `[0]`; `nums = [-2]` → `[4]` — один проход цикла.
- **Отрицательные и одинаковые по модулю**: `nums = [-3, 3]` → `[9, 9]` — при abs-равенстве направление неважно.

## Типичные ошибки

1. ❌ **Сортировать после возведения в квадрат** (O(n log n)) — two pointers даёт O(n), надо сразу вставлять в правильном порядке.
2. ❌ **Идти с начала, а не с конца результата** — если вставлять с начала, теряется информация о том, какой квадрат больше.
3. ❌ **Сравнивать квадраты вместо abs** — `nums[left] ** 2` vs `nums[right] ** 2` — тоже работает, но abs читаемей и не вызывает переполнения для гигантских int (Ruby с этим справится, но abs — идиоматичней).

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Square + sort | O(n log n) | O(n) | Проще для ума, но медленнее |
| **Two pointers outside-in** | **O(n)** | **O(n)** | **финальное решение** |

Square + sort (map + sort) короче по коду: `nums.map { |x| x**2 }.sort`, но O(n log n). Для собеседования ждут two pointers.

## Заметки после повторения

_— Заполняется после каждой тренировки._