Reorder Array using Given Indexes in Java
Reorder Array Using Given Indexes in Java Programming
On this page we will discuss about reorder array using given indexes . Given two input arrays of same size, second array is index array, we need to reorder array using given indexes array.
Here, on this page we have discussed both methods to Reorder Array using given indexes with Java Programming Language along with algorithms explanation and code examples.
Reorder Array Using Given Indexes in Java language
Reorder Array Using Given Indexes
- In computer science, reordering an array using given indexes is a common problem.
- Given an array of values and an array of indexes, the task is to reorder the values in the array based on the given indexes.
- Basic idea behind this problem is to create a temporary array to hold the sorted values and then copy the sorted values back into the original array in the correct order.
It is particularly useful in scenarios such as data shuffling, memory optimization, or simulating positional mappings.
Example Problem Statement
You are given:
- An array arr[] of length n.
- An integer array index[] of the same length.
- The task is to reorder the elements of arr[] such that each element moves to the position specified by index[].
Constraints:
- arr.length == index.length.
- index[i] must contain all unique integers from 0 to n-1.
where n is the size of the array, as we loop through the array and index array only once.
To do this, we first declare the 2 arrays:
- Array containing the values to be sorted, and the array containing the indexes that specify the order in which the values should be sorted.
- Next, we create a temporary array to hold the sorted values. We then loop through the index array and assign the values from the original array to the temporary array in the correct order specified by the index array.
- Finally, we copy the values from the temporary array back into the original array, effectively reordering the array according to the specified indexes.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Real World Application….
Imagine a deck of cards (arr[]) and a plan showing where each card should be placed on a table (index[]).
You are asked to place each card at the position specified in the plan.
Approach 1: Using Extra Array
Create a new array and place each element from arr[] into the new array at the index specified by index[].
Time Complexity: O(n)
Algorithm :
- Take the size of the array from the user and store it in variable n.
- Declare two arrays arr[] and idx[], one for array elements and another to store the require indexes value.
- Take the elements of the both arrays from the user.
- Declare an another array for the output say, res[].
- Traverse the result array and set, res[idx[i]]=arr[].
Code: For Given Indexes
import java.util.Arrays; public class ReorderArrayWithIndex { public static T[] reorder(T[] arr, int[] index) { T[] result = Arrays.copyOf(arr, arr.length); for (int i = 0; i < arr.length; i++) { result[index[i]] = arr[i]; } return result; } public static void main(String[] args) { String[] arr = {"a", "b", "c", "d"}; int[] index = {2, 0, 1, 3}; String[] result = reorder(arr, index); System.out.println("Reordered Array: " + Arrays.toString(result)); } }
Output:
Reordered Array: [b, c, a, d]
Approach 2: In Place Reordering using Cyclic Replacement
- Avoid using extra space by performing in place swaps based on the positions defined in the index array.
- This transforms the index array into a permutation and repositions elements accordingly.
Algorithm:
Loop through each element.
While the current element is not at its correct position:
- Swap the current element with the one at its target index
- Also swap the corresponding indices in the index array.
Time Complexity: O(n2)
Code For Cyclic Replacement
import java.util.Arrays; public class ReorderArrayInPlace { public static void reorderInPlace(T[] arr, int[] index) { for (int i = 0; i < arr.length; i++) { while (index[i] != i) { int targetIndex = index[i]; // Swap elements in arr T tempVal = arr[i]; arr[i] = arr[targetIndex]; arr[targetIndex] = tempVal; // Swap corresponding indices int tempIndex = index[i]; index[i] = index[targetIndex]; index[targetIndex] = tempIndex; } } } public static void main(String[] args) { String[] arr = {"a", "b", "c", "d"}; int[] index = {2, 0, 1, 3}; reorderInPlace(arr, index); System.out.println("In-Place Reordered Array: " + Arrays.toString(arr)); } }
Output:
In Place Reordered Array: [b, c, a, d]
Applications:
- Rearranging data based on position
- Shuffling arrays using permutation rules
- Reordering input for simulations or modeling
- Sorting based on custom index mapping
- Memory layout transformations
Summary:
Reordering an array using a given index array is a fundamental algorithmic task.
The extra array method is simple and efficient, while the in place method is space saving and useful in constrained environments.
Understanding both approaches strengthens your grasp of indexing, permutation handling, and time space optimization in Java.
FAQ's related to Reorder Array
Answer:
The most efficient way is the two pointer approach, which works in linear time (O(n)) and uses constant space (O(1)).
It swaps misplaced 0’s and 1’s in place.
Answer:
Yes, the in place two pointer method does not require any additional memory and directly modifies the original array.
Answer:
No, these methods are not stable. The relative order of 0’s and 1’s may change. If stability is required, you need to use a modified approach.
Answer:
Both the counting method and the two pointer method run in O(n) time, where n is the size of the array.
Answer:
The Dutch National Flag problem involves segregating 0’s, 1’s, and 2’s, while this problem deals with only 0’s and 1’s.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal Line by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric – C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree- C | C++ | Java
Introduction to Trees
Binary Trees
- Binary Tree in Data Structures (Introduction)
- Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
- Inorder Postorder PreOrder Traversals Examples
- Tree Traversal without Recursion
Binary Search Trees
Traversals
- Traversal in Trees
- Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
- Tree Traversals: Depth First Search (DFS) : C | C++ | Java
- Construct a Binary Tree from Postorder and Inorder
B – Trees
AVL Trees
- AVL Trees
Complete Programs for Trees
- Depth First Traversals – C | C++ | Java
- Level Order Traversal – C | C++ | Java
- Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
- Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
- Find size of the Binary tree – C | C++ | Java
- Find the height of binary tree – C | C++ | Java
- Find maximum in binary tree – C | C++ | Java
- Check whether two tree are identical- C| C++| Java
- Spiral Order traversal of Tree- C | C++| Java
- Level Order Traversal LIne by Line – C | C++| Java
- Hand shaking lemma and some Impotant Tree Properties.
- Check If binary tree if Foldable or not.- C| C++| Java
- check whether tree is Symmetric C| C++| Java.
- Check for Children-Sum in Binary Tree- C|C++| Java
- Sum of all nodes in Binary Tree- C | C++ | Java
- Lowest Common Ancestor in Binary Tree. C | C++ | Java
Login/Signup to comment