Алгоритм: Two Pointers

Two Pointers - это техника, при которой два индекса двигаются по массиву, чтобы эффективно решать задачи без использования вложенных циклов. Я запомнил как read pointer и write pointer

➡️ Суть
- Один индекс начинает с одного конца, второй с другого. Они двигаются навстречу друг, другу или в одном направлении в зависимости от задачи;
- Позволяет решать многие задачи за O(n) вместо O(n²)
- Работает лучше всего на отсортированных данных или в задачах с поиском зависимостей между элементами.

➡️ Задача
443. String Compression

➡️ Условие

Задан массив символов chars, сжать его с помощью следующего алгоритма:

Дан массив символов chars, сжать его, используя следующий алгоритм:

Начать с пустой строки s. Для каждой группы последовательно повторяющихся символов в chars:
- Если длина группы равна 1, добавьте этот символ в s
- В противном случае добавьте символ - длина группы.
- Сжатая строка s не должна возвращаться отдельно, а должна храниться в массиве входных символов chars. 
- Обратите имание, что длина группы, равная 10 или более, будет разбита на несколько символов в chars.
- После завершения модификации входного массива верните его новую длину.
- Вы должны написать алгоритм, который использует только постоянное дополнительное пространство.

➡️ Пример

Input: chars = ["a","a","b","b","c","c","c"]
Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"]
Explanation: The groups are "aa", "bb", and "ccc". This compresses to "a2b2c3".

➡️ Решение

public static int Compress(char[] input)
{
    var begin = 0;
    var count = 0;
    
    while (begin < input.Length)
    {
        var group = 1;
        
        while (begin + group < input.Length && input[begin + group] == input[begin])
            group++;

        input[count++] = input[begin];
        begin += group;
        
        if (group > 1)
        {
            foreach (var ch in group.ToString())
                input[count++] = ch;
        }
    }

    return count;
}

➡️ HW?
1⃣ begin – начальный индекс текущей группы (индекс чтения), count – длина ответа, сжатой строки (индекс записи). group - длинна группы
2⃣ Находим длину group
3⃣ input[count++] = input[begin] - не забыть скопировать элемент в индекс записи
5⃣ begin += group - сдвигаем (индекс записи) на начало следующей группы
5⃣ вставляем длину группы

#leetcode
#medium
#algorithm
#two_pointers

💡 Channel | ✏ Chat

1299. Replace Elements with Greatest Element on Right Side

➡️ Задача
1299. Replace Elements with Greatest Element on Right Side

➡️ Условие

Дано arr[], надо заменить каждый элемент на максимальный из элементов справа. Последний элемент становится -1.

➡️ Пример

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
Explanation:
- index 0 --> the greatest element to the right of index 0 is index 1 (18).
- index 1 --> the greatest element to the right of index 1 is index 4 (6).
- index 2 --> the greatest element to the right of index 2 is index 4 (6).
- index 3 --> the greatest element to the right of index 3 is index 4 (6).
- index 4 --> the greatest element to the right of index 4 is index 5 (1).
- index 5 --> there are no elements to the right of index 5, so we put -1.

➡️ Суть

Наивный способ - для каждого элемента искать максимум справа O(n²). Это медленно для больших массивов.
Оптимальное решение - идём с конца массива и запоминаем максимум, обновляя его по ходу элементами.

➡️ Решение

public int[] ReplaceElements(int[] arr)
{
    if (arr.Length == 1) return [-1];
    if (arr.Length == 2) return [arr[1], -1];

    var last = -1;
    for (int i = arr.Length - 1; i >= 0; i--)
    {
        if (arr[i] > last)
            (arr[i], last) = (last, arr[i]);
        else
            arr[i] = last;
    }

    return arr;
}

➡️ HW?
1⃣ Начинаем с last = -1
2⃣ Двигаемся с конца массива к началу
3⃣ Для каждого элемента сохраняем его значение во временной переменной
5⃣ Заменяем текущий элемент arr[i] на last
5⃣ Обновляем last, если найден новый максимум

#leetcode
#easy
#algorithm
#two_pointers

💡 Channel | ✏ Chat