📦 Arrays - The Foundation

🟢 Beginner Linear DS 60 min read

🎯 What is an Array?

An Array is a collection of elements stored at contiguous memory locations. Each element is identified by an index (starting from 0). Arrays are the most fundamental and widely used data structure.

📐 Memory Layout

Index:   0     1     2     3     4
      +-----+-----+-----+-----+-----+
Value |  10 |  20 |  30 |  40 |  50 |
      +-----+-----+-----+-----+-----+
Addr:  100   104   108   112   116
       ↑
arr[2] = *(100 + 2×4) = *(108) = 30

Contiguous memory enables O(1) access

🔑 Key Properties

Fixed size (in most languages) - PHP arrays are dynamic
Zero-indexed: First element at index 0
Random access: O(1) time to access any element
Homogeneous (typically): Same data type
Contiguous memory: Elements stored back-to-back

⚙️ Array Operations & Complexities

Operation	Time Complexity	Explanation
Access by Index	O(1)	Direct address calculation: base + index × size
Search (unsorted)	O(n)	Must scan all elements (Linear Search)
Search (sorted)	O(log n)	Binary Search possible on sorted arrays
Insert at End	O(1)	If space available; O(n) if resize needed
Insert at Beginning	O(n)	Must shift all elements right
Insert at Middle	O(n)	Shift elements after insertion point
Delete at End	O(1)	Just reduce size counter
Delete at Beginning	O(n)	Must shift all elements left
Update by Index	O(1)	Direct access + assignment
Traverse	O(n)	Visit every element once

🐘 Arrays in PHP 8

PHP's array is actually an ordered hash map - incredibly flexible. Let's see the different types:

Indexed Array

<?php
// Indexed (numeric) array
$fruits = ['Apple', 'Banana', 'Cherry', 'Date'];
// or: $fruits = array('Apple', 'Banana', 'Cherry', 'Date');

echo $fruits[0];    // Apple
echo $fruits[2];    // Cherry
echo count($fruits); // 4

// PHP 7.4+ spread operator
$more = ['Elderberry', ...$fruits];

Associative Array (Hash Map)

<?php
// Key-value pairs
$student = [
    'name'  => 'John Doe',
    'age'   => 21,
    'grade' => 'A',
    'courses' => ['DSA', 'DBMS', 'OS']
];

echo $student['name'];          // John Doe
echo $student['courses'][1];    // DBMS

// Check if key exists
if (array_key_exists('grade', $student)) {
    echo "Grade: {$student['grade']}";
}

Multidimensional Array

<?php
// 2D Array (Matrix)
$matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];

echo $matrix[1][2];  // 6 (row 1, col 2)

// Traverse 2D array
foreach ($matrix as $row) {
    foreach ($row as $cell) {
        echo $cell . ' ';
    }
    echo "\n";
}

🔧 Essential Array Algorithms

1. Linear Search (O(n))

function linearSearch(array $arr, int $target): int {
    foreach ($arr as $i => $value) {
        if ($value === $target) return $i;
    }
    return -1; // Not found
}

$arr = [10, 25, 30, 45, 50];
echo linearSearch($arr, 30); // 2

2. Binary Search (O(log n)) - Sorted Arrays Only

function binarySearch(array $arr, int $target): int {
    $low = 0;
    $high = count($arr) - 1;

    while ($low <= $high) {
        $mid = intdiv($low + $high, 2); // PHP 7+ intdiv

        if ($arr[$mid] === $target) return $mid;
        if ($arr[$mid] < $target) $low = $mid + 1;
        else $high = $mid - 1;
    }
    return -1;
}

$sorted = [10, 20, 30, 40, 50, 60, 70];
echo binarySearch($sorted, 40); // 3

📝 Binary Search Dry Run

Array: [10, 20, 30, 40, 50, 60, 70] | Target: 40

Step	Low	High	Mid	arr[mid]	Action
1	0	6	3	40	✅ Found at index 3!

Target: 25

Step	Low	High	Mid	arr[mid]	Action
1	0	6	3	40	40 > 25 → high = 2
2	0	2	1	20	20 < 25 → low=2
3	2	2	2	30	30 > 25 → high = 1
4	2	1	-	-	low > high → Not found (-1)

3. Array Reverse (In-Place, O(n))

function reverseArray(array &$arr): void {
    $left = 0;
    $right = count($arr) - 1;

    while ($left < $right) {
        // Swap arr[left] and arr[right]
        [$arr[$left], $arr[$right]] = [$arr[$right], $arr[$left]];
        $left++;
        $right--;
    }
}

$arr = [1, 2, 3, 4, 5];
reverseArray($arr);
print_r($arr); // [5, 4, 3, 2, 1]

4. Find Maximum Element (O(n))

function findMax(array $arr): int {
    $max = PHP_INT_MIN; // or $arr[0]
    foreach ($arr as $val) {
        if ($val > $max) $max = $val;
    }
    return $max;
}

5. Two Pointer Technique

// Check if array is palindrome
function isPalindrome(array $arr): bool {
    $left = 0;
    $right = count($arr) - 1;

    while ($left < $right) {
        if ($arr[$left] !== $arr[$right]) return false;
        $left++;
        $right--;
    }
    return true;
}

