Master array traversal, in-place modification, prefix sums, and core array patterns.
Arrays are the first real data structure most people learn, and they appear in almost every interview round. The reason is simple: once you understand arrays well, you automatically unlock many core patterns like two pointers, sliding window, prefix sum, hashing, and in-place rearrangement. Most array problems are not about the array itself — they are about recognizing which pattern fits the problem. If a question asks you to find a pair, subarray, max/min over a range, or place elements in their correct positions, there is usually a standard array pattern behind it. The goal of this section is to help you not only know the patterns, but also understand when to use them and why they work.
Access O(1) · Search O(n) · Insert/Delete O(n) · Most optimized interview patterns on arrays run in O(n) or O(n log n)
O(n) for storing n elements · Many array problems can be solved in O(1) auxiliary space if in-place modification is allowed
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Use this when the array is sorted or when you want to reason from both ends at the same time
The left pointer starts from the beginning, the right pointer starts from the end, and based on the current sum or comparison you move one of them inward. This works because moving a pointer changes the answer in a predictable direction in sorted arrays. It is commonly used in pair-sum, container area, and duplicate-removal style problems.
Problem Container With Most Water. Start with one pointer at each end. Compute area = width × min(leftHeight, rightHeight). Update the best answer. Then move the pointer pointing to the shorter line, because the shorter line is the bottleneck and keeping it cannot improve the area.
function maxArea(height) {
let left = 0, right = height.length - 1, best = 0;
while (left < right) {
const area = (right - left) * Math.min(height[left], height[right]);
best = Math.max(best, area);
if (height[left] < height[right]) left++;
else right--;
}
return best;
}Use this when the problem asks about a contiguous subarray or substring and you want to avoid recomputing everything from scratch
Instead of checking every possible subarray, keep a moving window and update it incrementally as the right boundary expands. For fixed-size windows, add the new element and remove the old one. For variable-size windows, grow until invalid and then shrink from the left until valid again. This turns many O(n²) problems into O(n).
Problem Maximum sum of any subarray of size k. Keep a running sum of the current window. Add nums[i], and once the window grows beyond k, subtract nums[i-k].
function maxSumSubarray(nums, k) {
let windowSum = 0, maxSum = -Infinity;
for (let i = 0; i < nums.length; i++) {
windowSum += nums[i];
if (i >= k) windowSum -= nums[i - k];
if (i >= k - 1) maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}Use this when you need repeated range sums or need to count subarrays efficiently
The idea is to precompute cumulative totals so that any subarray sum can be answered in O(1). Prefix sum is especially useful when the brute force solution keeps summing the same elements repeatedly. It is also the base for advanced patterns like subarray sum equals k and 2D range sum queries.
Problem Subarray Sum Equals K. Track the running prefix sum and store how many times each prefix has occurred. If currentSum - k has been seen before, then a subarray ending here sums to k.
function subarraySum(nums, k) {
const freq = new Map([[0, 1]]);
let sum = 0, count = 0;
for (const num of nums) {
sum += num;
count += freq.get(sum - k) ?? 0;
freq.set(sum, (freq.get(sum) ?? 0) + 1);
}
return count;
}Use this when you need fast lookup while scanning the array once
A hash map lets you remember information about elements you have already seen, such as value → index or prefix sum → frequency. This is one of the most common ways to optimize an O(n²) brute-force approach into O(n). The key interview skill is identifying what information needs to be stored in the map.
Problem Two Sum. As you scan the array, compute the complement target - nums[i]. If it already exists in the map, you have found the pair. Otherwise store the current value and index.
function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (seen.has(complement)) return [seen.get(complement), i];
seen.set(nums[i], i);
}
return [];
}Use this when the question asks for the maximum sum contiguous subarray
The core idea is that if your current running sum becomes harmful, you should restart from the current element instead of carrying bad history forward. At each step, decide whether it is better to start fresh or extend the previous subarray. This is one of the cleanest examples of dynamic thinking inside arrays.
Problem Maximum Subarray. At index i, the best subarray ending at i is either nums[i] alone or nums[i] appended to the previous best ending subarray.
function maxSubArray(nums) {
let current = nums[0], best = nums[0];
for (let i = 1; i < nums.length; i++) {
current = Math.max(nums[i], current + nums[i]);
best = Math.max(best, current);
}
return best;
}Use this when numbers are supposed to lie in a known range like 1..n or 0..n, and the problem asks for a missing, duplicate, or misplaced element
Instead of sorting normally, place each value into the index where it belongs. After that, the mismatch directly reveals the answer. This is powerful because it gives O(n) time with O(1) extra space.
Problem First Missing Positive. Ignore invalid values, and for every valid value x place it at index x-1. After rearrangement, the first index i where nums[i] !== i+1 gives the missing positive.
function firstMissingPositive(nums) {
let i = 0;
while (i < nums.length) {
const correct = nums[i] - 1;
if (nums[i] > 0 && nums[i] <= nums.length && nums[i] !== nums[correct]) {
[nums[i], nums[correct]] = [nums[correct], nums[i]];
} else {
i++;
}
}
for (let i = 0; i < nums.length; i++)
if (nums[i] !== i + 1) return i + 1;
return nums.length + 1;
}Before applying any pattern, you must understand how arrays work at the memory level
An array stores elements in contiguous memory, which means random access by index is O(1) but insertion or deletion in the middle is O(n) because everything after must shift. Most interview problems start with an array and rely on you knowing: how to traverse it, how to use indices carefully to avoid off-by-one errors, how to reverse or rotate in-place, and when to use a second pointer or auxiliary structure. These fundamentals unlock every other pattern.
Problem Rotate array right by k steps. Reverse the full array, then reverse the first k elements, then reverse the rest. This uses no extra space and runs in O(n).
function rotate(nums, k) {
k = k % nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
function reverse(nums, left, right) {
while (left < right) {
[nums[left], nums[right]] = [nums[right], nums[left]];
left++; right--;
}
}Sorting is often the first move that unlocks the rest of a solution
Once an array is sorted, duplicates become adjacent, pairs become reachable from both ends, and binary search becomes applicable. The cost is O(n log n) upfront but it can reduce the main logic from O(n²) to O(n). The pattern is: sort first, then apply two pointers, binary search, or linear scan. Always ask yourself: does sorting lose information I need (like original indices)?
Problem 3Sum. Sort the array. Fix one element at index i, then use two pointers on the rest to find pairs that sum to -nums[i]. Sorting makes it easy to skip duplicates by checking nums[i] === nums[i-1].
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1, right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++; right--;
} else if (sum < 0) left++;
else right--;
}
}
return result;
}Binary search is not just for finding a value in a sorted array
It is a general strategy for any problem where the search space is monotone: if a condition is false for small values and true for large values (or vice versa), you can binary search on the answer. On arrays, it applies when the array is sorted or partially sorted, when you need to find first/last occurrence, or when you are searching for a threshold value. The key discipline is maintaining the invariant: what does left mean? What does right mean? Never let them cross incorrectly.
Problem Find first bad version. The array of versions is sorted — good versions come before bad. Binary search for the first bad one.
function firstBadVersion(n) {
let left = 1, right = n;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
if (isBadVersion(mid)) right = mid;
else left = mid + 1;
}
return left;
}