Arrays

What you'll learn

• Memory Layout

• Contiguous Allocation

  When you declare an array of size n, the system allocates n sizeof(element) bytes of contiguous memory. The address of any element can be computed directly: This formula is why array access is O(1) - it requires exactly one arithmetic o…

• Cache-Friendliness

  Arrays are extremely cache-friendly because of spatial locality. When the CPU fetches arr[0] from main memory, it loads an entire cache line (typically 64 bytes) into L1 cache. For an int array, that means arr[0] through arr[15] are all…

• Static vs Dynamic Arrays

• Static Arrays

  Static arrays have a fixed size determined at compile time (or allocation time). They cannot grow or shrink. Pros: No overhead, no wasted space beyond allocation, predictable memory usage. Cons: Size must be known in advance, cannot acco…

• Dynamic Arrays

  Dynamic arrays (ArrayList in Java, vector in C++, list in Python) automatically resize when they run out of capacity. They maintain three key values:

• How Resizing Works

  When the array is full and a new element must be added: 1. Allocate a new array of 2x the current capacity 2. Copy all existing elements to the new array 3. Free the old array 4. Insert the new element

• Amortized Analysis

  Although a single resize costs O(n), the amortized cost per insertion is O(1). Proof by accounting method: Consider inserting n elements starting from capacity 1 with doubling: - Resizes happen at sizes: 1, 2, 4, 8, 16, ..., n - Cost of…

• Time Complexities

• Access - O(1)

  Why: The memory address of any element is computed directly using the formula base + index elementsize. No traversal or searching is needed. The CPU performs one multiplication and one addition to find the exact memory location.

• Search (Unsorted) - O(n)

  Why: Without any ordering, the target could be anywhere. In the worst case, you must check every element. There is no shortcut - you cannot skip elements because you have no information about their relative ordering.

• Search (Sorted) - O(log n)

  Why: With a sorted array, binary search eliminates half the remaining elements with each comparison. After k comparisons, only n/2^k elements remain. Solving n/2^k = 1 gives k = log n.

• Insertion at End - O(1) amortized

  Why: For static arrays with available space, it is one write operation. For dynamic arrays, occasional resizing costs O(n), but amortized over n operations, each costs O(1).

• Insertion at Beginning/Middle - O(n)

  Why: All elements after the insertion point must shift right by one position to maintain contiguity. In the worst case (inserting at index 0), all n elements must move.

• Deletion at End - O(1)

  Why: Simply decrement the size counter. No elements need to move.

• Deletion at Beginning/Middle - O(n)

  Why: All elements after the deleted position must shift left by one to fill the gap. In the worst case (deleting index 0), all n-1 remaining elements must move.

