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

[Решение 3.3. ДП, алгоритм Кадане] Leetcode #53. Maximum Subarray

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

Мы можем пойти еще дальше и отказаться от массива dp. На самом деле на каждом шаге нам нужно лишь предыдущее значение, значит, и хранить можно только его.

На самом деле мы будем хранить два значения - локальную сумму (локальный максимум) и глобальный максимум. Локальная сумма непрерывна, мы всегда сравниваем предыдущее накопленное значение и его сумму с текущим элементом. В глобальный максимум будем заносить только самые большим величины - он заменит нам финальный поиск самого большого элемента в массиве dp:

function kadane(nums) {
    let currentMax = 0;
    let maxTillNow = - Infinity;

    for (let i = 0; i < nums.length; i++) {
        const el = nums[i];
        currentMax = Math.max(el, currentMax + el);
        maxTillNow = Math.max(maxTillNow, currentMax)
    }

    return maxTillNow;
}

Временная сложность у этого алгоритма тоже равна O(n), зато пространственная всего O(1).

#medium #arrays #dp

@leetcode_furrycat

[Решение 4.1. Разделяй и властвуй] Leetcode #53. Maximum Subarray

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

Стратегия "Разделяй и властвуй" предполагает деление исходного массива на несколько частей. Мы будем делить на три (левую L, правую R и центральный элемент `mid`). Тогда наш искомый подмассив с максимальной суммой может лежать:

- полностью в левой части L (от 0 до `mid-1`)
- полностью в правой части R (от mid+1 до `n.length-1`)
- либо включает в себя обязательно центральный элемент mid и возможно части L и R, которые находятся рядом с mid

Для L и R мы запустим рекурсивное вычисление. Для третьего случая посчитаем максимальную сумму. Потом сравним три значения и вернем максимальное.

function getMaxSubArraySum(nums, left, right) {
    left = left ?? 0; // начало анализируемого подмассива
    right = right ?? nums.length - 1; // конец анализируемого подмассива

    if (left > right) return -Infinity;

    const mid = Math.floor((left + right) / 2); // середина анализируемого подмассива

    // рекурсивно считаем для левой и правой частей
    const maxLeftSubArraySum = getMaxSubArraySum(nums, left, mid - 1);
    const maxRightSubArraySum = getMaxSubArraySum(nums, mid + 1, right);

    // находим подмассив с максимальной суммой, 
    // который содержит элемент mid 

    let leftMaxSum = 0;
    let rightMaxSum = 0;

    // для L идем с конца, так как подмассив должен быть рядом с mid
    // считаем непрерывную сумму элементов и отбираем максимальную

    for (let i = mid - 1, currentLeftSum = 0; i >= left; i--) {
        currentLeftSum += nums[i];
        leftMaxSum = Math.max(leftMaxSum, currentLeftSum);
    }

    // то же для R 

    for (let i = mid + 1, currentRightSum = 0; i <= right; i++) {
        currentRightSum += nums[i];
        rightMaxSum = Math.max(rightMaxSum, currentRightSum);
    }

    const maxCenterSubArraySum = leftMaxSum + nums[mid] + rightMaxSum;

    return Math.max(maxLeftSubArraySum, maxRightSubArraySum, maxCenterSubArraySum)
}

Временная сложность этого решения - ожидаемо O (n * log n). Мы делаем log n разделений и для каждого считаем maxCenterSubArraySum, что требует перебора массива (n).

Пространственная сложность: O (log n) - так как у нас рекурсия.

#medium #arrays #divideandconquer #recursion

@leetcode_furrycat