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)