🎒 Array Mastery: Your Adventure Through Array Operations

Imagine you have a magical backpack with numbered pockets. Each pocket holds one treasure. That’s an array! Let’s explore all the cool tricks you can do with it.

🧱 Arrays Fundamentals

What is an Array?

Think of an array like a train with numbered cars. Each car (pocket) has a number starting from 0, and each car holds one item.

# A train with 5 cars
treasures = [10, 20, 30, 40, 50]
#            0   1   2   3   4  ← car numbers

Why start at 0? The computer counts from 0, just like floors in a building starting from “Ground” (0)!

Accessing Elements

Want the treasure in car 2? Just ask!

print(treasures[2])  # Output: 30

Changing Values

Found a better treasure? Swap it in!

treasures[2] = 99
# Now: [10, 20, 99, 40, 50]

Array Length

How many cars in the train?

print(len(treasures))  # Output: 5

🚶 Array Traversal and Manipulation

Walking Through Every Car

Imagine you’re a ticket collector walking through every train car.

treasures = [10, 20, 30, 40, 50]

# Visit every car
for item in treasures:
    print(item)

Using Index Numbers

Sometimes you need the car NUMBER too:

for i in range(len(treasures)):
    print(f"Car {i}: {treasures[i]}")

Common Manipulations

📊 Prefix Sum Arrays

The Magic of Running Totals

Imagine you’re counting coins as you walk. At each step, you note the total coins so far.

Story: You pick up coins: [3, 1, 4, 1, 5]

Prefix Sum Array: [3, 4, 8, 9, 14]

def build_prefix_sum(arr):
    prefix = [0] * len(arr)
    prefix[0] = arr[0]
    for i in range(1, len(arr)):
        prefix[i] = prefix[i-1] + arr[i]
    return prefix

coins = [3, 1, 4, 1, 5]
print(build_prefix_sum(coins))
# Output: [3, 4, 8, 9, 14]

Super Power: Range Sum in O(1)

Want sum from index 2 to 4? Formula: prefix[4] - prefix[1] = 14 - 4 = 10

def range_sum(prefix, left, right):
    if left == 0:
        return prefix[right]
    return prefix[right] - prefix[left - 1]

📈 Difference Arrays

The Opposite of Prefix Sum

Difference arrays are like recording changes between neighbors.

Original: [2, 5, 9, 12, 15] Differences: [2, 3, 4, 3, 3]

How? Each element = current - previous (first stays same)

def build_diff_array(arr):
    diff = [arr[0]]
    for i in range(1, len(arr)):
        diff.append(arr[i] - arr[i-1])
    return diff

Super Power: Range Updates in O(1)

Add 5 to indices 1-3? Instead of updating 3 elements:

def range_update(diff, left, right, val):
    diff[left] += val
    if right + 1 < len(diff):
        diff[right + 1] -= val

Rebuild with prefix sum to get the result!

✖️ Product of Array Except Self

The Puzzle

Given [1, 2, 3, 4], create an array where each position has the product of all OTHER numbers.

Result: [24, 12, 8, 6]

• Position 0: 2×3×4 = 24
• Position 1: 1×3×4 = 12
• Position 2: 1×2×4 = 8
• Position 3: 1×2×3 = 6

The Clever Trick: Left and Right Products

graph TD
    A[Build Left Products] --> B[Build Right Products]
    B --> C[Multiply Left × Right]

def product_except_self(nums):
    n = len(nums)
    result = [1] * n

    # Left products
    left = 1
    for i in range(n):
        result[i] = left
        left *= nums[i]

    # Right products
    right = 1
    for i in range(n-1, -1, -1):
        result[i] *= right
        right *= nums[i]

    return result

🏆 Kadane’s Algorithm

The Hero’s Quest for Maximum Sum

The Story: You walk through a path of gold (+) and traps (-). Find the best stretch to collect maximum gold!

graph TD
    A[Start Fresh OR Continue?] --> B{Current + previous > Current alone?}
    B -->|Yes| C[Keep growing subarray]
    B -->|No| D[Start new subarray here]
    C --> E[Update max if bigger]
    D --> E

The Golden Rule

At each step, ask: “Should I continue my journey or start fresh here?”

def kadane(arr):
    max_ending_here = arr[0]
    max_so_far = arr[0]

    for i in range(1, len(arr)):
        # Continue or restart?
        max_ending_here = max(
            arr[i],
            max_ending_here + arr[i]
        )
        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

💰 Maximum Subarray Sum

Kadane in Action

Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Let’s walk through:

Answer: Maximum sum = 6 (subarray [4, -1, 2, 1])

🚀 Maximum Product Subarray

A Trickier Challenge

Products are sneaky! Two negatives make a positive.

Array: [2, 3, -2, 4]

• [2, 3] = 6
• But wait… we can’t use [-2, 4] after that

Array: [-2, 3, -4]

• -2 × 3 × -4 = 24 ← Negatives cancel!

The Secret: Track BOTH Min and Max

def max_product(nums):
    max_prod = nums[0]
    min_prod = nums[0]
    result = nums[0]

    for i in range(1, len(nums)):
        num = nums[i]

        # Swap if negative (flips min/max)
        if num < 0:
            max_prod, min_prod = min_prod, max_prod

        max_prod = max(num, max_prod * num)
        min_prod = min(num, min_prod * num)

        result = max(result, max_prod)

    return result

Why Track Minimum?

A big negative × a negative = a big positive!

Example: [-10, -2, 5]

• Min so far at index 1: -10 × -2 = 20
• That 20 becomes our max!

🎯 Quick Summary

🌟 You Did It!

You’ve mastered the fundamental array operations! These patterns appear everywhere:

• Prefix sums → Running totals, range queries
• Difference arrays → Efficient batch updates
• Kadane’s → Stock prices, game scores
• Product subarray → Risk calculations

Now go practice! Every expert was once a beginner who never gave up. 💪