[Условие] Leetcode #4. Median of Two Sorted Arrays

Ссылка на задачу на Leetcode
Решение (часть 1 и часть 2)

Получаем два отсортированных массива: nums1 с длиной m и nums2 с длиной n. Возвращаем их медиану (серединное значение). Временная сложность должна быть O(log (m + n)).

Кейс #1:
nums1 = [1,3]
nums2 = [2]
Output: 2 
Объяснение: общий массив - [1,2,3], медиана - 2

Кейс #2:
nums1 = [1,2]
nums2 = [3,4]
Output: 2.5
Объяснение: общий массив - [1,2,3,4], медиана - (2+3)/2 = 2.5

#hard #arrays

@leetcode_furrycat

[Решение] Leetcode #4. Median of Two Sorted Arrays. Решение (Часть 1)

Условие задачи

Решение в лоб: слить отсортированные массивы в один. Но оно не соответствует заявленной сложности (будет O(n)), поэтому ищем другие пути.

Левая половина

Нам достаточно получить левую половину результирующего массива (до медианы).

если смерженный массив: [1,2,3,4,5]
то его левая половина: [1,2]

если смерженный массив: [1,2,3,4]
то его левая половина: [1,2]

У нас есть два массива, arr1 и arr2. Пусть arr1.length меньше или равна arr2.length, то есть arr1 короче. Будем называть смерженный массив mergedArr, а его левую половину mergedArrLeft.

Легко узнать, сколько элементов входят в mergedArrLeft. Находим общую длину двух массивов (`total`) и делим ее на 2 (`half`). Таким образом в mergedArrLeft входит half элементов.

если mergedArr: [1,2,3,4,5]
total = 5
half = Math.floor(total / 2) = 2
mergedArrLeft: [1,2]

mergedArr: [1,2,3,4]
total = 4
half = Math.floor(total / 2) = 2
mergedArrLeft: [1,2]

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

Сделаем предположение, что в mergedArrLeft входит половина массива arr1 (более короткого массива). Почему половина? Ну, нужно же с чего-то начинать, а начинаем мы обычно с принципа "разделяй и властвуй".

Внимание: нет гарантии, что это предположение окажется верным. Мы будем его корректировать по мере необходимости.

Итак, берем половину arr1, считаем, сколько это элементов. Вычитаем это число из half, чтобы понять, сколько элементов нужно взять из второго массива, чтобы составить mergedArrayLeft.

arr1 = [1,2,3,4,5]
arr2 = [1,2,3,4,5,6,7,8]

total = 5 + 8 = 13
half = Math.floor(13 / 2) = 6

arr1MedianIndex = Math.floor(5 / 2) = 2
arr1Elements = [1,2,3] // с 0го по 2й элемент включительно

arr2ElementsCount = 3 // 6 - 3
arr2Elements = [1,2,3]

Проверка

Теперь нам нужно убедиться, что мы предположили правильно, и действительно именно эти элементы составляют mergedArrLeft. Это очень просто. Нужно проверить, что последний элемент каждого массива меньше или равен первому элементу, оставшемуся в другом массиве.

То есть мы берем из arr1 элементы [1,2,3]. В нем остаются [4,5]. А из arr2 мы берем элементы [1,2,3].

arr1 = [1,2,3,4,5]
arr1Elements = [1,2,3] // входит в arrMergedLeft
arr1Rest = [4,5]

arr2 = [1,2,3,4,5,6,7,8]
arr2Elements = [1,2,3] // входит в arrMergedLeft
arr2Rest = [4,5,6,7,8]

Последний элемент из arr1Elements не может быть больше первого элемента из arr2Rest и наоборот.

