Arrays — Complete Step-by-Step Guide

Module 2 — Basics, Traversal, Insertion, Deletion & Classic Problems Structured as Topic → Plain-English Explanation → Real Code → Visual Diagram → Complexity → Common Pitfalls.

---

1. Array Basics

An array is a collection of elements of the same type, stored in one contiguous block of memory, accessed using a numeric index that starts at 0. Because the elements sit back-to-back in memory, the computer can compute the exact physical memory address of any element directly from its index using the Base Address Formula:

$$\text{Address}(\text{arr}[i]) = \text{Base Address} + i \times \text{sizeof}(\text{DataType})$$

Because multiplication and addition are executed in a single CPU cycle, accessing any element is an instantaneous $O(1)$ constant-time operation — no searching required.

int arr[5] = {10, 20, 30, 40, 50};
cout << arr[2]; // 30 — jumps directly to index 2

• Complexity: Access — $O(1)$. Search (unsorted) — $O(n)$.

---

2. Traversal

Traversal means visiting every element of the array exactly once, typically with a loop, in order to read, print, or process each value. It is the single most common operation in array-based algorithms and the building block almost every other array algorithm is made from.

for (int i = 0; i < 5; i++) {
    cout << arr[i] << " ";
}

• Complexity: $O(n)$ — every element is visited exactly once.

---

3. Insertion & Deletion: Shifting Mechanics

Because array elements are packed tightly together in memory, inserting a new element in the middle requires physically shifting every element after it one position to the right to make room — and deleting an element requires shifting everything after it one position to the left to close the gap. This is why insertion and deletion in the middle of an array are $O(n)$ operations, even though reading an element is $O(1)$.

// Insert 99 at index 2 in {10, 20, 30, 40}
// shift 30, 40 right -> {10, 20, 99, 30, 40}
for (int i = n; i > 2; i--) {
    arr[i] = arr[i - 1];
}
arr[2] = 99;

• Complexity: Insertion/Deletion at the end — $O(1)$ amortized. In the middle or beginning — $O(n)$ due to shifting.

---

4. Classic Array Problems & Patterns

A handful of patterns recur constantly in array problems and interviews:

1. Reversing an Array: Swapping elements from both ends moving inward in $O(n)$ time and $O(1)$ space.
2. Finding the Max/Min: Scans once in $O(n)$, tracking the best value seen so far.
3. The Two-Pointer Technique: Uses two indices moving toward or away from each other — often on a sorted array — to solve problems like "find a pair that sums to a target" in $O(n)$ instead of the $O(n^2)$ brute force of checking every pair.

// Two-pointer: find a pair summing to target in a sorted array
int left = 0, right = n - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) {
        // found pair!
        break;
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}

---

5. Sliding Window & Kadane's Algorithm

The Sliding Window Pattern

Maintains a contiguous window $[L, R]$ over the array, expanding with $R$ and contracting with $L$ to compute running maximums, sums, or substrings in linear $O(n)$ time instead of nested $O(n^2)$ scans.

Kadane's Algorithm (Maximum Subarray Sum)

Calculates the maximum possible sum of any contiguous subarray in a single pass ($O(n)$ time, $O(1)$ space):

int maxSubArray(const vector<int>& nums) {
    int maxSoFar = nums[0], currentSum = nums[0];
    for (size_t i = 1; i < nums.size(); i++) {
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSoFar = max(maxSoFar, currentSum);
    }
    return maxSoFar;
}