mediumStringsPattern: Mixed
Minimum Transpositions to Palindrome Solution
Problem Statement
Given an array of integers `arr`, determine the minimum number of transposition operations required to transform it into a palindrome array. A transposition operation involves swapping two adjacent elements in the array.
Examples
Example 1:
Input:[1, 3, 2, 1]
Output:1
Explanation: Swap 3 and 2 to get the palindrome [1, 2, 3, 1] requires only 1 transposition.
Example 2:
Input:[1, 2, 3, 4, 5]
Output:2
Explanation: Transforming [1, 2, 3, 4, 5] to a palindrome [1, 5, 4, 3, 2] requires at least two transpositions.
Constraints
- 1 <= arr.length <= 1000
- -1000 <= arr[i] <= 1000
- arr contains distinct integers
- The transposition operation only swaps adjacent elements
- The input array may or may not be a palindrome initially
Time: O(n^2) Space: O(1)
An optimized approach involves using a two-pointer technique to compare elements from the start and end of the array, working inwards and counting the number of transpositions needed to make the array a palindrome. This approach has a time complexity of O(n^2) and is more efficient than the brute force method. It also requires O(1) space.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
input = sys.stdin.readline
arr = list(map(int, input().split()))
n = len(arr)
ans = 0
for i in range(n // 2):
minIndex = i
for j in range(i, n - i):
if arr[j] < arr[minIndex]:
minIndex = j
for j in range(minIndex, i, -1):
arr[j], arr[j - 1] = arr[j - 1], arr[j]
ans += 1
maxIndex = i
for j in range(i, n - i):
if arr[j] > arr[maxIndex]:
maxIndex = j
for j in range(maxIndex, n - i - 1):
arr[j], arr[j + 1] = arr[j + 1], arr[j]
ans += 1
print(ans)