• Complete Complexity Table

  | Operation | Time | Space | |-----------|------|-------| | Access by index | O(1) | O(1) | | Search (unsorted) | O(n) | O(1) | | Search (sorted) | O(log n) | O(1) | | Insert at end | O(1) amortized | O(1) | | Insert at index i | O(n - i…

• Common Operations and Algorithms

• Array Traversal

  The simplest operation - visiting each element exactly once. Time: O(n) — each element is visited once. Space: O(1) — no extra structures.

• Array Rotation

  Problem: shift every element of an array k positions to the right. Elements that fall off the right end wrap around to the front. Sample Input / Output Input: arr = [1, 2, 3, 4, 5], k = 2 Output: [4, 5, 1, 2, 3] Input: arr = [10, 20, 30]…

• Circular Arrays

  Some problems treat an array as if it wraps around — there is no real "last" element because after index n-1 you come back to index 0. A queue at a ticket counter, a round-robin scheduler, a ring buffer for audio samples, a year's worth…

• Next Greater Element

  Problem: For each index i in the array, find the next element to the right (at some index j > i) with a value strictly greater than arr[i]. If no such element exists, the answer is -1. Sample Input / Output Input: arr = [2, 1, 3, 4, 2] O…

• Prefix Sum

  Precompute cumulative sums to answer range-sum queries in O(1). Sample Input / Output Input: arr = [3, 1, 4, 1, 5, 9], query rangesum(2, 4) Output: 10 — sum of subarray [4, 1, 5] Input: arr = [1, 2, 3, 4, 5], query rangesum(0, 4) Output:…

• Prefix Sum + Hashmap (Count Subarrays with Target Sum)

  When the problem asks "how many subarrays sum to exactly K?", combine prefix sums with a hashmap to find complementary prefix sums in O(1). Sample Input / Output Input: arr = [1, 2, 3], k = 3 Output: 2 — subarrays [1, 2] and [3] both sum…

• Maximum Sum Subarray of Fixed Length K

  Use prefix sum to find which window of exactly K consecutive elements has the maximum sum. Sample Input / Output Input: arr = [1, 4, 2, 10, 2, 3, 1, 0, 20], k = 3 Output: 21 — window [1, 0, 20] Input: arr = [5, 5, 5, 5, 5], k = 2 Output:…

• Check if Subarray with Given Sum Exists

  Determine whether any contiguous subarray sums to a target value. Sample Input / Output Input: arr = [4, 2, -3, 1, 6], target = 3 Output: True — subarray [4, 2, -3] sums to 3 Input: arr = [1, 2, 3, 4], target = 10 Output: True — entire a…

• Finding the Equilibrium Index

  Find an index where sum of elements to the left equals sum to the right. Sample Input / Output Input: arr = [-7, 1, 5, 2, -4, 3, 0] Output: 3 — at index 3, left sum = -1, right sum = -1 Input: arr = [1, 2, 3] Output: -1 — no equilibrium…

• 2D Prefix Sum (Matrix Range Queries)

  For a matrix, precompute 2D prefix sums to answer "sum of sub-rectangle" queries in O(1). Sample Input / Output Input: matrix = [[1,2,3],[4,5,6],[7,8,9]], query rectangle from (1,1) to (2,2) Output: 28 — sum of 2×2 block [5,6,8,9] Input:…

• Contribution Technique (Counting Element Frequency in All Subarrays)

  Instead of enumerating all subarrays, calculate how many subarrays each element participates in. Sample Input / Output Input: arr = [1, 2, 3] Output: 20 — sum of all subarray sums Input: arr = [5] Output: 5 — single element contributes o…

• Kadane's Algorithm (Maximum Subarray Sum)

  Sample Input / Output Input: arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4] Output: 6 — subarray [4, -1, 2, 1] Input: arr = [-3, -1, -2] Output: -1 — all negatives, pick the largest Input: arr = [5, -2, 3, 1] Output: 7 — entire array excluding th…

• Dutch National Flag (3-Way Partition)

  Sample Input / Output Input: arr = [2, 0, 2, 1, 1, 0, 2, 1, 0] Output: [0, 0, 0, 1, 1, 1, 2, 2, 2] Input: arr = [1, 1, 1] Output: [1, 1, 1] — all same value Input: arr = [2, 0, 1] Output: [0, 1, 2] — minimal case with one of each Partiti…

• Multi-Dimensional Arrays

• 2D Arrays (Matrices)

  A 2D array is stored as a flattened 1D array in memory. Row-major order (C, Python) stores rows sequentially:

• Matrix Transpose

  Definition: The transpose of a matrix M is a matrix T where T[i][j] = M[j][i]. Rows become columns, columns become rows.

• Common 2D Operations

  | Operation | Time | |-----------|------| | Access element | O(1) | | Row traversal | O(cols) | | Column traversal | O(rows) | | Full traversal | O(rows cols) | | Transpose | O(rows cols) |

• When to Use Arrays

• Use arrays when:

  - Random access is needed - accessing elements by index in O(1) - Cache performance matters - sequential access patterns benefit from spatial locality - Data size is known or has an upper bound - static allocation avoids overhead - Memor…

• Avoid arrays when:

  - Frequent insertions/deletions in the middle - O(n) shifting is expensive - Size is highly unpredictable - frequent resizing wastes time and memory - You need fast lookup by value - use a hash table instead - You need ordered insertions…

• Common Patterns in Competitive Programming

• Two-Pointer Technique

  Sample Input / Output Input: arr = [1, 2, 4, 7, 11, 15], target = 15 Output: (1, 4) — indices of 2 and 11 Input: arr = [1, 3, 5, 7], target = 10 Output: (1, 3) — indices of 3 and 7 Input: arr = [1, 2, 3], target = 10 Output: None — no pa…

