Array Mastery: In-place Manipulation 🎯

The Magic of Rearranging Without Extra Space

Imagine you have a toy box with limited space. You want to organize your toys, but you can’t get another box. You have to move toys around inside the same box. That’s what in-place manipulation means in programming!

In-place = Fixing things right where they are, without needing extra room.

🌈 The Dutch National Flag Algorithm

The Story of Three-Color Sorting

Picture this: You have a bag of marbles — red, white, and blue. You want to arrange them so all reds come first, then whites, then blues. But here’s the catch: you can only swap marbles inside the bag!

This is the Dutch National Flag problem, named after the Netherlands flag (red, white, blue stripes).

How Does It Work?

Think of three invisible helpers standing at different positions:

🔴 LOW helper: "I guard where reds end"
⚪ MID helper: "I'm checking each marble"
🔵 HIGH helper: "I guard where blues start"

The Simple Rules

1. MID looks at current marble
2. If it’s RED → swap with LOW, move both LOW and MID forward
3. If it’s WHITE → just move MID forward
4. If it’s BLUE → swap with HIGH, move HIGH backward

Visual Example

Start:  [🔵, 🔴, ⚪, 🔴, 🔵, ⚪]
         L,M              H

Step 1: Blue? Swap with HIGH!
        [⚪, 🔴, ⚪, 🔴, 🔵, 🔵]
         L,M           H

Step 2: White? Move MID forward
        [⚪, 🔴, ⚪, 🔴, 🔵, 🔵]
         L   M        H

Step 3: Red? Swap with LOW, move both
        [🔴, ⚪, ⚪, 🔴, 🔵, 🔵]
             L   M     H

...continue until MID passes HIGH...

Final:  [🔴, 🔴, ⚪, ⚪, 🔵, 🔵]

JavaScript Code

function dutchFlag(arr) {
  let low = 0;
  let mid = 0;
  let high = arr.length - 1;

  while (mid <= high) {
    if (arr[mid] === 0) {        // Red
      [arr[low], arr[mid]] = [arr[mid], arr[low]];
      low++; mid++;
    } else if (arr[mid] === 1) { // White
      mid++;
    } else {                      // Blue
      [arr[mid], arr[high]] = [arr[high], arr[mid]];
      high--;
    }
  }
  return arr;
}

Why Is This Magic?

• One pass through the array (super fast!)
• No extra space needed
• Time: O(n), Space: O(1)

🗳️ Boyer-Moore Voting Algorithm

The Story of Finding the King

Imagine a village election. Everyone votes by shouting their choice. You need to find who got more than half the votes — the majority.

But here’s the twist: You can only remember one name and one count!

The Clever Trick

Think of it like a battle:

1. Pick the first voter’s choice as your candidate
2. Give them 1 point
3. For each new vote:
   • Same choice? Add 1 point
   • Different choice? Subtract 1 point
4. If points hit zero, the next voter becomes the new candidate

Why Does This Work?

The majority appears more than half the time. Even if everyone else teams up against them, the majority still has more “soldiers”!

Visual Example

Votes: [👑, 🎩, 👑, 👑, 🎩, 👑, 👑]

Step 1: 👑 → candidate=👑, count=1
Step 2: 🎩 → different! count=0
Step 3: 👑 → count=0, new candidate=👑, count=1
Step 4: 👑 → same! count=2
Step 5: 🎩 → different! count=1
Step 6: 👑 → same! count=2
Step 7: 👑 → same! count=3

Winner: 👑 (appears 5 times out of 7!)

JavaScript Code

function findMajority(arr) {
  let candidate = null;
  let count = 0;

  // Phase 1: Find candidate
  for (let num of arr) {
    if (count === 0) {
      candidate = num;
    }
    count += (num === candidate) ? 1 : -1;
  }

  // Phase 2: Verify (optional)
  count = arr.filter(x => x === candidate).length;
  return count > arr.length / 2 ? candidate : null;
}

The Beauty

• Time: O(n) — just one loop!
• Space: O(1) — only two variables!
• Works like magic ✨

🧹 Remove Duplicates from Sorted Array

The Story of the Careful Librarian

Imagine a librarian arranging books on a shelf. The books are already sorted by title, but there are duplicate copies. The librarian wants to keep only one copy of each book — without using another shelf!

The Two-Finger Method

Use two fingers (pointers):

