Array Fundamentals

TL;DR

Arrays provide O(1) random access but O(n) insertion/deletion. Efficient traversal processes elements in order. In-place manipulation minimizes space. Rotation and reversal rearrange elements efficiently. Subarray problems often benefit from sliding window or prefix sum techniques. Understanding these fundamentals enables solving complex array-based problems optimally.

Core Concepts

Array Traversal and Manipulation

Linear traversal processes elements from index 0 to n-1, enabling simple sequential operations like counting, filtering, or aggregation. Single-pass algorithms often achieve O(n) efficiency.

Reverse traversal processes elements from n-1 to 0, useful for problems where working backwards reveals structure (e.g., removing duplicates while iterating).

Multi-pass traversal uses multiple iterations when single pass is insufficient. For example, finding the maximum element then removing it requires two passes.

In-place manipulation modifies the array without allocating new space. Swap operations enable efficient rearrangement. In-place algorithms achieve O(1) space complexity versus O(n) for copying.

Finding Elements and Indices

Linear search iterates sequentially through elements, comparing each to target. O(n) time, but works on unsorted arrays. Useful when no preprocessing is possible.

Binary search on sorted arrays eliminates half the search space per comparison, achieving O(log n) time. Requires sorted data but far more efficient for large datasets.

Finding multiple elements with linear search is O(n) regardless of match count. With hash tables, O(n) preprocessing enables O(1) individual lookups.

Index-based operations directly access elements by position. Useful for problems requiring specific indexing patterns like alternating elements or specific intervals.

Array Rotation and Reversal

Array rotation by k positions shifts all elements k indices to the left (or right), with wraparound. Example: rotate [1,2,3,4,5] by 2 gives [3,4,5,1,2].

In-place rotation uses reversal technique: reverse [0, k-1], reverse [k, n-1], then reverse entire array. Three reversals achieve rotation in O(n) time with O(1) space.

Array reversal completely reverses element order. In-place reversal swaps elements symmetrically: swap arr[i] with arr[n-1-i] for i from 0 to n/2.

Segment reversal reverses only part of array, useful for problems like rotating arrays or rearranging specific subarrays.

Subarray Problems

Maximum subarray finds contiguous elements with maximum sum. Kadane's algorithm achieves O(n) by tracking running sum and resetting when it becomes negative.

Subarray sum queries compute sums of arbitrary ranges. Prefix sum array enables O(1) queries after O(n) preprocessing: prefixSum[i+1] = prefixSum[i] + arr[i].

Subarray length problems find subarrays satisfying specific properties. Sliding window efficiently maintains current subarray characteristics while moving boundaries.

Subarrays with specific properties (e.g., sum equals target, all elements even) require careful boundary management. Two pointers or sliding window typically apply.

Key Algorithms and Techniques

Linear Search

Iterate through array comparing each element to target. O(n) time, O(1) space.

Reverse Traversal Technique

Process array backwards to handle deletions or removals safely without index shifting issues.

In-Place Rotation via Reversal

Three reversal operations rotate array without extra space: O(n) time, O(1) space.

Kadane's Algorithm

Maintain running maximum sum, reset when negative. Solves maximum subarray in O(n) time, O(1) space.

Prefix Sum Array

Precompute cumulative sums enabling O(1) range sum queries: sum(i, j) = prefix[j+1] - prefix[i].

Practical Example

Python

# Linear traversal
def process_array(arr):
    for i in range(len(arr)):
        print(arr[i])

# Reverse traversal
def reverse_process(arr):
    for i in range(len(arr) - 1, -1, -1):
        print(arr[i])

