Arrays are the most fundamental data structure. Master them and you'll solve 40% of coding interview problems.
An array is a contiguous block of memory storing elements of the same type, accessed by index.
int[] arr = {10, 20, 30, 40, 50};
// 0 1 2 3 4 ← indicesBecause elements are stored contiguously, accessing any element by index is O(1) — the CPU can jump directly to base_address + index * element_size.
arr[2]; // direct access, always instantpublic int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}Inserting shifts all elements to the right.
list.add(2, 99); // shifts list.get(2), list.get(3)... rightDeleting shifts all elements to the left.
list.remove(2); // shifts list.get(3), list.get(4)... leftDynamic arrays (Python lists, Java ArrayList) double in size when full — this makes append O(1) amortized even though occasional resizes are O(n).
Two pointers is used in ~30% of array interview problems.
public int[] twoSumSorted(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left < right) {
int total = arr[left] + arr[right];
if (total == target) {
return new int[]{left, right};
} else if (total < target) {
left++;
} else {
right--;
}
}
return new int[]{};
}public int removeDuplicates(int[] arr) {
if (arr.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < arr.length; fast++) {
if (arr[fast] != arr[slow]) {
slow++;
arr[slow] = arr[fast];
}
}
return slow + 1;
}public int maxSumSubarray(int[] arr, int k) {
// Find max sum of any subarray of size k
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
int maxSum = windowSum;
for (int i = k; i < arr.length; i++) {
windowSum += arr[i] - arr[i - k]; // slide window
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}public int[] buildPrefix(int[] arr) {
int[] prefix = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
prefix[i + 1] = prefix[i] + arr[i];
}
return prefix;
}
public int rangeSum(int[] prefix, int left, int right) {
return prefix[right + 1] - prefix[left]; // O(1) query!
}| Pattern | When to use | Example problems |
|---|---|---|
| Two pointers | Sorted array, pairs | Two Sum, Container With Most Water |
| Sliding window | Subarray/substring | Max sum subarray, Longest substring |
| Prefix sum | Range sum queries | Subarray sum equals K |
| Kadane's algorithm | Max subarray sum | Maximum Subarray |
| Binary search | Sorted array search | Search in rotated array |
public int maxSubarray(int[] arr) {
int maxSum = arr[0];
int currentSum = arr[0];
for (int i = 1; i < arr.length; i++) {
currentSum = Math.max(arr[i], currentSum + arr[i]);
maxSum = Math.max(maxSum, currentSum);
}
return maxSum;
}