🎒 Array Mastery: Your Backpack of Superpowers

Imagine you have a magical backpack with numbered pockets. Each pocket holds one treasure. That’s an array! Let’s master the secret tricks to make your backpack work like magic.

📦 Arrays Fundamentals: Your Numbered Treasure Boxes

What’s an Array?

Think of a row of mailboxes at an apartment. Each mailbox has:

• A number (index) starting from 0
• One item inside (the value)

// A row of fruit boxes
let fruits = ["🍎", "🍌", "🍇", "🍊"];
//  index:      0      1      2      3

// Get the banana (box #1)
console.log(fruits[1]); // "🍌"

Why Start at 0?

The computer counts from the start line, not the first box. Box 0 is right at the start!

let scores = [100, 85, 90];
// Position:    0    1    2

scores[0] // First score: 100
scores[2] // Last score: 90

Creating Arrays

// Empty backpack
let empty = [];

// Backpack with 5 numbers
let nums = [1, 2, 3, 4, 5];

// Mix of treasures
let mix = ["hello", 42, true];

🚶 Array Traversal and Manipulation: Walking Through Your Boxes

The Walk-Through (Traversal)

Imagine you’re a mail carrier. You must visit every single mailbox, one by one, from first to last.

let colors = ["red", "blue", "green"];

// Visit each box
for (let i = 0; i < colors.length; i++) {
  console.log(colors[i]);
}
// Prints: red, blue, green

The Magic For-Of Loop

An easier way to walk through:

let pets = ["dog", "cat", "fish"];

for (let pet of pets) {
  console.log("I have a " + pet);
}

Manipulation: Changing Your Boxes

Add to the end (like adding a caboose):

let train = [1, 2, 3];
train.push(4); // [1, 2, 3, 4]

Remove from the end:

train.pop(); // Returns 4, train is [1, 2, 3]

Add to the start:

train.unshift(0); // [0, 1, 2, 3]

Remove from the start:

train.shift(); // Returns 0, train is [1, 2, 3]

➕ Prefix Sum Arrays: The Running Total Trick

The Story

Imagine you’re counting coins as you walk past piggy banks. At each bank, you write down: “How many coins have I seen SO FAR?”

Piggy banks:  [3, 1, 4, 2]
Running total: [3, 4, 8, 10]
              (3)(3+1)(3+1+4)(3+1+4+2)

Why Is This Magic?

Question: How many coins from bank 1 to bank 3?

Without prefix sum: Add 1 + 4 + 2 = 7 (slow!)

With prefix sum: Just do 10 - 3 = 7 (instant!)

Building a Prefix Sum

let nums = [3, 1, 4, 2];
let prefix = [nums[0]]; // Start: [3]

for (let i = 1; i < nums.length; i++) {
  prefix[i] = prefix[i-1] + nums[i];
}
// prefix = [3, 4, 8, 10]

Quick Range Sum Formula

Sum from index L to R:

// sum = prefix[R] - prefix[L-1]
// (if L is 0, just use prefix[R])

➖ Difference Arrays: The Change Tracker

The Story

You’re a teacher with a class seating chart. Instead of writing everyone’s new seat, you just write “move 2 spots right” or “move 1 spot left.”

A difference array stores the change between neighbors, not the actual values.

Original:   [2, 5, 8, 3]
Difference: [2, 3, 3, -5]
           (start)(5-2)(8-5)(3-8)

The Superpower: Bulk Updates!

Problem: Add 5 to every element from index 1 to 3.

Slow way: Change each one: arr[1]+=5, arr[2]+=5, arr[3]+=5

Fast way with difference array: Only 2 changes!

diff[1] += 5;    // Start adding 5 here
diff[4] -= 5;    // Stop adding 5 here

Building Back the Original

let diff = [2, 3, 3, -5];
let original = [diff[0]]; // [2]

for (let i = 1; i < diff.length; i++) {
  original[i] = original[i-1] + diff[i];
}
// original = [2, 5, 8, 3]

✖️ Product of Array Except Self

The Puzzle

Given [1, 2, 3, 4], create a new array where each spot holds the product of ALL other numbers.

Result: [24, 12, 8, 6]

