Array | Dheerendra Varma

What is an Array?

An array is a contiguous block of memory that stores elements of the same type at consecutive addresses. Because elements are laid out sequentially, any element can be reached in constant time: the CPU computes the address as base + index × element_size without following any pointers.

Rust distinguishes between fixed-size arrays [T; N], which live on the stack with their length known at compile time, and dynamic arrays Vec<T>, which allocate on the heap and can grow or shrink at runtime. Slices &[T] are borrowed views into any contiguous sequence — both arrays and Vecs — and are the idiomatic way to accept array data in functions without caring about the source.

Applications

Arrays underpin nearly every other data structure. Hash tables use arrays of buckets. Heaps are stored as flat arrays because parent-child index relationships are purely arithmetic. Dense graphs are represented as two-dimensional arrays (adjacency matrices). Image data is a flat array of pixel values. Ring buffers — used in networking and audio processing — are arrays with head and tail indices that wrap around modulo capacity.

Representations

Fixed-size arrays in Rust carry their length as a type parameter. The compiler guarantees stack allocation and a size that can never change.

fn fixed_array() {
    let arr: [i32; 5] = [10, 20, 30, 40, 50];
    println!("index 2: {}", arr[2]);    // O(1)
    println!("length: {}", arr.len());  // compile-time constant
}

Dynamic arrays (Vec<T>) are the workhorse in algorithm problems. They allocate a backing buffer on the heap and double its capacity when full, giving amortised O(1) push.

fn dynamic_array() {
    let mut v: Vec<i32> = Vec::new();
    v.push(10);           // O(1) amortised
    v.push(20);
    v.push(30);
    v.insert(1, 15);      // O(n) — shifts elements right
    v.remove(2);          // O(n) — shifts elements left
    println!("{:?}", v);  // [10, 15, 30]
}

Slices are universal views. A function accepting &[i32] works with both stack arrays and Vecs.

fn sum(data: &[i32]) -> i32 {
    data.iter().sum()
}
 
fn slice_demo() {
    let arr = [1, 2, 3, 4, 5];
    let v = vec![10, 20, 30];
    println!("{}", sum(&arr));       // works on array
    println!("{}", sum(&v));         // works on Vec
    println!("{}", sum(&arr[1..4])); // subslice: sum of [2,3,4] = 9
}

Operations and Time Complexity

Operation	Time	Notes
Access by index	O(1)	Direct address computation
Search (unsorted)	O(n)	Linear scan
Search (sorted, binary)	O(log n)	Halve search space each step
Insert at end (Vec push)	O(1) amortised	Rare O(n) on capacity doubling
Insert at index	O(n)	Shifts all following elements right
Delete at end	O(1)	Decrement length
Delete at index	O(n)	Shifts all following elements left
Slice / view	O(1)	Pointer and length, no copy

Implementation in Rust

fn array_operations() {
    let mut nums = vec![3, 1, 4, 1, 5, 9, 2, 6];
 
    // Random access
    let first = nums[0];
    let last  = nums[nums.len() - 1];
 
    // Linear search
    let pos = nums.iter().position(|&x| x == 5); // Some(4)
 
    // Sort then binary search
    nums.sort();
    let bpos = nums.binary_search(&5); // Ok(index)
 
    // Subarray view — zero cost
    let mid = &nums[2..5];
 
    // In-place operations
    nums.reverse();
    nums.dedup(); // removes consecutive duplicates (requires sorted)
 
    // Rotate left by k positions
    let k = 2 % nums.len();
    nums.rotate_left(k);
 
    println!("first={first} last={last} linear={pos:?} binary={bpos:?}");
    println!("mid slice: {mid:?}");
}

Fundamental Algorithms and Problems

Two-Pointer Technique

Given a sorted array and a target, find two indices whose values sum to the target. Brute force checks all pairs in O(n²). The two-pointer technique uses one pointer at each end and moves them inward: if the sum is too small, advance the left pointer; if too large, retreat the right. This works in O(n) with O(1) space and generalises to three-sum, container-with-most-water, and trapping rain water.