# In-place array reversal
def reverse_array(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

# In-place array rotation
def rotate_array(arr, k):
    k = k % len(arr)  # Handle k > n
    def reverse(arr, start, end):
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1
    reverse(arr, 0, len(arr) - 1)
    reverse(arr, 0, k - 1)
    reverse(arr, k, len(arr) - 1)
    return arr

# Kadane's algorithm: maximum subarray
def max_subarray(arr):
    max_current = max_global = arr[0]
    for i in range(1, len(arr)):
        max_current = max(arr[i], max_current + arr[i])
        max_global = max(max_global, max_current)
    return max_global

# Prefix sum for range queries
def build_prefix_sum(arr):
    prefix = [0]
    for num in arr:
        prefix.append(prefix[-1] + num)
    return prefix

def range_sum(prefix, i, j):
    return prefix[j + 1] - prefix[i]

# Linear search
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Test cases
arr = [1, 2, 3, 4, 5]
print(f"Reversed: {reverse_array(arr.copy())}")
print(f"Rotated by 2: {rotate_array(arr.copy(), 2)}")
print(f"Max subarray of [-2, 1, -3, 4, -1, 2, 1, -5, 4]: {max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])}")

prefix = build_prefix_sum(arr)
print(f"Sum[1, 3]: {range_sum(prefix, 1, 3)}")

Java

public class ArrayFundamentals {
    // Linear traversal
    static void processArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    // In-place array reversal
    static void reverseArray(int[] arr) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

    // In-place array rotation
    static void rotateArray(int[] arr, int k) {
        k = k % arr.length;
        reverse(arr, 0, arr.length - 1);
        reverse(arr, 0, k - 1);
        reverse(arr, k, arr.length - 1);
    }

    static void reverse(int[] arr, int start, int end) {
        while (start < end) {
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            start++;
            end--;
        }
    }

    // Kadane's algorithm: maximum subarray
    static int maxSubarray(int[] arr) {
        int maxCurrent = arr[0], maxGlobal = arr[0];
        for (int i = 1; i < arr.length; i++) {
            maxCurrent = Math.max(arr[i], maxCurrent + arr[i]);
            maxGlobal = Math.max(maxGlobal, maxCurrent);
        }
        return maxGlobal;
    }

    // Prefix sum array
    static int[] buildPrefixSum(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;
    }

    static int rangeSum(int[] prefix, int i, int j) {
        return prefix[j + 1] - prefix[i];
    }

    // Linear search
    static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        rotateArray(arr, 2);
        System.out.println(Arrays.toString(arr));

        int[] arr2 = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Max subarray: " + maxSubarray(arr2));
    }
}

TypeScript

// Linear traversal
function processArray(arr: number[]): void {
    for (let i = 0; i < arr.length; i++) {
        console.log(arr[i]);
    }
}

// In-place array reversal
function reverseArray(arr: number[]): number[] {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
    return arr;
}

// In-place array rotation
function rotateArray(arr: number[], k: number): number[] {
    k = k % arr.length;

    function reverse(start: number, end: number): void {
        while (start < end) {
            [arr[start], arr[end]] = [arr[end], arr[start]];
            start++;
            end--;
        }
    }

    reverse(0, arr.length - 1);
    reverse(0, k - 1);
    reverse(k, arr.length - 1);
    return arr;
}

// Kadane's algorithm: maximum subarray
function maxSubarray(arr: number[]): number {
    let maxCurrent = arr[0], maxGlobal = arr[0];
    for (let i = 1; i < arr.length; i++) {
        maxCurrent = Math.max(arr[i], maxCurrent + arr[i]);
        maxGlobal = Math.max(maxGlobal, maxCurrent);
    }
    return maxGlobal;
}

// Prefix sum array
function buildPrefixSum(arr: number[]): number[] {
    const prefix: number[] = [0];
    for (const num of arr) {
        prefix.push(prefix[prefix.length - 1] + num);
    }
    return prefix;
}

function rangeSum(prefix: number[], i: number, j: number): number {
    return prefix[j + 1] - prefix[i];
}

// Linear search
function linearSearch(arr: number[], target: number): number {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

// Test
const arr = [1, 2, 3, 4, 5];
console.log("Reversed:", reverseArray([...arr]));
console.log("Rotated by 2:", rotateArray([...arr], 2));
console.log("Max subarray:", maxSubarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));

Common Pitfalls

warning

Off-by-one errors: Loop boundaries (i < n vs i <= n) and index calculations cause common bugs. Carefully verify loop ranges and edge cases.

Not handling negative numbers: Kadane's algorithm with all-negative array can fail if not initialized properly. Initialize max_current and max_global to first element.

Incorrect rotation formula: Rotation count k should be modulo array length. k > n wraps around multiple times; k % n gives effective rotation.

Prefix sum index confusion: Prefix array has n+1 elements for n-element input. Index i in prefix corresponds to sum of arr[0..i-1].

Modifying array during iteration: Removing elements while iterating forward causes skipped elements. Use reverse iteration or create new array.

Self-Check

1. Explain how Kadane's algorithm solves maximum subarray in O(n) time. What changes when all numbers are negative?
2. Why does reversing three times rotate an array? Work through an example to verify.
3. How does prefix sum enable range queries in O(1) time? What is the space trade-off?

One Takeaway

info

Master array fundamentals—efficient traversal, in-place manipulation, and subarray techniques—and you'll solve countless problems optimally. Understanding when to use techniques like prefix sums, sliding windows, and Kadane's algorithm separates efficient solutions from inefficient ones.

References

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
• McDowell, G. L. (2015). Cracking the Coding Interview (6th ed.). CareerCup.