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

Имея два массива arr1[] и arr2[] размером N каждый, задача состоит в том, чтобы найти минимальное количество взаимозаменяемых одинаковых индексированных элементов, необходимое для того, чтобы оба массива строго возрастали.

Примечание. Верните -1, если невозможно сделать их строго возрастающими.

Примеры:

Input: arr1 = {1, 3, 5, 4}, arr2 = {1, 2, 3, 7}
Output: 1
Explanation:  
Swap arr1[3] and arr2[3]. 
Then the sequences are:
arr1 = [1, 3, 5, 7] and arr2 = [1, 2, 3, 4] which are both strictly increasing.
Therefore, minimum number of swaps required =1.

Input: arr1 = {0, 3, 5, 8, 9}, nums2 = {2, 1, 4, 6, 9}
Output: 1

Подход: Задача может быть решена на основе следующего наблюдения:

For each index there are two choices: either swap the elements or not. If in both cases the prefixes of both arrays are not strictly increasing then it is not possible to perform the task. Otherwise, continue with this approach.

The above observation can be implemented using dynamic programming concept. Create two dp[] arrays where – 

• The i^th index of one will store the minimum steps required to make the prefixes strictly increasing when the current elements are swapped and 
• The other array will store the minimum steps when the current one is not swapped.

Выполните шаги, указанные ниже, чтобы реализовать вышеуказанное наблюдение:

• Рассмотрим два массива swap[] и noswap[], где –
  • swap[i] сохраняет минимальные шаги, когда arr1[i] и arr2[i] меняются местами, если массив отсортирован от 0 до i-1 .
  • noswap[i] хранит минимальные шаги, когда нет обмена между arr1[i] и arr2[i] при условии, что массив отсортирован от 0 до i-1 .
• Перебрать массив и на основе отношений между элементами массива в i ^-м и (i-1) ^-м индексах обновить значение массивов.
  • Если arr1[i] и arr2[i] больше, чем (i-1) ^-е элементы обоих массивов, то
    • Если текущие значения меняются местами, предыдущие также должны быть заменены местами. Итак, своп[i] = своп[i-1]+1
    • Если текущие элементы не меняются местами, то же самое следует сделать с предыдущими элементами. Итак, noswap[i] = noswap[i-1]
  • Если arr1[i] больше, чем arr2[i-1], а arr2[i] больше, чем arr1[i-1]:
    • Если мы поменяем местами i ^-е элементы индекса, то мы не должны менять местами (i-1) ^-е элементы индекса. Таким образом, swap[i] = min(swap[i], noswap[i-1]).
    • По тому же условию noswap[i] = min(noswap[i], swap[i-1]+1).
• Требуемый ответ — это минимальное значение среди значений последнего индекса массива swap[] и массива noswap[] .

Ниже приведена реализация вышеупомянутого подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)