Решенные задачи

1 - Two sum
2 - Add two numbers
3 - Longest Substring Without Repeating Characters
4 - Median of Two Sorted Arrays
5 - Longest Palindromic Substring
10 - Regular Expression Matching
11 - Container With Most Water
15 - 3Sum
33 - Search in Rotated Sorted Array
53 - Maximum Subarray
121 - Best Time to Buy and Sell Stock
152 - Maximum Product Subarray
153 - Find Minimum in Rotated Sorted Array
217 - Contains Duplicate
238 - Product of Array Except Self

По сложности

#easy
#medium
#hard

По темам и методам решения

#strings
#arrays
#linkedlists
#dp
#divideandconquer
#twopointers
#hashtable
#prefixsum

#ретро

[Условие] 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

[Решение 4.2. Оптимизация Разделяй и властвуй] Leetcode #53. Maximum Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/28

И наконец, мы можем еще сократить время выполнения алгоритма, заранее посчитав префиксные и суффиксные суммы.

const prefixes = [...nums]
const suffixes = [...nums] 

for (i = 1; i < nums.length; i++) {
  const previousSum = prefixes[i - 1];
  prefixes[i] += Math.max(0, previousSum);
}

for (i = nums.length - 2; i >= 0; i--) {
  const previousSum = suffixes[i + 1];
  suffixes[i] += Math.max(0, previousSum;
}

Теперь рассчитать maxCenterSubArraySum намного проще:

const maxCenterSubArraySum = prefixes[mid] + suffixes[mid+1]

Временная сложность: O(n)
Пространственная сложность: O(n)

#medium #arrays #divideandconquer #prefixsum

@leetcode_furrycat

[Решение] Leetcode #53. Maximum Subarray

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

Итого у нас получилось больше 5 способов решить одну и ту же задачку.

0 - Brute force
1 - Простая рекурсия
2 - Рекурсия с мемоизацией вычислений
3 - Табуляция, оптимизированная табуляция
4 - Алгоритм Кадане
5 - Разделяй и властвуй + оптимизация с предварительным расчетом

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

@leetcode_furrycat

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

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

Условие похоже на предыдущую задачу:

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

Кейс 1
nums = [2,3,-2,4]
Ответ: 6
Объяснение: [2,3]

Кейс 2
nums = [-2,0,-1]
Ответ: 0
Объяснение: 2 получиться не может, так как [-2,-1] это не подмассив, все остальные варианты дают 0 или отрицательное число

#medium #arrays #dp #prefixsum

@leetcode_furrycat

[Решение] Leetcode #152. Maximum Product Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/39

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

Для задачи с наибольшей суммой его суть заключалась в том, что мы проходили по массиву слева направо и вычисляем наибольшую возможную сумму для ТЕКУЩЕГО элемента (от начала массива до текущего элемента). А затем просто брали максимальное из полученных значений.

Но с произведением все немного по-другому. Здесь у нас есть нули, которые любой подмассив сведут к нулю, а также отрицательные числа, которые по одиночке радикальном уменьшают общее произведение, но парами очень даже увеличивают. То есть здесь мы не можем сказать, что максимально возможное произведение для 2-го элемента - это именно то, что нам нужно, чтобы получить максимальное произведение для 3-го элемента.

Пример:

const nums = [-2, 3, -4]

для n=1: maxTillNow = -2
для n=2: maxTillNow = Math.max(3, -6) = 3
для n=3: maxTillNow = Math.max(3, -12) = 3

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

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

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

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

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

function maxProduct(nums) {
    let currentProduction = 1;
    let maxTillNow = -Infinity;

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

    currentProduction = 1;

    for (let i = nums.length - 1; i >= 0; i--) {
        const el = nums[i];
        currentProduction *= el;
        maxTillNow = Math.max(maxTillNow, currentProduction);
        if (currentProduction === 0) {
            currentProduction = 1;
        }    
    }

    return maxTillNow;
}

Временная сложность: O(N) - мы делаем два прохода по массиву, но коэффициент отбрасывается

#medium #arrays #dp #prefixsum

@leetcode_furrycat

Blind 75. Arrays

Небольшое ретро по задачкам из раздела Массивы:

1 - Two sum (easy)
11 - Container With Most Water (medium)
15 - 3Sum (medium)
33 - Search in Rotated Sorted Array (medium)
53 - Maximum Subarray (medium)
121 - Best Time to Buy and Sell Stock (easy)
152 - Maximum Product Subarray (medium)
153 - Find Minimum in Rotated Sorted Array (medium)
217 - Contains Duplicate (ease)
238 - Product of Array Except Self (medium)

Какие подходы к решению использовались:

👉 Два указателя (#twopointers)

Используется, когда "второй" элемент всегда идет после "текущего". Часто используется для отбора последовательно идущих элементов, которые в комбинации соответствуют определенному условию.

- два/три элемента, составляющие определенную сумму (Two sum, 3Sum)
- две линии, составляющие прямоугольник наибольшей площади (Container With Most Water)
- две даты, между которыми акция росла больше всего (Best Time to Buy and Sell Stock)

👉 Хеш-таблица (#hashtable)

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

- Быстро найти второе слагаемое для известной суммы и первого слагаемого (Two sum)
- Найти дубликаты ( Contains Duplicate)

👉 Разделяй и властвуй (#divideandconquer)

Используется с отсортированными массивами, когда есть возможность определить, в какой части массива находится нужное значение. Часто используется для поиска (бинарный поиск) элемента (Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array). Но может использоваться и в более сложном виде, например, для поиска подмассива с максимальной суммой (Maximum Subarray).

👉 Рекурсия (#recursion)

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

Например, мы использовали рекурсию для поиска подмассива с максимальной суммой (Maximum Subarray).

👉 Динамическое программирование (#dp)

У динамического программирования есть несколько разновидностей: мемоизация и табуляция. Сюда же можно включить вычисление префиксных сумм (#prefixsum). Подвидом ДП является алгоритм Кадане.
Суть метода в том, что мы используем результаты предыдущих вычислений.
Динамическое программирование часто используется в задачах с массивами для нахождения подмассива с заданными свойствами, например, с максимальной суммой (Maximum Subarray, Maximum Product Subarray)
Также с его помощью (префиксные суммы) мы вычисляли произведение всех элементов массива кроме текущего (Product of Array Except Self).

👉 Set

При работе с массивами может быть полезна структура данных Set, которая позволяет быстро удалить дубликаты из массива (Contains Duplicate), а также обеспечивает быстрый доступ к элементам массива по их значению.

#arrays #ретро

@leetcode_furrycat