---
round: 3
ticket_no: 7
source_no: 3
slug: squares-of-a-sorted-array
topic: Two Pointers
difficulty: Easy
leetcode_id: 977
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 07 — Squares of a Sorted Array

## Условие (как предъявлено)

Дан отсортированный по неубыванию массив целых чисел `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]
```

Constraints: `1 <= nums.length <= 10^4`; `-10^4 <= nums[i] <= 10^4`. Массив отсортирован по неубыванию.

## Ответ

> Здесь идея в том, что мы ставим два указателя в начало и в конец и идём с разных сторон, возводим в квадрат и смотрим, какой квадрат из них больше. Вот. Или не такой, какой А, стоп. Так как нам надо минимальный, то есть это означает, что сначала нужно найти бинарным поиском сначала элемент минимальный. Хорошо, бинарным поиском давайте здесь не будем усложнять. Просто при первом проходе мы находим минимальный элемент. То есть, когда мы идём и видим, что прибавляется элемент ближе всего к нулю. Вот так. То есть мы идём, идём, идём, идём и вдруг бац и видим, что возрастает число. Да, теперь оно там Ну, да, по модулю, по модулю мы идём. Дальше мы начинаем двигать указатели в разные стороны: влево и вправо, и смотрим, какой у нас элемент даёт меньший квадрат. Его добавляем в результирующий массив и сдвигаем указатель. И снова сравниваем два указателя, на что они смотрят. И так далее. Идм, пока не упираемся в конец. И дальше хвост добираем.

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

**Критерии:** идея ⚠️ · структура данных ⚠️ · сложность ⚠️ · граничные случаи ⚠️

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

**Разбор задачи:** [`../../algo-solutions/01-must-have/01-two-pointers/03-squares-of-a-sorted-array.md`](../../algo-solutions/01-must-have/01-two-pointers/03-squares-of-a-sorted-array.md)