Если все верно, то мы легко можем найти последний элемент mergedArrLeft (самое большое значение из arr1Elements и arr2Elements`) и следующий за ним элемент (самое маленькое значение из `arr1Rest и arr2Rest`). Если `total - четное, нам нужно будет найти их среднее арифметическое, если нечетное, то следующий элемент и является медианой.

На данный момент сложность алгоритма константная - O(1), так как мы выполняем только арифметические операции.

#hard #arrays

@leetcode_furrycat

Leetcode #4. Median of Two Sorted Arrays. Решение (Часть 2)

Корректировка

Если проверка не прошла - мы неправильно определили состав mergedArrLeft. Значит, нужно сдвинуть arr1Elements. Куда именно, зависит от того, какая конкретно проверка не прошла. Если arr1Elements оказался больше, чем надо, то его нужно уменьшить. И соответственно, наоборот.

Посмотрим на примере:

arr1 = [1,2,3,4]
arr2 = [1,2,3,4,5,6,7,8]

total = 4 + 8 = 12
half = Math.floor(12 / 2) = 6

arr1MedianIndex = Math.floor(4 / 2) = 2
arr1Elements = [1,2] 
arr1Rest = [3,4]

arr2ElementsCount = 3 // 6 - 2
arr2Elements = [1,2,3,4]
arr2Rest = [5,6,7,8]

Тут проверка не проходит, так как последний элемент arr2Elements больше, чем первый элемент arr1Rest. Получается, что мы взяли слишком мало элементов из arr1, нужно больше.

Те элементы, что уже взяты ([1,2]) мы отбросим, так как они точно входят в arrMergedLeft. Возьмем оставшиеся - и повторим с ними все то же самое: разделим пополам, и предположим, что первая половина входит в arrMergedLeft.

Таким образом, arr1Elements увеличится, придется все пересчитать.

arr1Elements = [1,2,3]
arr1Rest = [4]

arr2ElementsCount = 3
arr2Elements = [1,2,3]
arr2Rest = [4,5,6,7,8]

Теперь проверка проходит.

Код

В разборе для наглядности использовалось количество элементов в частях массивов. Разумеется, в коде удобнее и проще использовать индексы. То есть мы не будем вычислять arr2ElementsCount, а вычислим, элементы до какого индекса входят в arrayMergedLeft.

Также мы будем использовать указатели left и right для обозначения той части массива arr1, с которой мы сейчас работаем. Изначально они будут стоять по краям массива (`0` и `arr1.length - 1`). Если проверка не пройдет, мы будем их сдвигать (либо один, либо другой).

Сложность

В неудачном случае (если проверка не проходит), мы делим массив arr1 надвое - "разделяй и властвуй", следовательно сложность алгоритма составляет O(log(n)).

Решение (видео, англ.)

#hard #arrays

@leetcode_furrycat

[Условие] Leetcode #5. Longest Palindromic Substring

Ссылка на задачу на Leetcode
Решение

На вход получаем строку s, необходимо найти самую длинную подстроку, которая является палиндромом (читается в обе стороны одинаково).

Ограничения:

- длина строки s = [1, 1000]
- строка s состоит только из английских букв и цифр

#medium #strings

@leetcode_furrycat

[Решение] Leetcode #5. Longest Palindromic Substring

Условие задачи

Проходимся в цикле по всем символам строки. Для каждого символа (`currentIndex`) определяем палиндромную строку с этим символом в центре - то есть начинаем с этого символа и пытаемся наращивать подстроку в обе стороны до тех пор, пока она остается палиндромом.

Для набираемой подстроки нужно хранить индекс начала (`left`) и конца (`right`). Изначально left = currentIndex, right = currentIndex.

Начинать следует с последовательности одинаковых символов любой длины - это ядро палиндрома. То проверяем правые от currentIndex символы, если они одинаковые, раздвигаем, отодвигаем right.

Когда одинаковые символы закончились, пробуем расширять подстроку по одному символу в обе стороны сразу. Если слева и справа от нее находятся одинаковые символы, значит, она продолжает оставаться палиндромом, можно сдвинуть left и right.

Потом просто находим самый длинный палиндром из полученных.

#medium #strings

@leetcode_furrycat

Подборки задач с LeetCode

Blind 75: 75 самых популярных задачек, которые часто встречаются на собеседованиях. Удобно разделены по темам: Массивы, Бинарные операции, Динамическое программирование, Графы, Интервалы, Связные списки, Матрицы, Строки, Деревья и Кучи.

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

Grind 75: улучшенная версия Blind 75. Это фактически план обучения, разбитый понедельно. Сложность задачек постепенно увеличивается.

#подборки

@leetcode_furrycat

[Условие] Leetcode #121. Best Time to Buy and Sell Stock

Ссылка на задачу на Leetcode
Решение

У нас есть некоторая акция, цена которой каждый день меняется. Эти цены занесены в массив prices. Необходимо определить самую выгодную комбинацию дней для покупки и продажи этой акции. Разумеется, нельзя продать раньше, чем купишь. Функция должна вернуть размер максимальной прибыли.

Кейс 1:
prices: [7, 1, 5, 3, 6, 4]
ответ: 5
объяснение: выгоднее всего купить акцию во второй день (цена = 1) и продать в пятый (цена = 6)

Кейс 2:
prices: [7,6,5,4,3,1]
ответ: 0
объяснение: с этой акции в этот период нельзя получить прибыль

Ограничения:

prices.length = [1, 10^5]
prices[i] = [0, 10^4]

#easy #arrays #twopointers

@leetcode_furrycat

[Решение] Leetcode #121. Best Time to Buy and Sell Stock

Условие задачи

Используем подход с двумя указателями (`left` и `right`). Изначально устанавливаем их на первый и второй день.

Если цена между этими днями упала, то этот период нам не нужен. Можем сдвинуть указатели - left встает на место right, а right сразу же за ним.

Если цена между этими днями выросла, то считаем прибыль и записываем ее во временную переменную. После этого сдвигаем только right (на одну позицию дальше), так как в следующие дни акция снова смогла вырасти.

Повторяем эту операцию в цикле, пока right не достигнет конца массива.

Таким образом мы учитываем все периоды, в которые была прибыль.
Если обнаруживаем падение цены (`right` меньше `left`), то начинаем отсчет с этого места, так как для всех дальнейших периодов прибыль с нового `left` будет больше, чем со старого.

#easy #arrays #twopointers

@leetcode_furrycat

[Условие] Leetcode #217. Contains Duplicate

Ссылка на задачу на Leetcode
Решение

Получаем на вход массив целых чисел nums. Нужно вернуть true, если хоть одно значение встречается два раза (или больше).

Кейс 1
nums = [1,2,3,1]
output: true

Кейс 2
numbs = [1,2,3,4]
output: false

#easy #arrays #hashtable

@leetcode_furrycat

[Решение] Leetcode #217. Contains Duplicate

Условие задачи

Задачка выглядит несложной. В голову приходят два способа решения.

1 - с помощью хеша.
Создаем дополнительный объект, который будет служить хешем (трата памяти).
Проходим в цикле по каждому элементу массива и записываем его как ключ хеша.
Если такой элемент в хеше уже есть, значит, есть совпадение, возвращаем true.

2 - с использованием Set.
Создаем из нашего массива Set (без дублирующихся элементов) и сравниваем их размеры.

Оба алгоритма имеют сложность O(n).

#easy #arrays #hashtable

@leetcode_furrycat

[Условие] Leetcode #238. Product of Array Except Self

Ссылка на задачу на Leetcode
Решение 1 и Решение 2

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

То есть answer[0] - это произведение всех элементов массива nums, кроме нулевого.

Кейс 1
nums = [1,2,3,4]
output: [24,12,8,6]

Гарантируется, что результат умножения элементов массива всегда будет 32-битным целым числом.

Важно: сложность алгоритма должна быть O(n) и нельзя использовать деление.

#medium #arrays #prefixsum

@leetcode_furrycat

[Решение 1] Leetcode #238. Product of Array Except Self

Условие задачи

Предположим, что наш входной массив выглядит так: [a,b,c,d].

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

для элемента 0
nums[0] = a
предыдущих членов нет

для элемента nums[1] = b
произведение предыдущих членов = a

для элемента nums[2] = c
произведение предыдущих членов = a * b

для элемента nums[3] = d
произведение предыдущих членов = a * b * c

Тут можем вывести простую формулу:

production(i) = production(i - 1) * nums[i - 1]

или словами: для каждого элемента i произведение предыдущих элементов равно:
произведение, вычисленное для i-1,
умножить на элемент i-1.

Получится вот такой промежуточный результат:

[undefined, a, ab, abc]

Теперь пройдем в другую сторону и сделаем то же самое (постфиксное произведение):

[bcd, cd, d, undefined]

Если объединить эти два массива, мы получим решение задачи:

[bcd, a * cd, ab * d, abc]

Мы можем использовать подход с двумя указателями, чтобы одновременно идти по массиву с двух сторон. Тут важно хранить оба массива отдельно, чтобы элементы не дублировались, а в результат записывать уже результат их объединения.

Так как мы идем по массиву с обоих сторон одновременно, в одном цикле, временная сложность получается всего O(n).
Но и памяти мы тратим прилично - для хранения двух промежуточных массивов.

#medium #arrays #prefixsum

@leetcode_furrycat

[Решение 2] Leetcode #238. Product of Array Except Self

Условие задачи

А вот и более изящное решение, основанное на том же подходе префиксных и постфиксных произведений (см. предыдущий пост).

Мы не будем хранить массивы с вычисленными значениями, мы будем просто накапливать значение префиксного и постфиксного произведения.

Начнем с нуля и пойдем по массиву, увеличивая одновременно префиксное произведение для элемента i и постфиксное произведение для элемента nums.length - i - 1 и обновляя соответствующие индексы в результирующем массиве.

Исходные данные:

nums = [a,b,c,d]
result = [1,1,1,1] // заполняем единицами
len = nums.length
pre = 1 // накопл. префиксное произв. для i-го элемента с начала массива
post = 1 // накопл. постфиксное произв. для i-го элемента с конца массива

На каждом шаге делаем следующее:

// обновляем результат для элемента i с начала массива
result[i] = result[i] * pre 
// увеличиваем pre для следующего элемента 
pre = pre * nums[i]
// обновляем результат для элемента i с конца массива 
result[len - i - 1] = result[len - i - 1] * post 
// увеличиваем post для следующего элемента 
post = post * nums[len - i - 1]

Промежуточные результаты по шагам:

i = 0 
result = [1, 1, 1, 1]
pre = a 
post = d 

i = 1
result = [1, a, d, 1]
pre = ab 
post = cd 

i = 2 
result = [1, acd, abd, 1]
pre = abc 
post = bcd 

i = 3 
result = [bcd, acd, abd, abc]
pre = abcd 
post = abcd

#medium #arrays #prefixsum

@leetcode_furrycat

[Условие] Leetcode #53. Maximum Subarray

Ссылка на задачу на Leetcode
Решение

Получаем на вход массив целых чисел nums. Необходимо найти подмассив с самой большой суммой элементов. На выходе должна быть сумма элементов подмассива.

Подмассив - это непрерывная и непустая последовательность элементов. Сам массив тоже является своим подмассивом.

Кейс 1
nums = [-2,1,-3,4,-1,2,1,-5,4]
Ответ: 6
Объяснение: подмассив с самой большой суммой [4, -1, 2, 1]

Кейс 2
nums = [1]
Ответ: 1

Кейс 3
nums = [5,4,-1,7,8]
Ответ: 23
Объяснение: подмассив с самой большой суммой [5,4,-1,7,8]

Примечание: если получится найти решение со сложностью O(n), постарайтесь найти более "изящное" решение с использованием подхода "разделяй и властвуй".

#medium #arrays #dp #recursion #divideandconquer #prefixsum

@leetcode_furrycat

[Решение 1. Рекурсия] Leetcode #53. Maximum Subarray

Условие задачи

Эту задачу можно решить несколькими способами (помимо грубой силы). Мы начнем с рекурсии.

🔹Логика такая:

У нас есть массив чисел [a,b,c,d] с первым элементом a:

[a, ...rest]

Для этого элемента есть всего два возможных варианта:
1. он либо входит в искомый максимальный подмассив
2. либо не входит

Каждый из этих вариантов мы обработаем, а потом просто сравним два полученных результата и выберем максимальный.

В любом случае мы этот элемент временно откладываем и переходим к массиву массиву rest. Его можно представить в таком же виде:

[b, ...rest2]

Таким образом будем рекурсивно погружаться, пока массив не кончится.

🟢 Вариант 1 (элемент входит в искомый подмассив)

Назовем это firstElementMustPick = true.

Если мы предполагаем, что a входит в искомый подмассив, то на следующем витке рекурсии у нас появляется некоторая определенность.

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

Важно не забыть, что у нас есть еще элемент a, который тоже входит в этот подмассив. Его нужно будет прибавить к полученному результату.

🟢 Вариант 2 (элемент не входит в искомый подмассив)

firstElementMustPick = false.

Просто повторяем те же самые предположения:

1 - b входит в искомый подмассив
2 - или b не входит в искомый подмассив

Сравниваем 1 и 2, чтобы найти максимум.

🟢 Функция

Выглядеть все это будет примерно так:

function getMaxSubarraySum(nums, startIndex = 0, firstElementMustPick = false) {
    const currentElement = nums[startIndex]
    const sumWithFirstElement = currentElement + getMaxSubarraySum(nums, startIndex + 1, true);

    if (firstElementMustPick) {
        return sumWithCurrentElement;
    }

    const sumWithoutFirstElement = getMaxSubarraySum(nums, startIndex + 1, false);

    return Math.max(sumWithCurrentElement, sumWithoutCurrentElement)
}

🟢 Крайний случай

Рано или поздно мы доберемся до крайнего случая, когда наш массив закончится (когда startIndex достигает длины массива `nums`).

Например, массив изначально состоял из одного элемента:

const nums = [f]

Опять рассматриваем два варианта для элемента f:

1 - f входит в подмассив
2 - f не входит в подмассив

const sumWithFirstElement = f + getMaxSubarraySum(nums, 1, true);
const sumWithoutFirstElement = getMaxSubarraySum(nums, 1, false);
return Math.max(sumWithCurrentElement, sumWithoutCurrentElement);

Что должна вернуть функция getMaxSubarraySum в первом и втором случае?

Тут становится очевидно, что в крайнем случае функция должна возвращать разные значения в зависимости от параметра firstElementMustPick. В первом случае - 0, чтобы не повлиять на общую сумму. Во втором случае - очень маленькое значение, чтобы всегда проигрывать в сравнении.

if (startIndex >= nums.length) {
    if (firstElementMustPick) return 0;
    return -Infinity;
}

🟢 Полный код

function getMaxSubarraySumRecursive(nums, startIndex, firstElementMustPick) {
 if (startIndex >= nums.length) {
  if (firstElementMustPick) return 0;
  return -Infinity;
 }

    const currentElement = nums[startIndex];

    const sumWithFirstElement = currentElement + getMaxSubarraySumRecursive(nums, startIndex + 1, true);

    if (firstElementMustPick) {
        return Math.max(sumWithCurrentElement, 0);
    }

    const sumWithoutFirstElement = getMaxSubarraySumRecursive(nums, startIndex + 1, false); 

    return Math.max(sumWithFirstElement, sumWithoutFirstElement)
}

function maxSubArray(nums: number[]): number {
 return getMaxSubarraySumRecursive(nums, 0, false);
}

#medium #arrays #recursion

@leetcode_furrycat

🔼

Оценка

Временная сложность этого решения - O(n^2). Для каждого элемента мы запускаем две ветки выполнения, каждая из которых проходит по всему массиву. Это очень много, и на Leetcode это решение проваливается на очень большом массиве.

Но это решение хорошо подходит для оптимизации с помощью методов динамического программирования.

#medium #arrays #recursion

@leetcode_furrycat

[Решение 2. ДП, мемоизация] Leetcode #53. Maximum Subarray

Условие задачи: https://t.iss.one/leetcode_furrycat/28

Если посмотреть на рекурсивное решение задачи https://t.iss.one/leetcode_furrycat/29 повнимательнее, то можно заметить, что у нас много повторяющихся вычислений: сначала мы для нулевого элемента массива считаем все последующие комбинации (от 1 до конца, от 2 до конца, от 3 до конца). Потом для первого считаем практически то же самое (от 2 до конца, от 3 до конца и т.д.)

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

const nums = [5,4,-1,7,8]
const dp = {
    0: [23,18,15,15,8],
    1: [null, 18,14,15,8]
}

Ключи 0 и 1 - это значения параметра firstElementMustPick, а массивы чисел - это максимальные суммы для каждого элемента исходного массива. Рассчитываем их один раз, а потом просто переиспользуем.

#medium #arrays #dp

@leetcode_furrycat

[Решение 3.1. ДП, табуляция] Leetcode #53. Maximum Subarray

Условие задачи: https://t.iss.one/leetcode_furrycat/28

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

Возьмем сначала самый маленький подмассив (состоящий из одного элемента) и посчитаем сумму для него - сохраним это значение.

Затем увеличим этот массив на один элемент. Новый элемент может:
1) входить в искомый подмассив вместе с предыдущим
2) входить в искомый подмассив самым первым (открывать его)
3) не входить в искомый подмассив