var_dump(isPalindrome([1, 2, 3, 2, 1])); // true
var_dump(isPalindrome([1, 2, 3, 4, 5])); // false

6. Array Rotation (O(n))

// Rotate array left by k positions
function rotateLeft(array $arr, int $k): array {
    $n = count($arr);
    $k = $k % $n; // Handle k > n
    // Slice and recombine
    return [...array_slice($arr, $k), ...array_slice($arr, 0, $k)];
}

$arr = [1, 2, 3, 4, 5];
print_r(rotateLeft($arr, 2)); // [3, 4, 5, 1, 2]

📊 Algorithm Complexity Reference

Algorithm	Time	Space	Requires Sorted?
Linear Search	O(n)	O(1)	No
Binary Search	O(log n)	O(1)	Yes
Reverse Array	O(n)	O(1)	No
Find Max/Min	O(n)	O(1)	No
Two Sum (Hash)	O(n)	O(n)	No
Two Sum (Two Pointer)	O(n)	O(1)	Yes
Merge Sorted Arrays	O(n+m)	O(n+m)	Yes
Remove Duplicates	O(n)	O(n)	No

💼 Interview Questions

$middleIndex = intdiv(count($arr), 2);
For odd-length: exact middle. For even-length: second middle element. O(1) time.

Math approach: Expected sum = n×(n+1)/2. Subtract actual sum.
function missingNumber($arr) { $n = count($arr); return $n*($n+1)/2 - array_sum($arr); }
O(n) time, O(1) space. Works because sum formula is O(1).

Kadane's Algorithm (O(n)): Track current sum and max sum. If current sum becomes negative, reset to 0.

function maxSubArray($arr) { $maxSoFar = $arr[0]; $currentMax = $arr[0]; for($i=1;$i<count($arr);$i++) { $currentMax = max($arr[$i], $currentMax+$arr[$i]); $maxSoFar = max($maxSoFar, $currentMax); } return $maxSoFar; }

⚠️ Common Mistakes

❌ Off-by-One Errors: Using <= instead of < in loops. Always verify bounds!

❌ Forgetting Sorted Requirement: Binary search only works on sorted arrays. Always sort first or use linear search.

❌ Modifying While Iterating: Don't add/remove elements while using foreach. Use array_filter or iterate backwards.

✅ Use PHP Built-ins: array_sum(), array_filter(), array_map() are optimized C implementations.

📝 Quick Quiz

Q1: What is the time complexity of accessing an array element by index?

O(n) O(1) O(log n) O(n²)

Q2: Binary Search requires the array to be:

Sorted Unsorted Reversed Has unique elements only

Q3: What does intdiv(7, 2) return in PHP?

3.5 3 4 2

Q4: What is the space complexity of swapping two array elements in-place?

O(1) O(n) O(log n) O(n²)

Q5: Which PHP function has O(1) complexity?

in_array() array_search() isset($arr[$key]) array_filter()

✏️ Practice Problems

Find Pivot Index

Easy

Find index where left sum equals right sum.

Solve →

Move Zeroes

Easy

Move all zeros to end while maintaining order.

Solve →

Product Except Self

Medium

Return array where each element is product of all others.

Solve →

Container With Most Water

Medium

Find two lines that form container with max water.

Solve →

First Missing Positive

Hard

Find smallest missing positive integer in O(n).

Solve →

Sliding Window Maximum

Hard

Find max in each sliding window of size k.

Solve →

📋 Arrays Cheat Sheet

Access	O(1)	`$arr[$index]`
Search (unsorted)	O(n)	Linear scan
Search (sorted)	O(log n)	Binary search
Insert End	O(1)*	`$arr[] = $val` (amortized)
Insert Begin	O(n)	`array_unshift()`
Delete End	O(1)	`array_pop()`
Delete Begin	O(n)	`array_shift()`
Sort	O(n log n)	`sort()`, `usort()`

Previous: Complexity Next: Strings

📦 Arrays - The Foundation

🎯 What is an Array?

📐 Memory Layout

🔑 Key Properties

⚙️ Array Operations & Complexities

🐘 Arrays in PHP 8

Indexed Array

Associative Array (Hash Map)

Multidimensional Array

🔧 Essential Array Algorithms

1. Linear Search (O(n))

2. Binary Search (O(log n)) - Sorted Arrays Only

📝 Binary Search Dry Run

3. Array Reverse (In-Place, O(n))

4. Find Maximum Element (O(n))

5. Two Pointer Technique

6. Array Rotation (O(n))

📊 Algorithm Complexity Reference

💼 Interview Questions

Basic: How do you find the middle element of an array?

Intermediate: Find the missing number in array [0..n]?

Advanced: Implement Kadane's Algorithm for Maximum Subarray.

⚠️ Common Mistakes

📝 Quick Quiz

✏️ Practice Problems

Find Pivot Index

Move Zeroes

Product Except Self

Container With Most Water

First Missing Positive

Sliding Window Maximum

📋 Arrays Cheat Sheet