• Position 0: 2×3×4 = 24 (everything except 1)
• Position 1: 1×3×4 = 12 (everything except 2)
• Position 2: 1×2×4 = 8 (everything except 3)
• Position 3: 1×2×3 = 6 (everything except 4)

The Clever Trick: Left × Right

For each position, multiply:

• Everything to the left
• Everything to the right

let nums = [1, 2, 3, 4];

// Left products: [1, 1, 2, 6]
// (nothing, 1, 1×2, 1×2×3)

// Right products: [24, 12, 4, 1]
// (2×3×4, 3×4, 4, nothing)

// Answer: left × right at each spot
// [1×24, 1×12, 2×4, 6×1] = [24, 12, 8, 6]

The Code

function productExceptSelf(nums) {
  let n = nums.length;
  let result = new Array(n).fill(1);

  // Left pass
  let left = 1;
  for (let i = 0; i < n; i++) {
    result[i] = left;
    left *= nums[i];
  }

  // Right pass
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= right;
    right *= nums[i];
  }

  return result;
}

🏆 Kadane’s Algorithm: The Happiness Tracker

The Story

Imagine you’re walking through a theme park. Some rides give you joy points (+3), others take them away (-2). You want to find the best stretch that gives you the most joy!

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

The Rule

At each ride, ask yourself:

“Should I continue my happy streak, or start fresh here?”

Pick whichever is bigger!

The Flow

graph TD
    A[Start with first number] --> B[Walk to next number]
    B --> C{Current + Previous OR Just Current?}
    C -->|Previous helps| D[Keep the streak going]
    C -->|Fresh start better| E[Start new streak here]
    D --> F[Update best if this is highest]
    E --> F
    F --> B

The Code

function kadane(nums) {
  let maxCurrent = nums[0];
  let maxGlobal = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Should I continue or start fresh?
    maxCurrent = Math.max(
      nums[i],           // Start fresh
      maxCurrent + nums[i] // Continue
    );

    // Is this my new record?
    maxGlobal = Math.max(maxGlobal, maxCurrent);
  }

  return maxGlobal;
}

kadane([-2, 1, -3, 4, -1, 2, 1, -5, 4]);
// Returns 6 (from [4, -1, 2, 1])

📈 Maximum Subarray Sum

This IS Kadane’s Algorithm in action!

The Challenge

Find the contiguous subarray with the largest sum.

Array: [−2, 1, −3, 4, −1, 2, 1, −5, 4]
Answer: 6 (the subarray [4, −1, 2, 1])

Step-by-Step Trace

The magic window [4, -1, 2, 1] wins with sum = 6!

📉 Maximum Product Subarray

The Twist

Now we’re multiplying, not adding! And here’s the trick: negative × negative = positive!

Array: [2, 3, -2, 4]
Answer: 6 (from [2, 3])

But wait…

Array: [−2, 3, −4]
Answer: 24 (from [-2, 3, -4])

Two negatives made a positive!

The Double-Track Strategy

Keep track of both:

• Maximum so far (could become bigger)
• Minimum so far (negative, but could flip to huge positive!)

function maxProduct(nums) {
  let maxProd = nums[0];
  let minProd = nums[0];
  let result = nums[0];

  for (let i = 1; i < nums.length; i++) {
    let curr = nums[i];

    // The magic swap: negative flips everything!
    let tempMax = Math.max(
      curr,
      maxProd * curr,
      minProd * curr
    );

    minProd = Math.min(
      curr,
      maxProd * curr,
      minProd * curr
    );

    maxProd = tempMax;
    result = Math.max(result, maxProd);
  }

  return result;
}

maxProduct([2, 3, -2, 4]); // 6
maxProduct([-2, 3, -4]);   // 24

The Key Insight

graph TD
    A[Current Number] --> B{Is it negative?}
    B -->|Yes| C[Previous minimum could become maximum!]
    B -->|No| D[Previous maximum stays maximum]
    C --> E[Swap max and min logic]
    D --> F[Normal multiplication]

🎯 Summary: Your Array Superpowers

You now have the keys to array mastery! Each technique is a tool in your backpack. The more you practice, the faster you’ll know which tool to grab. Happy coding! 🚀