[Условие] Leetcode #153. Find Minimum in Rotated Sorted Array

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

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

Слишком просто, да?) Да, загвоздка в том, что массив у нас rotated ("прокручен" что ли) несколько раз.

Например, если у нас есть массив [0,1,2,3,4] и мы его один раз "прокрутим", получится [4,0,1,2,3]. Если еще один раз прокрутим, будет [3,4,0,1,2].

Так вот наш массив прокручен от 1 до n раз. И мы должны найти в нем минимальный элемент. И сделать это нужно алгоритмом с временной сложностью не более, чем O(log n).

Кейс 1
nums = [3,4,5,1,2]
ответ: 1
объяснение: оригинальный отсортированный массив [1,2,3,4,5] прокручен 3 раза

#medium #arrays #divideandconquer

@leetcode_furrycat

[Решение] Leetcode #153. Find Minimum in Rotated Sorted Array

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

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

Берем исходный массив и находим его середину. Теперь нужно выяснить, в какой части массива (левой или правой) нужно продолжить поиск.

Тут может быть две ситуации:

- центральный элемент меньше первого элемента массива
например, [4,5,1,2,3] или [5,1,2,3,4]
тогда либо центральный элемент искомый, либо мы продолжаем поиск в левой части массива

- центральный элемент больше первого элемента массива
например, [1,2,3,4,5] или [3,4,5,1,2]
тогда либо первый элемент искомый, либо мы продолжаем поиск в правой части массива

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

function findMin(nums: number[]): number {
  let start = 0;
  let end = nums.length - 1;
  let min = Infinity;

  while(start <= end) {
    const mid = Math.floor((start + end) / 2);
    if (nums[start] <= nums[mid]) {
      min = Math.min(min, nums[start]);
      start = mid + 1;
    } else {
      min = Math.min(min, nums[mid]);
      end = mid - 1;
    }
  }

  return min;
}

#medium #arrays #divideandconquer

@leetcode_furrycat

[Условие]. Leetcode #33. Search in Rotated Sorted Array

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

Тут мы снова имеем дело с rotated массивами (можно посмотреть в предыдущей задачке подробнее). На этот раз нам нужно искать конкретный элемент в таком "прокрученном" массиве. Нужно вернуть либо индекс искомого элемента, либо -1, если элемента в массиве нет.

Кейс 1
nums = [4,5,6,7,0,1,2], target = 0
ответ: 4

Кейс 2
nums = [4,5,6,7,0,1,2], target = 3
ответ: -1

Необходимо решить задачку за O(log n).

#medium #arrays #divideandconquer

@leetcode_furrycat

[Решение] Leetcode #33. Search in Rotated Sorted Array

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

Решение довольно простое. Как и в предыдущем примере мы берем массив, находим средний элемент и делим массив пополам. Проверив ряд простых условий, определяем, в какой половине продолжать поиск.

Основная сложность здесь - учесть все возможные ситуации.

function search(nums: number[], target: number): number {
    let start = 0 
    let end = nums.length - 1
    
    while(start <= end) {
        const mid = Math.floor((start + end) / 2)

        if (nums[mid] === target) return mid

        if (nums[start] <= nums[mid]) {
            if (target >= nums[start] && target < nums[mid]) {
                end = mid - 1 
            } else {
                start = mid + 1
            }
        } else {
            if (target > nums[mid] && target <= nums[end]) {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
    }

    return -1
}

#medium #arrays #divideandconquer

@leetcode_furrycat

[Условие]. Leetcode 15. 3Sum

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

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

Кейс 1
nums = [-1,0,1,2,-1,4]
ответ: [ [-1, -1, 2], [-1, 0, 1] ]

Кейс 2
nums = [0,1,1]
ответ: []

Кейс 3
nums = [0,0,0]
ответ: [[0,0,0]]

#medium #arrays #twopointers

@leetcode_furrycat

[Решение] Leetcode #15. 3Sum

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

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

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

function threeSum(nums: number[]): number[][] {
    if (nums.length < 3) return [];

    nums.sort((a, b) => a - b);
    if (nums[0] > 0) return [];

    const triplets = [];

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) break;
        if (nums[i] === nums[i - 1]) continue;

        let j = i + 1;
        let k = nums.length - 1;
        
        while(j < k) {
            const sum = nums[i] + nums[j] + nums[k];
            if (sum === 0) {
                triplets.push([nums[i], nums[j], nums[k]]);
                j++;
                k--;
            } else if (sum < 0) {
                j++;
            } else {
                k--;
            }
        }
    }

    return triplets;
}

#medium #arrays #twopointers

@leetcode_furrycat

[Условие]. Leetcode 11. Container With Most Water

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

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

Кейс 1
height = [1,8,6,2,5,4,8,3,7] (на картинке)
Ответ: 49 (между линиями с высотой 8 и 7)

#medium #arrays #twopointers

@leetcode_furrycat

[Решение]. Leetcode 11. Container With Most Water

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

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

function getVolume(height: number[], left: number, right: number): number {
    const h1 = height[left]
    const h2 = height[right]
    return Math.min(h1, h2) * (right - left)
}

function maxArea(height: number[]): number {
    let left = 0
    let right = height.length - 1
    let max = 0

    while(left < right) {
        max = Math.max(max, getVolume(height, left, right))

        if (height[left] < height[right]) {
            left++
        } else {
            right--
        }
    }

    return max
}

#medium #arrays #twopointers

@leetcode_furrycat