Arrays in Data Structure Operations

What is an Array?

An array provides indexed access over contiguous elements. Insertion and deletion costs depend on shifting, while every traversal must respect length and valid index boundaries.

Choose Arrays in Data Structure Operations when its access pattern matches the problem; avoid it when a simpler array, list, or map would make the code easier to reason about.

An array is the simplest and most widely used data structure. It stores a fixed-size collection of elements of the same type in contiguous memory locations. Each element is accessed directly by its index (position), starting from 0.

Think of an array like a row of numbered lockers - you can instantly open locker #5 without checking lockers 1 through 4.

Array Characteristics

Property	Value
Access by index	O(1) - instant
Search (unsorted)	O(n) - must check each element
Search (sorted)	O(log n) - binary search
Insert at end	O(1) - if space available
Insert at middle	O(n) - must shift elements
Delete	O(n) - must shift elements
Memory	Contiguous - cache-friendly
Size	Fixed (static) or dynamic (ArrayList/vector)

Array Declaration and Basic Operations

Array - Declaration, Access, Traversal

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // Static array - fixed size
    int arr[5] = {10, 20, 30, 40, 50};

    // Access by index - O(1)
    cout << "arr[0] = " << arr[0] << endl;  // 10
    cout << "arr[4] = " << arr[4] << endl;  // 50

    // Traversal
    cout << "Elements: ";
    for (int i = 0; i < 5; i++) cout << arr[i] << " ";
    cout << endl;

    // Range-based for (C++11)
    for (int x : arr) cout << x << " ";
    cout << endl;

    // Dynamic array - vector (preferred in C++)
    vector<int> v = {1, 2, 3, 4, 5};
    v.push_back(6);   // add to end - O(1) amortized
    v.pop_back();     // remove last - O(1)
    cout << "Size: " << v.size() << endl;

    // 2D array
    int matrix[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
    cout << "matrix[1][2] = " << matrix[1][2] << endl;  // 6

    return 0;
}

Array Declaration and Basic Operations - Java Example

import java.util.ArrayList;
import java.util.Arrays;

public class ArrayDemo {
    public static void main(String[] args) {
        // Static array - fixed size
        int[] arr = {10, 20, 30, 40, 50};

        // Access by index - O(1)
        System.out.println("arr[0] = " + arr[0]);  // 10
        System.out.println("arr[4] = " + arr[4]);  // 50

        // Traversal
        System.out.print("Elements: ");
        for (int i = 0; i < arr.length; i++) System.out.print(arr[i] + " ");
        System.out.println();

        // Enhanced for loop
        for (int x : arr) System.out.print(x + " ");
        System.out.println();

        // Dynamic array - ArrayList
        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
        list.add(6);       // add to end - O(1) amortized
        list.remove(0);    // remove at index - O(n)
        System.out.println("Size: " + list.size());

        // 2D array
        int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};
        System.out.println("matrix[1][2] = " + matrix[1][2]);  // 6
    }
}

Array Declaration and Basic Operations - Python Example

# Python list - dynamic array (no fixed-size arrays by default)
arr = [10, 20, 30, 40, 50]

# Access by index - O(1)
print("arr[0] =", arr[0])   # 10
print("arr[-1] =", arr[-1]) # 50 (negative index from end)

# Traversal
print("Elements:", arr)
for x in arr:
    print(x, end=" ")
print()

# Dynamic operations
arr.append(60)      # add to end - O(1)
arr.insert(2, 25)   # insert at index 2 - O(n)
arr.pop()           # remove last - O(1)
arr.pop(0)          # remove at index - O(n)
print("After ops:", arr)

# List slicing
print("First 3:", arr[:3])
print("Last 2:", arr[-2:])
print("Reversed:", arr[::-1])

# 2D array (list of lists)
matrix = [[1,2,3],[4,5,6],[7,8,9]]
print("matrix[1][2] =", matrix[1][2])  # 6

# NumPy for true arrays (optional)
# import numpy as np
# arr = np.array([1, 2, 3, 4, 5])

Array Declaration and Basic Operations - JavaScript Example

// JavaScript Array - dynamic, can hold mixed types
const arr = [10, 20, 30, 40, 50];

// Access by index - O(1)
console.log("arr[0] =", arr[0]);   // 10
console.log("arr[4] =", arr[4]);   // 50

