Array Basics and Common Techniques

The Memory Model of Arrays

The array is the most fundamental data structure. Its core characteristic is: a contiguous block of memory storing elements of the same type.

This "contiguity" is not an arbitrary design choice; it is the root of all its properties:

Memory Address: 1000  1004  1008  1012  1016
                 |     |     |     |     |
Value:          [  3  |  7  |  1  |  9  |  5  ]
Index:           0     1     2     3     4

Given the starting address base and the element size size, the address of the i-th element = base + i × size. This is why Random Access is O(1)—it's a simple calculation to jump to any element in one step.

In contrast, accessing the i-th element of a linked list requires jumping through pointers from the head one by one, resulting in O(n).

Operational Complexity

Two Pointers Technique

Two pointers is one of the most common techniques for solving array problems. It generally falls into two categories:

Collision Pointers (Moving from Ends to Middle)

Use Case: Sorted arrays, when searching for a pair of elements that satisfy a specific condition.

Classic Problems: Two Sum (Sorted version), Three Sum, Trapping Rain Water, Palindrome check.

// Two Sum (Sorted Array version)
// Time: O(n), Space: O(1)
int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return new int[]{left, right};
        else if (sum < target) left++;   // Sum too small, move left pointer right (increase)
        else right--;                    // Sum too large, move right pointer left (decrease)
    }
    return new int[]{};
}

Intuition: In a sorted array, the smallest values are at the left and the largest at the right. By moving pointers inward based on the current sum, we eliminate one candidate per step, reaching the target in O(n).

Fast & Slow Pointers (Moving in Same Direction)

Use Case: Deduplication, element removal, finding midpoints. Usually used to "overwrite" unwanted elements in-place.

// Remove all occurrences of 'val' in-place, return new length
// Time: O(n), Space: O(1)
int removeElement(int[] nums, int val) {
    int slow = 0;  // 'slow' points to the next available position for a valid element
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];  // Move valid element to the 'slow' position
        }
        // Skip 'fast' when it hits 'val', while 'slow' stays put
    }
    return slow;  // 'slow' represents the new length of the valid subarray
}

Initial: [3, 2, 2, 3], val = 3
fast=0: nums[0]=3=val, skip
fast=1: nums[1]=2≠val, nums[0]=2, slow=1
fast=2: nums[2]=2≠val, nums[1]=2, slow=2
fast=3: nums[3]=3=val, skip
Result: [2, 2, ?, ?], returns 2

Sliding Window

Sliding Window is the go-to technique for contiguous subarray problems, reducing brute force O(n²) to O(n).

Core Idea: Maintain a "window" (the range between left and right). Expand the right boundary to include new elements; when the window fails to meet a condition, shrink the left boundary until valid again.

// Minimum Size Subarray Sum (sum >= target)
// Time: O(n), Space: O(1)
int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0, minLen = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];           // Expand right boundary
        while (sum >= target) {       // While condition is met
            minLen = Math.min(minLen, right - left + 1);  // Update answer
            sum -= nums[left++];      // Shrink left boundary to find smaller window
        }
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

Key Questions for Sliding Window

1. What state to maintain in the window? (Sum, Character frequency, etc.)
2. When to expand the right boundary? (Usually every iteration)
3. When to shrink the left boundary? (When a condition is violated or when optimization is possible)
4. When to update the answer? (When valid; either before or during the shrinking phase)

Prefix Sum

Prefix Sum is a pre-processing technique for range queries, reducing "subarray sum calculation" from O(n) to O(1).

// Construct the prefix sum array
// prefix[i] = nums[0] + nums[1] + ... + nums[i-1]
// prefix[0] = 0 (Sentinel value for easier index math)
int[] buildPrefix(int[] nums) {
    int[] prefix = new int[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }
    return prefix;
}

// Query the sum of range [left, right]: O(1)
int rangeSum(int[] prefix, int left, int right) {
    return prefix[right + 1] - prefix[left];
}

Intuition: prefix[i] represents the cumulative total from the start to before the i-th element. The sum of a range [left, right] is the total up to right minus the total before left.

nums:    [2, 3, 1, 5, 4]
Index:     0  1  2  3  4
prefix:  [0, 2, 5, 6, 11, 15]
          ^
          Sentinel 0

Query sum of [1, 3]: prefix[4] - prefix[1] = 11 - 2 = 9
Verification: 3 + 1 + 5 = 9 ✓

Difference Array

A Difference Array is the "inverse operation" of a Prefix Sum, used for frequent range updates.

Scenario: Perform m operations of "add val to all elements in range [l, r]," then query final values.

• Brute Force: O(mn)
• Difference Array: O(m + n) (O(1) per update, O(n) to restore).

// Core logic of Difference Array
int[] diff = new int[n + 1];  // diff[i] = nums[i] - nums[i-1]

// Update range [l, r] by 'val': Modify only two points
void add(int l, int r, int val) {
    diff[l] += val;       // Start increase at 'l'
    diff[r + 1] -= val;  // End increase after 'r'
}

// Restore original array: Calculate prefix sum of diff
int[] restore() {
    int[] nums = new int[n];
    nums[0] = diff[0];
    for (int i = 1; i < n; i++) {
        nums[i] = nums[i - 1] + diff[i];
    }
    return nums;
}

String Processing Techniques

In Java, strings are immutable String objects. For frequent concatenation, use StringBuilder (O(1) amortized append vs. O(n) for String concat).

Char Frequency Counters

// Option 1: For lowercase English letters (26)
int[] freq = new int[26];
for (char c : s.toCharArray()) {
    freq[c - 'a']++;
}

// Option 2: For any character set
Map<Character, Integer> freq = new HashMap<>();
for (char c : s.toCharArray()) {
    freq.merge(c, 1, Integer::sum);
}

Two Pointers in Strings

Palindrome Check: Use collision pointers moving from both ends to the center.

boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left++) != s.charAt(right--)) return false;
    }
    return true;
}

Common Edge Cases and Pitfalls

Integer Overflow in (left + right) / 2

If left and right are large, their sum may exceed the maximum int value.

// Incorrect: May overflow
int mid = (left + right) / 2;

// Correct: Equivalent but safe
int mid = left + (right - left) / 2;

Index Out of Bounds

Always verify 0 <= i < arr.length before accessing arr[i]. Be especially careful with arr[i-1] or arr[i+1] near the boundaries.

Empty Arrays and Single Elements

Many algorithms have special behavior for null, empty, or single-element inputs. Add guards at the start:

if (nums == null || nums.length == 0) return 0;

Summary

The fundamental advantage of arrays is O(1) random access from contiguous memory addressing.

Four Key Mastery Points: