Pattern Guide
Array Manipulation Tricks
"Rotate with 3 reverses. Mark visited in-place. Rearrange with index encoding."
Array manipulation problems often require O(1) extra space. Key tricks: rotate k positions with 3 reverses, mark visited by negating values, rearrange using index encoding (val-1 → index), cyclic sort for 1..n arrays. These patterns appear constantly but easy to miss.
Problems you can solve with this pattern
6 problems · click any to start solving
// TRICK 1: ROTATE ARRAY k positions (right) using 3 reverses
function rotate(nums, k) {
k = k % nums.length;
const rev = (lo, hi) => { while(lo<hi) [nums[lo++],nums[hi--]]=[nums[hi],nums[lo-1]]; };
rev(0, nums.length-1); // reverse all
rev(0, k-1); // reverse first k
rev(k, nums.length-1); // reverse remaining
}
// Why it works: [1,2,3,4,5], k=2
// reverse all: [5,4,3,2,1]
// reverse 0..k-1: [4,5,3,2,1]
// reverse k..n-1: [4,5,1,2,3] ✓
// TRICK 2: MARK VISITED by negating (array values 1..n)
// Visit index i → nums[nums[i]-1] = -|nums[nums[i]-1]|
// Check if value v is visited: nums[v-1] < 0
function findDuplicates(nums) {
const result = [];
for (const n of nums) {
const idx = Math.abs(n) - 1;
if (nums[idx] < 0) result.push(Math.abs(n)); // visited twice = duplicate
else nums[idx] = -nums[idx]; // mark visited
}
return result;
}
// TRICK 3: CYCLIC SORT (array with values 1..n)
// Place each number at index (value-1) by swapping
function cyclicSort(nums) {
let i = 0;
while (i < nums.length) {
const j = nums[i] - 1; // correct index for nums[i]
if (nums[i] !== nums[j]) [nums[i], nums[j]] = [nums[j], nums[i]]; // swap to correct pos
else i++; // already in place, move on
}
}
// After cyclic sort: nums[i] = i+1 iff no duplicate/missingArray in-place manipulation problems have a deceptive pattern: the O(n) extra space solution is obvious, but the O(1) space version requires a non-trivial trick. Learn the three canonical tricks — 3-reversal rotation, negation marking, and index encoding — and you'll be able to solve a whole class of problems that seem impossible at O(1) space.
The Three Canonical Tricks
// TRICK 1: ROTATE ARRAY k positions (right) using 3 reverses
function rotate(nums, k) {
k = k % nums.length;
const rev = (lo, hi) => { while(lo<hi) [nums[lo++],nums[hi--]]=[nums[hi],nums[lo-1]]; };
rev(0, nums.length-1); // reverse all
rev(0, k-1); // reverse first k
rev(k, nums.length-1); // reverse remaining
}
// Why it works: [1,2,3,4,5], k=2
// reverse all: [5,4,3,2,1]
// reverse 0..k-1: [4,5,3,2,1]
// reverse k..n-1: [4,5,1,2,3] ✓
// TRICK 2: MARK VISITED by negating (array values 1..n)
// Visit index i → nums[nums[i]-1] = -|nums[nums[i]-1]|
// Check if value v is visited: nums[v-1] < 0
function findDuplicates(nums) {
const result = [];
for (const n of nums) {
const idx = Math.abs(n) - 1;
if (nums[idx] < 0) result.push(Math.abs(n)); // visited twice = duplicate
else nums[idx] = -nums[idx]; // mark visited
}
return result;
}
// TRICK 3: CYCLIC SORT (array with values 1..n)
// Place each number at index (value-1) by swapping
function cyclicSort(nums) {
let i = 0;
while (i < nums.length) {
const j = nums[i] - 1; // correct index for nums[i]
if (nums[i] !== nums[j]) [nums[i], nums[j]] = [nums[j], nums[i]]; // swap to correct pos
else i++; // already in place, move on
}
}
// After cyclic sort: nums[i] = i+1 iff no duplicate/missing- "Rotate k positions in O(1) space" → 3 reverses
- "Mark visited without extra space (values 1..n)" → negate at index value-1
- "Place each value at correct index (1..n)" → cyclic sort
- "Find missing/duplicate in 1..n array" → cyclic sort, then scan for mismatch
- "Next permutation" → find rightmost dip, swap with just-larger, reverse suffix
- "Rearrange by condition" → two pointers with step 2 for alternating pattern