В dp[1][i] мы сохраним максимальный вариант из 1) и 2).
А в dp[0][i] - максимальный вариант из ранее сохраненного (`dp[0][i-1]`) и только что посчитанного (`dp[1][i]`).

В dp[1] мы будем хранить значения с учетом того, что элемент входит в подмассив, а в dp[0] - без учета, то есть просто максимально возможное значение.

Таким образом, в кеше в элементе с индексом i у нас будет находиться максимальная сумма для соответствующего элемента массива nums (точнее для подмассива [0, i]).

Пошаговый разбор:

const nums = [-2,1,-3,4,-1,2,1,-5,4]
const dp = {
    0: [-2],
    1: [-2]
}

i = 1
если i-й элемент входит в подмассив
- то он либо следует за предыдущим элементом (dp[1][0] + nums[1] = -2 + 1 = 1)
- либо начинает этот массив сам (nums[1] = 1)
находим максимум и добавляем в кеш

если i-й элемент не входит в подмассив
находим максимум между предыдущим значением в этом массиве (максимальная сумма для предыдущего элемента) dp[0][i - 1] = -2
и только что посчитанной максимальной суммой для текущего dp[1][i] = 1

dp = {
    0: [-2, 1],
    1: [-2, 1]
}

i = 2
dp[1][2] = Math.max(dp[1][1] + nums[2], nums[2]) = Math.max(1 + -3, -3) = -2
dp[0][2] = Math.max(dp[0][1], dp[1][2]) = Math.max(1, -3) = 1

Ответом всегда будет последнее значение в dp[0], так как там хранится максимально возможная сумма подмассива для последнего индекса.

#medium #arrays #dp

@leetcode_furrycat

[Решение 3.2. ДП, табуляция] Leetcode #53. Maximum Subarray

Условие задачи: https://t.iss.one/leetcode_furrycat/28

Предыдущее решение с использованием метода табуляции можно еще больше упростить. Там мы сохраняли каждое промежуточное значение - даже два для каждого элемента (в вхождением в подмассив и без). Но в принципе мы можем просто сразу выбирать самое большое из возможных для данного индекса значений:

- сумма, накопленная для предыдущего элемента, плюс текущий элемент
- или только текущий элемент (если предыдущая сумма отрицательна)

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

const dp = [...nums]

for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
}

return Math.max.apply(null, dp);

#medium #arrays #dp

@leetcode_furrycat

🔼 Временная сложность алгоритмов, использующих приемы динамического программирования, - O(n), так как по массиву мы проходим только один раз, и используем при этом ранее вычисленные значения.


#medium #arrays #dp

@leetcode_furrycat