Given two integer arrays arr and index of size N, the task is to create a new array by inserting the elements given in the arr array at the indices given by the index array. If a particular position occur multiple time then right shift the right-side array elements and then insert element at given index.
Note: It is given that all the indices that in the index array lie in the range [0, N).
Examples:
Input: arr = [0, 1, 2, 3, 4], index = [0, 1, 2, 2, 1]
Output: [0, 4, 1, 3, 2]
Explanation:
First we insert at 0th, 1st and 2nd index so the array will become [0, 1, 2]
Then we insert again at 2nd position and rightshift all rightside elements so array will be [0, 1, 3, 2]
Then we insert 4 at first index so final array will become: [0, 4, 1, 3, 2].Input: arr = [1, 2, 3, 4, 0], index = [0, 1, 2, 3, 0]
Output: [0, 1, 2, 3, 4]
Approach (Using static array):
If we use a static array, then the given problem can be solved using the following steps:
- Create a new array finalArr of size N, to store the resultant output.
- For each element in the given arr array, insert it at the corresponding given index given by the index array, simply using:
finalArr[index[i]] = arr[i] where i is the current position during iteration
- If the index is repeated, then right shift all right-side element and then finally insert at that position.
Approach (Using dynamic array):
If we use a dynamic array-like structure, like Vectors, etc; then we can simply insert the given element at the given index, without worrying about the repetition. The vector-like data structure takes care of the right shifting by itself, when it expands at each insertion.
- Create a new vector vec, to store the resultant output.
- For each element in the given arr array, insert it at the corresponding given index given by the index array, simply using insert() function of vector. This will insert at a particular position, and take care of repeating positions automatically.
Below is the implementation of the above approach:
C++
// C++ program to reorder an Array// according to given indices// with repetition allowed#include <bits/stdc++.h>using namespace std;// Function that returns the// modified vector according to indicesvector<int> createTargetArray( vector<int>& nums, vector<int>& index){ // create an ans vector vector<int> ans; int n = nums.size(); for (int i = 0; i < n; i++) // insert at particular position // mention in index array. ans.insert(ans.begin() + index[i], nums[i]); // finally return ans return ans;}// Function to reorder and// print the given arrayvoid reorder( vector<int>& arr, vector<int>& index){ vector<int> ans; ans = createTargetArray(arr, index); // print ans vector for (int i = 0; i < ans.size(); i++) { cout << ans[i] << " "; }}// Driver Codeint main(){ vector<int> arr = { 0, 1, 2, 3, 4 }; vector<int> index = { 0, 1, 2, 2, 1 }; reorder(arr, index); return 0;} |
Java
// Java program to reorder an Array// according to given indices// with repetition allowedimport java.util.*;class GFG {// Function that returns the// modified List according to indicesstatic List<Integer> createTargetArray(List<Integer> nums, List<Integer> index){ // Create an ans List List<Integer> ans = new ArrayList<>(); int n = nums.size(); for(int i = 0; i < n; i++) { // Insert at particular position // mention in index array ans.add(index.get(i), nums.get(i)); } // Finally return ans return ans;}// Function to reorder and// print the given arraystatic void reorder(List<Integer> arr, List<Integer> index){ List<Integer> ans; ans = createTargetArray(arr, index); // Print ans list for(int i = 0; i < ans.size(); i++) { System.out.print(ans.get(i) + " "); }}// Driver codepublic static void main(String[] args){ List<Integer> arr = Arrays.asList(0, 1, 2, 3, 4); List<Integer> index = Arrays.asList(0, 1, 2, 2, 1); reorder(arr, index);}}// This code is contributed by offbeat |
Python3
# Python3 program to reorder an array# according to given indices# with repetition allowed# Function that returns the modified # vector according to indicesdef createTargetArray(nums, index): # Create an ans vector ans = [] n = len(nums) for i in range(n): # Insert at particular position # mention in index array. ans.insert(index[i], nums[i]) # Finally return ans return ans# Function to reorder and# print the given arraydef reorder(arr, index): ans = createTargetArray(arr, index) # Print ans vector for i in range(len(ans)): print(ans[i], end = " ")# Driver Codeif __name__ == "__main__": arr = [ 0, 1, 2, 3, 4 ] index = [ 0, 1, 2, 2, 1 ] reorder(arr, index)# This code is contributed by chitranayal |
C#
// C# program to reorder an Array// according to given indices// with repetition allowedusing System;using System.Collections.Generic;class GFG{// Function that returns the// modified List according to indicesstatic List<int> createTargetArray(List<int> nums, List<int> index){ // Create an ans List List<int> ans = new List<int>(); int n = nums.Count; for(int i = 0; i < n; i++) { // Insert at particular position // mention in index array ans.Insert(index[i], nums[i]); } // Finally return ans return ans;}// Function to reorder and// print the given arraystatic void reorder(List<int> arr, List<int> index){ List<int> ans; ans = createTargetArray(arr, index); // Print ans list for(int i = 0; i < ans.Count; i++) { Console.Write(ans[i] + " "); }}// Driver codepublic static void Main(){ List<int> arr = new List<int>{ 0, 1, 2, 3, 4 }; List<int> index = new List<int>{ 0, 1, 2, 2, 1 }; reorder(arr, index);}}// This code is contributed by akhilsaini |
Javascript
<script>// Javascript program to reorder an Array// according to given indices// with repetition allowed// Function that returns the// modified vector according to indicesfunction createTargetArray( nums, index){ // create an ans vector var ans = []; var n = nums.length; for (var i = 0; i < n; i++) // insert at particular position // mention in index array. ans.splice(index[i],0, nums[i]); // finally return ans return ans;}// Function to reorder and// print the given arrayfunction reorder( arr, index){ var ans = []; ans = createTargetArray(arr, index); // print ans vector for (var i = 0; i < ans.length; i++) { document.write( ans[i] + " "); }}// Driver Codevar arr = [0, 1, 2, 3, 4 ];var index = [0, 1, 2, 2, 1 ];reorder(arr, index);</script> |
0 4 1 3 2
Time complexity: O(N2), for performing insert operations in the loop.
Auxiliary space: O(N), for storing elements in the answer array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
