Array Rotation Alignment ā Problem Statement & Solution Guide
Problem Description
Given two arrays of integers sequenceA and sequenceB, determine if sequenceB can be transformed into sequenceA by applying a series of rotations. If possible, find the minimum number of rotations required.
Examples
Input
[1, 2, 3, 4, 5, 6, 7] and [7, 1, 2, 3, 4, 5, 6]
Output
{"identical": false, "rotations": 6}Explanation: Step-by-step: Rotate sequenceB to the left by 6 positions to get sequenceA. This is the minimum number of rotations required.
Input
[1, 2, 3, 4, 5, 6, 7] and [3, 4, 5, 6, 7, 1, 2]
Output
{"identical": false, "rotations": -1}Explanation: Step-by-step: No valid rotation exists to transform sequenceB into sequenceA.
Constraints
- The sequences will have a length between 2 and 100 elements.
- All elements in the sequences are integers between 1 and 1000.
Optimal Approach & Strategy
The optimal approach involves using the fact that if two sequences can be made identical by rotation, then one must be a rotation of the other. We can check this by concatenating one sequence with itself and checking if the other sequence is a substring of the concatenated sequence.
Brute Force Approach
The brute-force approach involves trying all possible rotations of one sequence and checking if it matches the other sequence. This can be done using nested loops to generate all rotations and compare them. However, this approach has a time complexity of O(nĀ²).
Verified Code Solutions
function arrayRotationAlignment(sequenceA, sequenceB) {
if (sequenceA.length !== sequenceB.length) return { identical: false, rotations: -1 };
let rotations = 0;
for (let i = 0; i < sequenceA.length; i++) {
if (sequenceA[i] !== sequenceB[(i - rotations + sequenceA.length) % sequenceA.length]) {
rotations = -1;
break;
}
}
return { identical: true, rotations: rotations === -1 ? -1 : rotations % sequenceA.length === 0 ? 0 : 1 };
}class Solution {
public int[] arrayRotationAlignment(int[] sequenceA, int[] sequenceB) {
if (sequenceA.length != sequenceB.length) {
return new int[]{-1, 0};
}
for (int i = 0; i < sequenceA.length; i++) {
if (isRotation(sequenceA, sequenceB, i)) {
return new int[]{1, i};
}
}
for (int i = 0; i < sequenceA.length; i++) {
if (isRotation(sequenceA, sequenceB, -i)) {
return new int[]{1, -i};
}
}
return new int[]{-1, 0};
}
private boolean isRotation(int[] sequenceA, int[] sequenceB, int rotations) {
int n = sequenceA.length;
int[] rotatedSequenceB = new int[n];
if (rotations >= 0) {
System.arraycopy(sequenceB, rotations, rotatedSequenceB, 0, n - rotations);
System.arraycopy(sequenceB, 0, rotatedSequenceB, n - rotations, rotations);
} else {
rotations = -rotations;
System.arraycopy(sequenceB, 0, rotatedSequenceB, 0, rotations);
System.arraycopy(sequenceB, rotations, rotatedSequenceB, rotations, n - rotations);
}
return Arrays.equals(sequenceA, rotatedSequenceB);
}
}def array_rotation_alignment(sequenceA, sequenceB):
if len(sequenceA) != len(sequenceB):
return {'identical': False, 'rotations': -1}
for i in range(len(sequenceA)):
if sequenceA == sequenceB[i:]+sequenceB[:i]:
return {'identical': True, 'rotations': i}
for i in range(len(sequenceA)):
if sequenceA == sequenceB[-i:]+sequenceB[:-i]:
return {'identical': True, 'rotations': -i}
return {'identical': False, 'rotations': -1}function arrayRotationAlignment(sequenceA, sequenceB) {
if (sequenceA.length !== sequenceB.length) return { identical: false, rotations: -1 };
let rotations = 0;
for (let i = 0; i < sequenceA.length; i++) {
if (sequenceA[i] !== sequenceB[(i - rotations + sequenceA.length) % sequenceA.length]) {
rotations = -1;
break;
}
}
return { identical: true, rotations: rotations === -1 ? -1 : rotations % sequenceA.length === 0 ? 0 : 1 };
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.