📍 SLOW finger: Points to the last unique book
👆 FAST finger: Scans through all books

The Simple Rule

• FAST finds a new book? Put it next to SLOW, then move SLOW forward
• FAST finds a duplicate? Just skip it!

Visual Example

Books: [A, A, B, B, B, C, D, D]
        S
        F

Fast sees 'A' (same as Slow) → skip
        [A, A, B, B, B, C, D, D]
        S  F

Fast sees 'B' (new!) → copy to Slow+1
        [A, B, B, B, B, C, D, D]
           S  F

Fast sees 'B' (same) → skip
Fast sees 'B' (same) → skip
        [A, B, B, B, B, C, D, D]
           S        F

Fast sees 'C' (new!) → copy to Slow+1
        [A, B, C, B, B, C, D, D]
              S        F

Fast sees 'D' (new!) → copy to Slow+1
        [A, B, C, D, B, C, D, D]
                 S           F

Done! First 4 elements are unique: [A, B, C, D]

JavaScript Code

function removeDuplicates(arr) {
  if (arr.length === 0) return 0;

  let slow = 0;

  for (let fast = 1; fast < arr.length; fast++) {
    if (arr[fast] !== arr[slow]) {
      slow++;
      arr[slow] = arr[fast];
    }
  }

  return slow + 1; // Length of unique elements
}

Why So Efficient?

• One pass through the array
• No extra array needed
• Time: O(n), Space: O(1)

🎪 Move Zeroes

The Story of the Party Organizer

You’re organizing a party line. Some guests arrived (non-zero), but some spots are empty (zeros). You want all guests to move to the front, keeping their order, and empty spots go to the back!

The Snowplow Method

Imagine a snowplow pushing snow (zeros) to the end:

🚜 WRITE pointer: Where the next guest should stand
👀 READ pointer: Scanning the whole line

The Simple Rule

• See a guest (non-zero)? Place them at WRITE position, move WRITE forward
• See an empty spot (zero)? Skip it!
• At the end, fill remaining spots with zeros

Visual Example

Line: [0, 1, 0, 3, 12]
       W
       R

R sees 0 → skip
      [0, 1, 0, 3, 12]
       W  R

R sees 1 → write at W, move W
      [1, 1, 0, 3, 12]
          W  R

R sees 0 → skip
      [1, 1, 0, 3, 12]
          W     R

R sees 3 → write at W, move W
      [1, 3, 0, 3, 12]
             W     R

R sees 12 → write at W, move W
      [1, 3, 12, 3, 12]
                 W     R

Fill remaining with zeros:
      [1, 3, 12, 0, 0]

JavaScript Code

function moveZeroes(arr) {
  let write = 0;

  // Move non-zeros forward
  for (let read = 0; read < arr.length; read++) {
    if (arr[read] !== 0) {
      arr[write] = arr[read];
      write++;
    }
  }

  // Fill rest with zeros
  while (write < arr.length) {
    arr[write] = 0;
    write++;
  }

  return arr;
}

Alternative: Swap Method

function moveZeroesSwap(arr) {
  let write = 0;

  for (let read = 0; read < arr.length; read++) {
    if (arr[read] !== 0) {
      [arr[write], arr[read]] = [arr[read], arr[write]];
      write++;
    }
  }

  return arr;
}

Why This Rocks

• Order preserved for non-zero elements
• Time: O(n), Space: O(1)
• Elegant and simple!

🎯 The Big Picture

All four algorithms share a secret:

graph TD
    A[In-place Manipulation] --> B[Use Pointers]
    B --> C[No Extra Arrays]
    C --> D[O#40;1#41; Space]
    D --> E[Swap or Overwrite]

Quick Comparison

💡 Key Takeaways

1. Pointers are your friends — they help navigate without extra space
2. Swapping is powerful — rearrange without copying
3. One pass is possible — think cleverly!
4. Sorted arrays are easier — duplicates are neighbors

Remember: In-place means working with what you have. Like a chef who makes a feast using only what’s in the kitchen — no grocery runs allowed! 🍳

🚀 Practice Time!

Try these on your own:

1. Sort [2, 0, 1, 2, 1, 0] using Dutch Flag
2. Find majority in [3, 3, 4, 2, 3, 3, 3]
3. Remove duplicates from [1, 1, 2, 2, 3]
4. Move zeros in [0, 0, 1, 0, 2]

You’ve got this! 🎉