Array Rotation Alignment — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Array Rotation Alignment problem optimally.
O(n)O(1)Problem Description
Given two integer arrays sequenceA and sequenceB of equal length, determine whether sequenceB can be turned into sequenceA by repeatedly applying a single‑step left circular rotation (moving the first element to the end). If it is possible, output the smallest number of such rotations required; otherwise output -1. The algorithm must run in O(n) time and O(1) additional space beyond the input arrays.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Array Rotation Alignment"
WHY DOES IT MATTER?
Detecting cyclic equivalence appears in version control diffing, circular buffer management, and cryptographic key rotations, making it a reusable pattern for many engineering problems.
OPTIMIZATION CHALLENGE
The insight is to avoid explicit rotation simulation; by viewing the problem as substring search in a doubled sequence, we collapse O(n^2) work into a single linear pass.
REAL-WORLD CONNECTION
Think of a conveyor belt with items; rotating the belt twice brings the third item to the front—checking if two belt configurations match after some rotations mirrors this array problem.
When coding, first verify lengths, then use a two‑pointer or KMP scan on the virtual doubled array—no need to allocate a new array, just modulo the index during comparison.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem reduces to checking whether one array is a cyclic shift of another. A naive O(n^2) scan compares each possible rotation by shifting elements, which quickly becomes prohibitive for large n because each rotation requires O(n) work. The optimal O(n) solution treats the arrays as strings and uses the classic "string in string" trick: concatenate sequenceB with itself and then search for sequenceA as a contiguous sub‑array using a linear‑time pattern matcher such as KMP or the built‑in index‑of for primitive types. The first occurrence index directly yields the minimal left‑rotation count, while the absence of a match means the arrays are not rotations of each other.
Interview Questions on This Problem
Q1How would you determine if two arrays are rotations of each other without using extra space?
Concatenate the second array with itself (conceptually) and then scan for the first array using a linear‑time algorithm like KMP; the match index gives the rotation count, and no extra array storage is needed beyond a few pointers.
Q2Why does the "double array" technique work for rotation detection?
A left rotation moves the prefix of the original array to the end; by appending the array to itself, every possible rotation appears as a contiguous sub‑segment, so searching for the target sequence inside this doubled sequence captures all rotations.
Q3What edge cases must you handle when implementing rotation alignment for arrays that may contain duplicate values?
Duplicates can cause multiple matching positions; you must return the smallest index (minimum rotations) and ensure the algorithm correctly distinguishes overlapping matches, which KMP handles naturally.
Examples
Input
{"sequenceA":[1,2,3,4],"sequenceB":[3,4,1,2]}Output
2
Explanation: Applying a left rotation to sequenceB once yields [4,1,2,3]; a second rotation yields [1,2,3,4], which matches sequenceA. No fewer rotations achieve the target, so the answer is 2.
Input
{"sequenceA":[5,6,7],"sequenceB":[5,6,7]}Output
0
Explanation: sequenceB already equals sequenceA, so zero rotations are needed.
Input
{"sequenceA":[10,20,30,40],"sequenceB":[20,30,40,10]}Output
3
Explanation: Rotating sequenceB left once gives [30,40,10,20]; twice gives [40,10,20,30]; three times gives [10,20,30,40], which matches sequenceA. Hence the minimum rotations are 3.
Input
{"sequenceA":[1,2,3],"sequenceB":[1,3,2]}Output
-1
Explanation: No amount of left circular rotations can reorder sequenceB into [1,2,3]; the relative order of 2 and 3 cannot be achieved, so the answer is -1.
Constraints
- 1 <= sequenceA.length == sequenceB.length <= 100000
- -10^9 <= sequenceA[i], sequenceB[i] <= 10^9
- Both arrays contain integers and may include duplicates
Optimal Approach & Strategy
Conceptually double B, then run a linear‑time pattern search (e.g., KMP) for A; the first match index is the answer, achieving O(n) time and O(1) extra space.
Brute Force Approach
Try every possible rotation by physically shifting the array and compare with A each time, which costs O(n) work per rotation leading to O(n^2) total time.
Code Solutions
function buildLPS(pattern) {
const m = pattern.length;
const lps = new Array(m).fill(0);
let len = 0;
for (let i = 1; i < m; ) {
if (pattern[i] === pattern[len]) {
lps[i++] = ++len;
} else if (len) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}
function minRotations(sequenceA, sequenceB) {
const n = sequenceA.length;
if (n !== sequenceB.length) return -1;
if (n === 0) return 0;
const text = new Array(2 * n);
for (let i = 0; i < 2 * n; ++i) text[i] = sequenceB[i % n];
const lps = buildLPS(sequenceA);
let i = 0, j = 0;
while (i < 2 * n) {
if (text[i] === sequenceA[j]) {
++i; ++j;
if (j === n) {
const start = i - j;
if (start < n) return start;
j = lps[j - 1];
}
} else if (j) {
j = lps[j - 1];
} else {
++i;
}
}
return -1;
}
module.exports = { minRotations };#include <bits/stdc++.h>
using namespace std;
// KMP helper to build longest prefix suffix array
static vector<int> buildLPS(const vector<int>& pat) {
int m = pat.size();
vector<int> lps(m,0);
for(int i=1,len=0;i<m;){
if(pat[i]==pat[len]) lps[i++]=++len;
else if(len) len=lps[len-1];
else lps[i++]=0;
}
return lps;
}
int minRotations(const vector<int>& A, const vector<int>& B) {
int n = A.size();
if(n!= (int)B.size()) return -1;
if(n==0) return 0;
// Concatenate B with itself
vector<int> text(2*n);
for(int i=0;i<2*n;++i) text[i]=B[i%n];
// KMP search for pattern A in text
vector<int> lps = buildLPS(A);
int i=0,j=0; // i over text, j over pattern
while(i<2*n){
if(text[i]==A[j]){ ++i; ++j; if(j==n){ int start = i-j; if(start < n) return start; j = lps[j-1]; } }
else if(j) j = lps[j-1];
else ++i;
}
return -1;
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);
int n; if(!(cin>>n)) return 0; vector<int>A(n),B(n);
for(int &x:A)cin>>x; for(int &x:B)cin>>x;
cout<<minRotations(A,B);
return 0;}
import java.util.*;
public class Solution {
private static int[] buildLPS(int[] pattern) {
int m = pattern.length;
int[] lps = new int[m];
int len = 0, i = 1;
while (i < m) {
if (pattern[i] == pattern[len]) {
lps[i++] = ++len;
} else if (len != 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}
public static int minRotations(int[] sequenceA, int[] sequenceB) {
int n = sequenceA.length;
if (n != sequenceB.length) return -1;
if (n == 0) return 0;
int[] text = new int[2 * n];
for (int i = 0; i < 2 * n; ++i) text[i] = sequenceB[i % n];
int[] lps = buildLPS(sequenceA);
int i = 0, j = 0;
while (i < 2 * n) {
if (text[i] == sequenceA[j]) {
i++; j++;
if (j == n) {
int start = i - j;
if (start < n) return start;
j = lps[j - 1];
}
} else if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
}
}
def build_lps(pattern):
m = len(pattern)
lps = [0] * m
length = 0
i = 1
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
def min_rotations(sequence_a, sequence_b):
n = len(sequence_a)
if n != len(sequence_b):
return -1
if n == 0:
return 0
text = sequence_b * 2
lps = build_lps(sequence_a)
i = j = 0
while i < 2 * n:
if text[i] == sequence_a[j]:
i += 1
j += 1
if j == n:
start = i - j
if start < n:
return start
j = lps[j - 1]
elif j:
j = lps[j - 1]
else:
i += 1
return -1
function buildLPS(pattern) {
const m = pattern.length;
const lps = new Array(m).fill(0);
let len = 0;
for (let i = 1; i < m; ) {
if (pattern[i] === pattern[len]) {
lps[i++] = ++len;
} else if (len) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}
function minRotations(sequenceA, sequenceB) {
const n = sequenceA.length;
if (n !== sequenceB.length) return -1;
if (n === 0) return 0;
const text = new Array(2 * n);
for (let i = 0; i < 2 * n; ++i) text[i] = sequenceB[i % n];
const lps = buildLPS(sequenceA);
let i = 0, j = 0;
while (i < 2 * n) {
if (text[i] === sequenceA[j]) {
++i; ++j;
if (j === n) {
const start = i - j;
if (start < n) return start;
j = lps[j - 1];
}
} else if (j) {
j = lps[j - 1];
} else {
++i;
}
}
return -1;
}
module.exports = { minRotations };
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.