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

Sort vs. Rearrangement

Решал задачу "Sort Array by Parity"
Сначала подумал:
“Разделить, отсортировать, объединить” - звучит логично? Да.
Но... Памяти потребляется много.

А потом осенило:
Используй два указателя.
✅ Один дополнительный индекс
❌ Без списков
❌ Без сортировки
❌ Без лишней памяти

Было: O(n²) Стало: O(n)

Иногда перестановка лучше, чем сортировка 🥹

#leetcode
#sorting
#algorithm
#easy
#developer

💡 Channel | ✏ Chat