• Sliding Window

  Sample Input / Output Input: arr = [1, 4, 2, 10, 2, 3, 1, 0, 20], k = 3 Output: 21 — maximum sum window [1, 0, 20] Input: arr = [5, 5, 5, 5], k = 2 Output: 10 — all windows identical Input: arr = [-1, -2, -3], k = 2 Output: -3 — window […

• Subarray Problems

  Many competitive programming problems involve finding subarrays with specific properties: | Problem Type | Technique | Complexity | |-------------|-----------|-----------| | Max/min subarray sum | Kadane's | O(n) | | Subarray with given…

• Maximum Profit from One Trade (Stock Buy/Sell)

  Sample Input / Output Input: prices = [7, 1, 5, 3, 6, 4] Output: 5 — buy at 1, sell at 6 Input: prices = [7, 6, 4, 3, 1] Output: 0 — strictly decreasing Input: prices = [3, 3, 3, 3] Output: 0 — all same price Given the day-by-day price o…

• Maximum Product of Array Elements

  Sample Input / Output Input: arr = [-1, -2, -3, 4, 5, 0, 6] Output: 720 — pick {-2, -3, 4, 5, 6} Input: arr = [0, -2, 0] Output: 0 — only zeros and one negative Input: arr = [2, 3, -2, 4] Output: 96 — product of all four elements Given a…

• Boyer-Moore Majority Vote

  Sample Input / Output Input: arr = [3, 3, 4, 2, 4, 4, 2, 4, 4] Output: 4 — appears 5 times (> n/2) Input: arr = [1, 1, 1, 2, 2] Output: 1 — appears 3 times Input: arr = [5] Output: 5 — single element is always majority Find the element t…

• In-Place vs Out-of-Place Operations

  Understanding space usage is critical for array algorithms:

• In-Place (O(1) extra space)

  The algorithm modifies the input array directly without allocating proportional extra memory. Examples: rotation via reversal, Dutch National Flag, quicksort partition, Kadane's.

• Out-of-Place (O(n) extra space)

  The algorithm creates a new array for the result. Examples: mergesort merge step, prefix sum construction, filtering. Interview tip: Always clarify whether you can modify the input array or need to preserve it. This affects your space co…

• Array vs Other Data Structures

  | Feature | Array | Linked List | Hash Table | BST | |---------|-------|-------------|-----------|-----| | Access by index | O(1) | O(n) | N/A | N/A | | Search by value | O(n) | O(n) | O(1) avg | O(log n) | | Insert at end | O(1) | O(1)…

• Common Interview Tricks

• Sentinel Values

  Using special values to simplify boundary conditions:

• Index Mapping

  Using array indices as implicit keys (a form of direct addressing): This is O(n) time and O(1) space (fixed 128 slots regardless of input size).

• Circular Array Trick

  Treating an array as circular using modulo arithmetic: This is the basis for efficient circular buffer / ring buffer implementations.

• Count Distinct Pairs with Given Difference

  Sample Input / Output Input: arr = [1, 5, 3, 4, 2], k = 3 Output: 2 — pairs (1,4) and (5,2) Input: arr = [1, 1, 1, 2], k = 0 Output: 1 — only value 1 appears more than once Input: arr = [1, 2, 3, 4, 5], k = 1 Output: 4 — consecutive pair…

• Find Pair Where Sum of Indices Equals Sum of Values

  Sample Input / Output Input: arr = [0, 2, 1, 4] Output: true — indices i=1, j=2: 1+2 = 2+1 = 3 Input: arr = [1, 2, 3, 4] Output: false — no valid pair Input: arr = [-1, 5, 3] Output: true — indices i=0, j=2: 0+2 = -1+3 = 2 Given an array…

• Related Algorithms

  Arrays serve as the foundation for many fundamental algorithms covered in the Algorithms path: - Sorting - Comparison sorts (quicksort, mergesort) and non-comparison sorts (counting, radix) all operate on arrays - Binary Search - Require…

• Edge Cases to Remember

  Always consider these in interviews: 1. Empty array (n = 0) 2. Single element (n = 1) 3. All elements identical 4. Already sorted / reverse sorted 5. Array with negative numbers (affects sum-based problems) 6. Integer overflow in sum cal…

• Summary

  Arrays are the bedrock data structure. Their O(1) access and cache-friendliness make them the default choice when random access is needed. The key trade-off is O(n) insertion/deletion in the middle. Master prefix sums, two pointers, slid…