Merge Sorted Array

Дано

nums1 имеет длину m + n: первые m элементов отсортированы, последние n ячеек свободны. В nums2 находятся n отсортированных элементов. Нужно изменить nums1 in-place.

nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6],          n = 3
result: [1, 2, 2, 3, 5, 6]

Почему заполняем с конца

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

static void merge(int[] nums1, int m, int[] nums2, int n) {
    int left = m - 1;
    int right = n - 1;
    int write = m + n - 1;
 
    while (right >= 0) {
        if (left >= 0 && nums1[left] > nums2[right]) {
            nums1[write--] = nums1[left--];
        } else {
            nums1[write--] = nums2[right--];
        }
    }
}

Когда nums2 исчерпан, остаток nums1 уже стоит на месте. Когда nums1 исчерпан, цикл копирует остаток nums2.

Инвариант

После каждой итерации диапазон (write, m + n) заполнен наибольшими элементами обоих еще не обработанных префиксов и находится на окончательных позициях.

Сложность и границы

• время O(m + n);
• дополнительная память O(1);
• m = 0 — весь nums2 копируется;
• n = 0 — цикл не выполняется;
• дубликаты и отрицательные числа работают без отдельной ветки.

На собеседовании

• Почему идти с конца? Не затирать вход в nums1.
• Почему условие цикла только right >= 0? Остаток первого массива уже на месте.
• Дополнительная память? O(1).
• Что является свободной областью? Ячейки nums1[m, m+n), а не обязательно нули как значения.