Pattern Guide
Array Rotation & Circular Problems
"Rotate by k, search in rotated array, circular queue/buffer problems."
Array rotation problems work with shifted or circular arrays. Key insight: rotating right by k is equivalent to reversing the full array, then reversing [0..k-1] and [k..n-1] (three-reversal trick). Search in rotated sorted array: binary search with one side always sorted. Circular problems (max sum subarray in circular array) require handling wrap-around: answer is either normal max subarray or total sum minus min subarray.
Problems you can solve with this pattern
4 problems · click any to start solving
// Rotate array right by k — three reversals
function rotate(nums, k) {
const n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
function reverse(arr, l, r) {
while (l < r) { [arr[l], arr[r]] = [arr[r], arr[l]]; l++; r--; }
}
// Maximum sum circular subarray
function maxSubarraySumCircular(nums) {
let maxSum = nums[0], curMax = 0;
let minSum = nums[0], curMin = 0;
let total = 0;
for (const n of nums) {
curMax = Math.max(curMax + n, n);
maxSum = Math.max(maxSum, curMax);
curMin = Math.min(curMin + n, n);
minSum = Math.min(minSum, curMin);
total += n;
}
// If maxSum < 0, all negative — return maxSum
return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
}Rotate array by k: three reversals. Reverse all → reverse [0..k-1] → reverse [k..n-1]. O(n) time, O(1) space. Search in rotated array: one half is always sorted. If nums[l] <= nums[mid], left half sorted; check if target in [nums[l], nums[mid]], else go right. Circular max subarray: max(max_subarray, total - min_subarray). Edge case: all negative means min_subarray = full array.
// Rotate array right by k — three reversals
function rotate(nums, k) {
const n = nums.length;
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
}
function reverse(arr, l, r) {
while (l < r) { [arr[l], arr[r]] = [arr[r], arr[l]]; l++; r--; }
}
// Maximum sum circular subarray
function maxSubarraySumCircular(nums) {
let maxSum = nums[0], curMax = 0;
let minSum = nums[0], curMin = 0;
let total = 0;
for (const n of nums) {
curMax = Math.max(curMax + n, n);
maxSum = Math.max(maxSum, curMax);
curMin = Math.min(curMin + n, n);
minSum = Math.min(minSum, curMin);
total += n;
}
// If maxSum < 0, all negative — return maxSum
return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
}Rotated sorted array binary search: Always ask "which half is sorted?" The sorted half can be checked with a simple range test; if target not there, it must be in the other half.
Circular subarray wrap: Wrapping subarray = total - middle subarray. To maximize wrapping sum, minimize the middle. Two Kadane passes: one for max (forward), one for min.