Galactic Vessel Alignment — Problem Statement & Solution Guide
Problem Description
Given two integer arrays A and B of the same length, determine whether B can be transformed into A by performing a series of cyclic right rotations. A single right rotation moves the last element of the array to the front, shifting all other elements one position to the right. If such a transformation is possible, output the minimum number of right rotations required; otherwise output -1. The input consists of an integer n (the length of the arrays), followed by a line with n space‑separated integers representing A, and a line with n space‑separated integers representing B. The output is a single integer as described.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Galactic Vessel Alignment"
WHY DOES IT MATTER?
Detecting cyclic equivalence appears in string matching, networking packet reassembly, and circular buffer management; mastering the B+B pattern equips engineers to solve a broad class of rotation‑related problems efficiently.
OPTIMIZATION CHALLENGE
The key insight is that all rotations of B are linearly represented in B+B, turning a combinatorial search into a single linear substring search, thereby collapsing O(n^2) possibilities into O(n) work.
REAL-WORLD CONNECTION
Consider a distributed log that is replicated in a ring topology; verifying that two replicas contain the same sequence of events despite different starting points is exactly a rotation check, analogous to matching B+B against A.
In an interview, first state the B+B observation, then immediately mention KMP (or built‑in index) to achieve linear time; avoid writing nested loops that hint at quadratic complexity.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The problem reduces to checking whether one array is a cyclic rotation of another. A naive element‑by‑element comparison for each possible shift leads to O(n^2) time, which quickly becomes infeasible for large n (e.g., n≈10^5). The optimal paradigm treats the rotation check as a substring search: by concatenating array B with itself (B+B) we embed every possible rotation of B as a contiguous sub‑array of length n. The task then becomes finding A as a sub‑array inside B+B, which can be solved in linear time using a string‑matching algorithm such as Knuth‑Morris‑Pratt (KMP) or Rabin‑Karp. Once the starting index i of the match is known, the required right rotations are (n‑i) mod n, giving the minimal count because any further full cycles would repeat the same configuration. This approach guarantees O(n) time and O(n) auxiliary space for the failure function, dramatically improving over the quadratic brute force.
Interview Questions on This Problem
Q1How would you determine if array B can be transformed into A using only cyclic right rotations, and compute the minimal number of rotations?
Concatenate B with itself to form C = B+B. Use KMP to search for A as a sub‑array of C within the first n positions. If found at index i, the minimal right rotations = (n‑i)%n; otherwise return -1.
Q2Why is the "B+B" trick valid for rotation detection, and does it work for both left and right rotations?
Because rotating B left by i positions yields the sub‑array C[i..i+n‑1] in B+B. A right rotation by k is equivalent to a left rotation by n‑k, so the same trick captures both directions; the index i gives the left shift, from which the right shift is derived.
Q3What are the time and space complexities of using KMP for this problem compared to using a hash‑based rolling checksum like Rabin‑Karp?
Both KMP and Rabin‑Karp run in O(n) expected time; KMP guarantees O(n) worst‑case time with O(n) extra space for the prefix table, while Rabin‑Karp uses O(1) extra space but may suffer collisions, leading to occasional O(n^2) worst‑case behavior.
Examples
Input
5 1 2 3 4 5 3 4 5 1 2
Output
2
Explanation: Rotating B right once yields [2,3,4,5,1]; rotating again yields [1,2,3,4,5] which matches A. No fewer rotations achieve equality, so the answer is 2.
Input
4 7 8 9 10 10 7 8 9
Output
1
Explanation: A single right rotation moves the last element 9 to the front, producing [9,10,7,8]; a second rotation gives [8,9,10,7]; a third gives [7,8,9,10] which equals A. The minimal number of rotations is 3, but rotating left once is equivalent to three right rotations. Since we count right rotations, the answer is 3.
Input
3 5 5 5 5 5 5
Output
0
Explanation: Both arrays are already identical; zero rotations are needed.
Constraints
- 1 <= n <= 100000
- -10^9 <= A[i], B[i] <= 10^9
- All elements are integers
Optimal Approach & Strategy
Concatenate B with itself and run a linear‑time substring search (KMP) to locate A, then compute rotations from the match index.
Brute Force Approach
Try every possible rotation (0 to n‑1) and compare the whole array each time, leading to O(n^2) time.
Verified Code Solutions
function buildLPS(pat){
const m=pat.length;
const lps=new Array(m).fill(0);
let len=0,i=1;
while(i<m){
if(pat[i]===pat[len]){len++; lps[i]=len; i++;}
else if(len) len=lps[len-1];
else {lps[i]=0; i++;}
}
return lps;
}
function minRotations(A,B){
const n=A.length;
if(n!==B.length) return -1;
if(n===0) return 0;
const text=new Array(2*n);
for(let i=0;i<2*n;i++) text[i]=B[i%n];
const lps=buildLPS(A);
let i=0,j=0;
while(i<2*n){
if(text[i]===A[j]){i++;j++; if(j===n){const pos=i-j; if(pos<n){return (n-pos)%n;} j=lps[j-1];}}
else if(j) j=lps[j-1];
else i++;
}
return -1;
}
const fs=require('fs');
const data=fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p=0; const n=data[p++]||0; const A=data.slice(p,p+n); p+=n; const B=data.slice(p,p+n);
console.log(minRotations(A,B).toString());#include <bits/stdc++.h>
using namespace std;
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;
// KMP search A in B+B
vector<int> text(2*n);
for(int i=0;i<2*n;i++) text[i]=B[i%n];
vector<int> lps=buildLPS(A);
int i=0,j=0;
while(i<2*n){
if(text[i]==A[j]){i++;j++; if(j==n){int pos=i-j; if(pos<n){int k=(n-pos)%n; return k;} 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.io.*;
import java.util.*;
public class Main {
private static int[] buildLPS(int[] pat){
int m=pat.length;
int[] lps=new int[m];
int len=0,i=1;
while(i<m){
if(pat[i]==pat[len]){len++; lps[i]=len; i++;}
else if(len!=0){len=lps[len-1];}
else{lps[i]=0; i++;}
}
return lps;
}
static int minRotations(int[] A, int[] B){
int n=A.length;
if(n!=B.length) return -1;
if(n==0) return 0;
int[] text=new int[2*n];
for(int i=0;i<2*n;i++) text[i]=B[i%n];
int[] lps=buildLPS(A);
int i=0,j=0;
while(i<2*n){
if(text[i]==A[j]){i++;j++; if(j==n){int pos=i-j; if(pos<n){return (n-pos)%n;} j=lps[j-1];}}
else if(j!=0) j=lps[j-1];
else i++;
}
return -1;
}
public static void main(String[] args) throws Exception {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String line=br.readLine();
if(line==null||line.isEmpty()) return;
int n=Integer.parseInt(line.trim());
int[] A=new int[n];
int[] B=new int[n];
StringTokenizer st=new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) A[i]=Integer.parseInt(st.nextToken());
st=new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) B[i]=Integer.parseInt(st.nextToken());
System.out.print(minRotations(A,B));
}
}
import sys
def build_lps(pat):
m=len(pat)
lps=[0]*m
length=0
i=1
while i<m:
if pat[i]==pat[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(A,B):
n=len(A)
if n!=len(B):
return -1
if n==0:
return 0
text=B+B
lps=build_lps(A)
i=j=0
while i<2*n:
if text[i]==A[j]:
i+=1; j+=1
if j==n:
pos=i-j
if pos<n:
return (n-pos)%n
j=lps[j-1]
elif j:
j=lps[j-1]
else:
i+=1
return -1
def main():
data=sys.stdin.read().strip().split()
if not data:
return
it=iter(data)
n=int(next(it))
A=[int(next(it)) for _ in range(n)]
B=[int(next(it)) for _ in range(n)]
print(min_rotations(A,B))
if __name__=="__main__":
main()
function buildLPS(pat){
const m=pat.length;
const lps=new Array(m).fill(0);
let len=0,i=1;
while(i<m){
if(pat[i]===pat[len]){len++; lps[i]=len; i++;}
else if(len) len=lps[len-1];
else {lps[i]=0; i++;}
}
return lps;
}
function minRotations(A,B){
const n=A.length;
if(n!==B.length) return -1;
if(n===0) return 0;
const text=new Array(2*n);
for(let i=0;i<2*n;i++) text[i]=B[i%n];
const lps=buildLPS(A);
let i=0,j=0;
while(i<2*n){
if(text[i]===A[j]){i++;j++; if(j===n){const pos=i-j; if(pos<n){return (n-pos)%n;} j=lps[j-1];}}
else if(j) j=lps[j-1];
else i++;
}
return -1;
}
const fs=require('fs');
const data=fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let p=0; const n=data[p++]||0; const A=data.slice(p,p+n); p+=n; const B=data.slice(p,p+n);
console.log(minRotations(A,B).toString());
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.