// Traversal
arr.forEach(x => process.stdout.write(x + " "));
console.log();

// Dynamic operations
arr.push(60);       // add to end - O(1)
arr.pop();          // remove last - O(1)
arr.unshift(5);     // add to front - O(n)
arr.shift();        // remove from front - O(n)
arr.splice(2, 0, 25); // insert at index 2 - O(n)

// Useful array methods
const doubled = arr.map(x => x * 2);
const evens   = arr.filter(x => x % 2 === 0);
const sum     = arr.reduce((acc, x) => acc + x, 0);
console.log("Sum:", sum);

// 2D array
const matrix = [[1,2,3],[4,5,6],[7,8,9]];
console.log("matrix[1][2] =", matrix[1][2]);  // 6

Common Array Algorithms

Find Max, Reverse, Rotate Array

#include <iostream>
#include <algorithm>
using namespace std;

// Find maximum element - O(n)
int findMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max) max = arr[i];
    return max;
}

// Reverse array in-place - O(n)
void reverse(int arr[], int n) {
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        swap(arr[lo], arr[hi]);
        lo++; hi--;
    }
}

// Rotate array left by k positions - O(n)
void rotateLeft(int arr[], int n, int k) {
    k %= n;
    reverse(arr, arr + k);
    reverse(arr + k, arr + n);
    reverse(arr, arr + n);
}

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
    int n = 8;
    cout << "Max: " << findMax(arr, n) << endl;  // 9
    reverse(arr, n);
    for (int x : arr) cout << x << " ";  // 6 2 9 5 1 4 1 3
    return 0;
}

Common Array Algorithms - Java Example

import java.util.Arrays;

public class ArrayAlgorithms {
    static int findMax(int[] arr) {
        int max = arr[0];
        for (int x : arr) if (x > max) max = x;
        return max;
    }

    static void reverse(int[] arr) {
        int lo = 0, hi = arr.length - 1;
        while (lo < hi) {
            int temp = arr[lo]; arr[lo] = arr[hi]; arr[hi] = temp;
            lo++; hi--;
        }
    }

    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
        System.out.println("Max: " + findMax(arr));  // 9
        reverse(arr);
        System.out.println(Arrays.toString(arr));    // [6, 2, 9, 5, 1, 4, 1, 3]
    }
}

Common Array Algorithms - Python Example

arr = [3, 1, 4, 1, 5, 9, 2, 6]

# Find max - O(n)
print("Max:", max(arr))          # 9
print("Max:", max(arr, key=abs)) # using key function

# Reverse - O(n)
arr.reverse()                    # in-place
print("Reversed:", arr)

# Or using slicing (creates new list)
reversed_arr = arr[::-1]

# Rotate left by k - O(n)
def rotate_left(arr, k):
    k %= len(arr)
    return arr[k:] + arr[:k]

arr = [1, 2, 3, 4, 5]
print("Rotated left by 2:", rotate_left(arr, 2))  # [3, 4, 5, 1, 2]

# Two-pointer: find pair with given sum
def two_sum(arr, target):
    seen = {}
    for i, x in enumerate(arr):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i
    return []

print(two_sum([2, 7, 11, 15], 9))  # [0, 1]

Common Array Algorithms - JavaScript Example

const arr = [3, 1, 4, 1, 5, 9, 2, 6];

// Find max - O(n)
const max = Math.max(...arr);
console.log("Max:", max);  // 9

// Reverse - O(n)
const reversed = [...arr].reverse();  // non-destructive
console.log("Reversed:", reversed);

// Rotate left by k
function rotateLeft(arr, k) {
    k = k % arr.length;
    return [...arr.slice(k), ...arr.slice(0, k)];
}
console.log("Rotated:", rotateLeft([1,2,3,4,5], 2));  // [3,4,5,1,2]

// Two Sum - O(n)
function twoSum(arr, target) {
    const seen = new Map();
    for (let i = 0; i < arr.length; i++) {
        const complement = target - arr[i];
        if (seen.has(complement)) return [seen.get(complement), i];
        seen.set(arr[i], i);
    }
    return [];
}
console.log(twoSum([2, 7, 11, 15], 9));  // [0, 1]

Before you move on