Swaps to Convert Array
Filed under Oracle
Free read 1 of 3Understand if elements are unique and what type of swaps are allowed (adjacent vs arbitrary).
The question
Given two arrays of integers, arr1 and arr2, of the same size containing a permutation of the same elements, find the minimum number of adjacent swaps required to convert arr1 into arr2.
Constraints
- 1 <= arr1.length <= 1000
- arr1 and arr2 are permutations of each other.
Examples
- Input
- arr1 = [3, 1, 2], arr2 = [1, 3, 2]
- Output
- 1
- Why
- Swap 3 and 1 in arr1 to get [1, 3, 2].
Approach
Understand if elements are unique and what type of swaps are allowed (adjacent vs arbitrary).
Simulate all adjacent swaps using BFS or Dijkstra to find the shortest path of transformations.
Map each value in arr1 to its indices in arr2. The problem reduces to finding the number of inversions in the mapped array, which can be solved using a Fenwick tree (Binary Indexed Tree) or Merge Sort in O(N log N) time.
Arrays are already identical (0 swaps), single element arrays.
Tips
- What they are testing: Test with arrays already equal, reverse arrays, and arrays requiring maximum inversions.
- Common mistake: Assuming standard sorting techniques work directly without mapping elements from arr1 to their target indices in arr2.
Related Oracle questions
Collected from public candidate posts and coding forums. Updated Nov 2026.