Minimize the shift required to make arr1[i] <= arr2[i] ❤️

Given two sorted non-decreasing arrays arr1[] and arr2[] of length N. The task is to make array arr1 such that arr1[i] <= arr2[i] for all i. If arr1[i] is greater than arr2[i], then shift all the elements to the right of arr1[i] by one place (including arr1[i]), (the last element will be deleted), and update arr1[i] = arr2[i]. You do not have to make any changes to arr2. Now you have to print the minimum number of shift required to make all elements of arr1 <= arr2. The maximum length of arr1 and arr2 will not exceed 10^3.

Examples:

Input: N = 6, arr1[] = {1000, 1400, 2000, 2000, 2200, 2700}, arr2[] = {800, 1200, 1500, 1800, 2200, 3000}
Output: 2
Explanation: As we can see that arr1[0] (1000) > arr2[0] (800), so we shift all elements to the right by one place (3000 will be removed) and arr1[0] will be 800, that is the new arr1[] = {800, 1000, 1400, 2000, 2000, 2200}. Now arr1[3] (2000) > arr2[3] (1800) so all elements to the right of 3 will be shifted by 1 place (2200 will be removed) and arr1[3] will be 1800, that is the new arr1[] = {800, 1000, 1400, 1800, 2000, 2000}. Now there is no need to make further changes as all elements of arr1 <= arr2. As we have made 2 shifts so the output is 2.

Input: N = 6, arr1[] = {4, 5, 6, 7, 8, 9}, arr2[] = {1, 2, 3, 4, 5, 6}
Output: 3
Explanation: The first shift will be at arr1[0], so now arr1 = {1, 4, 5, 6, 7, 8}. The second shift will be at arr1[1], so now arr1 = {1, 2, 4, 5, 6, 7}. The third shift will be at arr1[2], so now arr1 = {1, 2, 3, 4, 5, 6}. Now the condition has been fulfilled, so there is no need to make changes, and as 3 shifts are made, the output is 3.

Approach: To solve the problem follow the below idea:

Iterate through each element in arr1. Then check if arr1[i] > arr2[i] then we shift all elements from index i to one more unit to their right side.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;

void shift(vector<int>& A, int k)
{

    // we iterating in reverse as we do not need last
    // element
    for (int i = A.size() - 1; i > k; i--) {
        A[i] = A[i - 1];
    }
    return;
}

int main()
{
    int N = 6;
    vector<int> A = { 1000, 1400, 2000, 2000, 2200, 2700 };
    vector<int> B = { 800, 1200, 1500, 1800, 2200, 3000 };
    int ans = 0; // this will keep count of shifts made
    for (int i = 0; i < N; i++) {
        if (A[i] > B[i]) {

            // we will pass array A and index i as we have
            // to shift from i
            shift(A, i);

            // increasing count
            ans++;

            // updating A[i]
            A[i] = B[i];
        }
    }
    cout << ans << "\n";
    return 0;
}

Java

import java.util.*;

public class GFG {

    public static void shift(List<Integer> A, int k)
    {
        // we iterating in reverse as we do not need last
        // element
        for (int i = A.size() - 1; i > k; i--) {
            A.set(i, A.get(i - 1));
        }
        return;
    }

    public static void main(String[] args)
    {
        int N = 6;
        List<Integer> A = Arrays.asList(1000, 1400, 2000,
                                        2000, 2200, 2700);
        List<Integer> B = Arrays.asList(800, 1200, 1500,
                                        1800, 2200, 3000);
        int ans = 0; // this will keep count of shifts made
        for (int i = 0; i < N; i++) {
            if (A.get(i) > B.get(i)) {

                // we will pass array A and index i as we
                // have to shift from i
                shift(A, i);

                // increasing count
                ans++;

                // updating A[i]
                A.set(i, B.get(i));
            }
        }
        System.out.println(ans);
        return;
    }
}

Python

def shift(A, k):
    # we iterating in reverse as we do not need last
    # element
    for i in range(len(A) - 1, k, -1):
        A[i] = A[i - 1]

N = 6
A = [1000, 1400, 2000, 2000, 2200, 2700]
B = [800, 1200, 1500, 1800, 2200, 3000]
ans = 0  # this will keep count of shifts made
for i in range(N):
    if A[i] > B[i]:
        # we will pass array A and index i as we have
        # to shift from i
        shift(A, i)

        # increasing count
        ans += 1

        # updating A[i]
        A[i] = B[i]

print(ans)

JavaScript

function shift(A, k) {
    // Iterate in reverse as we do not need the last element
    for (let i = A.length - 1; i > k; i--) {
        A[i] = A[i - 1];
    }
}

function main() {
    const N = 6;
    let A = [1000, 1400, 2000, 2000, 2200, 2700];
    const B = [800, 1200, 1500, 1800, 2200, 3000];
    let ans = 0; // This will keep count of shifts made

    for (let i = 0; i < N; i++) {
        if (A[i] > B[i]) {
            // Shift array A starting from index i
            shift(A, i);

            // Increase count
            ans++;

            // Update A[i]
            A[i] = B[i];
        }
    }
    console.log(ans);
}

main();

Output

Time Complexity: O(N²)
Auxiliary Space: O(1)

Minimize the shift required to make arr1[i] <= arr2[i]

Contact Us