fn two_sum_sorted(arr: &[i32], target: i32) -> Option<(usize, usize)> {
    let (mut l, mut r) = (0, arr.len().saturating_sub(1));
    while l < r {
        let s = arr[l] + arr[r];
        match s.cmp(&target) {
            std::cmp::Ordering::Equal   => return Some((l, r)),
            std::cmp::Ordering::Less    => l += 1,
            std::cmp::Ordering::Greater => r -= 1,
        }
    }
    None
}
 
fn main() {
    let arr = [1, 2, 4, 6, 8, 10];
    println!("{:?}", two_sum_sorted(&arr, 10)); // Some((1, 4)) → 2+8
}

Sliding Window

Find the maximum sum among all contiguous subarrays of a fixed size k. The naive approach recomputes each window from scratch in O(n·k). The sliding window maintains a running sum, subtracting the element that leaves and adding the one that enters, giving O(n) time and O(1) space. The variable-size variant — used in "longest substring without repeating characters" — expands the right pointer and contracts the left when a constraint is violated.

fn max_sum_window(arr: &[i32], k: usize) -> i32 {
    if arr.len() < k { return 0; }
 
    let mut window: i32 = arr[..k].iter().sum();
    let mut best = window;
 
    for i in k..arr.len() {
        window += arr[i] - arr[i - k];
        best = best.max(window);
    }
    best
}
 
fn main() {
    let arr = [2, 1, 5, 1, 3, 2];
    println!("{}", max_sum_window(&arr, 3)); // 9  (window [5,1,3])
}

Prefix Sum

prefix[i] stores the sum of elements from index 0 through i-1. The sum of any range [l, r] is then prefix[r+1] - prefix[l] — a single subtraction after O(n) preprocessing. This technique appears in 2D matrix problems (2D prefix sums), difference arrays (range add operations), and equilibrium index problems.

fn build_prefix(arr: &[i32]) -> Vec<i32> {
    let mut p = vec![0; arr.len() + 1];
    for (i, &x) in arr.iter().enumerate() {
        p[i + 1] = p[i] + x;
    }
    p
}
 
fn range_sum(prefix: &[i32], l: usize, r: usize) -> i32 {
    prefix[r + 1] - prefix[l]
}
 
fn main() {
    let arr   = [3, 1, 4, 1, 5, 9, 2, 6];
    let prefix = build_prefix(&arr);
    println!("{}", range_sum(&prefix, 2, 5)); // 4+1+5+9 = 19
    println!("{}", range_sum(&prefix, 0, 7)); // full sum = 31
}

Kadane's Algorithm — Maximum Subarray Sum

Find the contiguous subarray with the largest sum. Kadane's insight: the best subarray ending at index i is either arr[i] alone (start fresh) or arr[i] extended from the best subarray ending at i-1 (extend). Choosing the larger of the two and tracking the global maximum runs in O(n) with O(1) space and handles arrays with all-negative values correctly.

fn max_subarray(arr: &[i32]) -> i32 {
    let mut best_ending_here = arr[0];
    let mut best_so_far      = arr[0];
 
    for &x in &arr[1..] {
        best_ending_here = x.max(best_ending_here + x);
        best_so_far      = best_so_far.max(best_ending_here);
    }
    best_so_far
}
 
fn main() {
    let arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
    println!("{}", max_subarray(&arr)); // 6  (subarray [4,-1,2,1])
}

Dutch National Flag — Three-Way Partition

Sort an array of only 0s, 1s, and 2s in one pass without counting. Three pointers define four regions: [0..low) all zeros, [low..mid) all ones, [mid..high) unexplored, [high..n) all twos. The mid pointer advances through the unexplored region. Finding a 0 swaps it to the zeros region and advances both low and mid. Finding a 2 swaps it to the twos region and retreats high only — the new element at mid still needs inspection. Finding a 1 just advances mid.

fn dutch_national_flag(arr: &mut [i32]) {
    let (mut low, mut mid) = (0usize, 0usize);
    let mut high = arr.len();
 
    while mid < high {
        match arr[mid] {
            0 => { arr.swap(low, mid); low += 1; mid += 1; }
            1 => { mid += 1; }
            _ => { high -= 1; arr.swap(mid, high); }
        }
    }
}
 
fn main() {
    let mut arr = vec![2, 0, 1, 2, 1, 0, 0, 2, 1];
    dutch_national_flag(&mut arr);
    println!("{:?}", arr); // [0, 0, 0, 1, 1, 1, 2, 2, 2]
}