С двух сторон

В этом уроке ты

Научишься решать задачи на одну из популярных тем в алгоритмах — “два указателя”.
Решишь типовую задачу, которую часто дают на собеседованиях в BigTech.

Пример задачи с собеседования

Представь, что ты находишься на созвоне с компанией мечты, и интервьюер озвучивает задачу, которую нужно решить за 20 минут.

Условие

Дан массив nums, отсортированный по возрастанию. Нужно вернуть отсортированный массив, полученный путём взятия модуля от каждого элемента nums.

Проще говоря, все отрицательные элементы нужно заменить на их положительные значения, и итоговый массив вернуть в отсортированном порядке.

Пример

Ввод: nums = [-3,-2,0,1,3,5]
Вывод: nums = [0,1,2,3,3,5]

В чем сложность задачи?

Наивное решение — сначала взять модуль каждого элемента, а затем вызвать встроенную сортировку, которая обычно работает за O(n*log(n)).

using System;
using System.Collections.Generic;

public class Solution
{
    // Время: O(n*log(n)), где n - размер массива
    // Память: O(n), где n - размер массива
    public static List<int> SortedNums(int[] nums)
    {
        // Преобразуем массив: берем абсолютные значения
        List<int> result = new List<int>();
        foreach (int num in nums)
        {
            result.Add(Math.Abs(num));
        }
        // Сортируем массив
        result.Sort();
        return result;
    }
}

#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// Время: O(n*log(n)), где n - размер массива
// Память: O(n), где n - размер массива
vector<int> sorted_nums(const vector<int>& nums) {
    // Преобразуем массив: берем абсолютные значения
    vector<int> result;
    for (int num : nums) {
        result.push_back(abs(num));
    }
    // Сортируем массив
    sort(result.begin(), result.end());
    return result;
}

package main

import (
    "math"
    "sort"
)

// Время: O(n*log(n)), где n - размер массива
// Память: O(n), где n - размер массива
func sortedNums(nums []int) []int {
    result := make([]int, len(nums))
    // Преобразуем массив: берем абсолютные значения
    for i, num := range nums {
        result[i] = int(math.Abs(float64(num)))
    }
    // Сортируем массив
    sort.Ints(result)
    return result
}

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    // Время: O(n*log(n)), где n - размер массива
    // Память: O(n), где n - размер массива
    public static List<Integer> sortedNums(List<Integer> nums) {
        return nums.stream()
                   // Преобразуем массив: берем абсолютные значения
                   .map(Math::abs)
                   // Сортируем массив
                   .sorted()
                   .collect(Collectors.toList());
    }
}

from typing import *

# Время: O(n*log(n)), где n - размер массива
# Память: O(n), где n - размер массива
def sorted_nums(nums: List[int]) -> List[int]:
    return list(sorted(map(abs, nums)))

// Время: O(n*log(n)), где n - размер массива
// Память: O(n), где n - размер массива
function sortedNums(nums) {
    // Преобразуем массив: берем абсолютные значения
    return nums.map(Math.abs)
                // Сортируем массив
                .sort((a, b) => a - b);
}

Однако, такое решение не устроит интервьюера, потому что оно будет долго работать при большом массиве и тебя попросят найти более эффективный способ.

Как решить эффективно?

Заметим, что в отсортированном массиве nums самый большой элемент по модулю может находиться либо в начале массива, либо в конце. Например, в массиве [-8,1,2,3,4] наибольшее абсолютное значение — это либо |-8|, либо |4|.

Если у нас [-8,X,X,X,4], в конце итогового массива окажется 8.
Если у нас [-3,X,X,5], то, сравнивая |-3| и |5|, видим, что |5| больше, значит в конце окажется 5.

Таким образом, мы сравниваем абсолютные значения элементов, на которые указывают два указателя: левый (p1) на начало массива и правый (p2) на конец массива. Модуль какого элемента больше — тот и добавляем в конец результирующего массива. После этого сдвигаем соответствующий указатель (если взяли левый, сдвигаем p1, если правый — p2).

Такой метод движения двух указателей называется “с двух сторон”. Самая сложная задача – это придумать условие, когда двигается левый указатель, а когда правый. В данной задаче мы двигаем указатель, который указывает на больший элемент по модулю.

using System;
using System.Collections.Generic;

public class Solution
{
    public static List<int> SortedNums(int[] nums)
    {
        // храним массив чисел по модулю в убывающем порядке
        List<int> result = new List<int>();
        int p1 = 0; // указывает на начало массива
        int p2 = nums.Length - 1; // указывает на конец массива
        
        while (p1 <= p2)
        {
            // больший элемент добавляем в конец ответа и двигаем указатель
            if (Math.Abs(nums[p1]) > Math.Abs(nums[p2]))
            {
                result.Add(Math.Abs(nums[p1]));
                p1++;
            }
            else
            {
                result.Add(Math.Abs(nums[p2]));
                p2--;
            }
        }
        
        // разворачиваем список, чтобы получить возрастающий порядок
        result.Reverse();
        return result;
    }
}

#include <vector>
#include <algorithm>

using namespace std;

vector<int> sortedNums(vector<int>& nums) {
    // храним массив чисел по модулю в убывающем порядке
    vector<int> result;
    int p1 = 0; // указывает на начало массива
    int p2 = nums.size() - 1; // указывает на конец массива
    while (p1 <= p2) {
        // больший элемент добавляем в конец ответа и двигаем указатель
        if (abs(nums[p1]) > abs(nums[p2])) {
            result.push_back(abs(nums[p1]));
            p1++;
        } else {
            result.push_back(abs(nums[p2]));
            p2--;
        }
    }
    // разворачиваем список, чтобы получить возрастающий порядок
    reverse(result.begin(), result.end());
    return result;
}

package main

func abs(a int) int {
    if a > 0 {
        return a
    }
    return -a
}

func reverseSlice(nums []int) []int {
    p1, p2 := 0, len(nums) - 1
    for p1 < p2 {
        nums[p1], nums[p2] = nums[p2], nums[p1]
        p1++
        p2--
    }
    return nums
}

func sortedNums(nums []int) []int {
    // храним массив чисел по модулю в убывающем порядке
    result := make([]int, 0, len(nums))
    p1 := 0 // указывает на начало массива
    p2 := len(nums) - 1 // указывает на конец массива
    for p1 <= p2 { 
        // больший элемент добавляем в конец ответа и двигаем указатель
        if abs(nums[p1]) > abs(nums[p2]) {
            result = append(result, abs(nums[p1]))
            p1++
        } else {
            result = append(result, abs(nums[p2]))
            p2--
        }
    }
    // разворачиваем список, чтобы получить возрастающий порядок
    result = reverseSlice(result)
    return result
}

import java.util.*;

public class Solution {
    public List<Integer> sortedNums(List<Integer> nums) {
        // храним массив чисел по модулю в убывающем порядке
        List<Integer> result = new ArrayList<>();
        int p1 = 0; // указывает на начало массива
        int p2 = nums.size() - 1; // указывает на конец массива
        while (p1 <= p2) {
            // больший элемент добавляем в конец ответа и двигаем указатель
            if (Math.abs(nums.get(p1)) > Math.abs(nums.get(p2))) {
                result.add(Math.abs(nums.get(p1)));
                p1++;
            } else {
                result.add(Math.abs(nums.get(p2)));
                p2--;
            }
        }
        // разворачиваем список, чтобы получить возрастающий порядок
        Collections.reverse(result);
        return result;
    }
}

from typing import *

def sorted_nums(nums: List[int]) -> List[int]:
    # храним массив чисел по модулю в убывающем порядке
    result = []
    p1 = 0 # указывает на начало массива
    p2 = len(nums) - 1 # указывает на конец массива
    while p1 <= p2:
        # больший элемент добавляем в конец ответа и двигаем указатель
        if abs(nums[p1]) > abs(nums[p2]):
            result.append(abs(nums[p1]))
            p1 += 1
        else:
            result.append(abs(nums[p2]))
            p2 -= 1
    # разворачиваем список, чтобы получить возрастающий порядок
    return list(reversed(result))

export function sortedNums(nums) {
    // храним массив чисел по модулю в убывающем порядке
    const result = [];
    let p1 = 0; // указывает на начало массива
    let p2 = nums.length - 1; // указывает на конец массива

    while (p1 <= p2) {
        // больший элемент добавляем в конец ответа и двигаем указатель
        if (Math.abs(nums[p1]) > Math.abs(nums[p2])) {
            result.push(Math.abs(nums[p1]));
            p1 += 1;
        } else {
            result.push(Math.abs(nums[p2]));
            p2 -= 1;
        }
    }

    // разворачиваем список, чтобы получить возрастающий порядок
    return result.reverse();
}

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

Оценка по времени и памяти

Время: В каждом шаге цикла мы сдвигаем один из указателей, а всего таких шагов будет не больше n, где n — длина массива. Значит, время работы алгоритма — O(n).
Память: Мы используем список result для хранения всех элементов, его размер также будет n. Следовательно, дополнительная память — O(n).

Итог:

Время: O(n), где n - размер nums
Память: O(n)

Как часто “2 указателя” встречается на собеседованиях

Два указателя входит в ТОП-3 самых популярных тем на собеседовании. И осознание данной темы очень круто увеличивает твои шансы успешно пройти собеседование.

В последнее время тренд на 2 указателя очень плотно засел в головах интервьюерах как в крупных технологических компаниях так и в более мелких, так что встретить задачку на два указателя можно даже в мало известной компании.

Что такое два указателя

Указатель — это, по сути, индекс, который обычно указывает на элемент массива или строки. “Два указателя” — это метод, при котором мы используем два индекса и двигаем их по определённому алгоритму. В рассмотренном примере указатели начинают с краёв массива и постепенно двигаются навстречу друг другу.

Паттерн “с двух сторон” — это разновидность метода двух указателей, где они идут от краёв к центру.

Что дальше

Скорее переходи к решению задач, чтобы отточить полученные знания на практике!