Replace array elements in given range from another array elements

Given an array A[] and size of array is N. The task is to replace element of array A[] are in given range L to R both are included. Element replace by one another Array B[] size of N.

Examples:

Input : N = 8
        A[] = { 3, 5, 3, 4, 9, 3, 1, 6 }
        B[] = { 5, 2, 7, 0, 1, 6, 4, 10 }
        L = 2
        R = 7
Output : 3 5 7 0 1 6 4 10
Since A[2] = 3 but this is replace by B[2] = 7
A[3] = 4 replace by B[3] = 0, A[4] = 9 replace by B[4] = 1,
A[5] = 3 replace by B[5] = 6,A[6] = 1 replace by B[6] = 4  
A[7] =  6 replace by B[7] = 10 

Input : N = 10
        A[] ={ 5, 8, 11, 15, 26, 14, 19, 17, 10, 14 }
        B[] = { 8, 6, 9, 2, 4, 6, 41, 32, 45, 78}
        L = 4
        R = 6
Output :5 8 11 15 4 6 41 17 10 14

Naive Approach:

A naive approach is to replace element in range L to R with extra space. Below is the implementation of the above approach.

Implementation in C++:

// C++ code to replace elements in a given range
#include <bits/stdc++.h>
using namespace std;

// Replace elements from L to R in A with elements from B
vector<int> replaceElements(int A[], int B[], int L, int R, int N) {
    vector<int> C;
    
    for (int i = 0; i < L; i++)
        C.push_back(A[i]);
    
    for (int i = L; i <= R; i++)
        C.push_back(B[i]);
    
    for (int i = R + 1; i < N; i++)
        C.push_back(A[i]);
    
    return C;
}

// Main Driver
int main() {
    int A[] = {5, 8, 11, 15, 26, 14, 19, 17, 10, 14};
    int B[] = {8, 6, 9, 2, 4, 6, 41, 32, 45, 78};
    int L = 4, R = 6;
    int N = sizeof(A) / sizeof(A[0]);
    vector<int> res = replaceElements(A, B, L, R, N);
    
    for (auto x : res)
        cout << x << " ";
    
    return 0;
}

Output :

5 8 11 15 4 6 41 17 10 14

Time Complexity : O(n)
Auxiliary Space : O(n)

Efficient Approach :

An efficient solution without using extra space. Below is the implementation of the above approach.

Implementation in C++:

// C++ code to replace elements in a given range
#include <bits/stdc++.h>
using namespace std;

int A[] = {5, 8, 11, 15, 26, 14, 19, 17, 10, 14};

// Replace elements from L to R in A with elements from B
void replaceElement(int B[], int L, int R, int N) {
    int j = 0;
    for (int i = L; i <= R; i++) {
        A[i] = B[j];
        j++;
    }
}

// Print array
void printArray(int N) {
    for (int i = 0; i < N; i++)
        cout << A[i] << " ";
    cout << endl;
}

// main Driver
int main() {
    int B[] = {8, 6, 9, 2, 4, 6, 41, 32, 45, 78};
    int L = 4, R = 6;
    int N = sizeof(A) / sizeof(A[0]);
    replaceElement(B, L, R, N);
    printArray(N);
    return 0;
}

5 8 11 15 4 6 41 17 10 14

Time Complexity: O(n)
Auxiliary Space : O(1)