The O(n) Club: Reverse String (LeetCode 344) for the Two-Pointer Skeptics

The O(n) Club: Reverse String (LeetCode 344) for the Two-Pointer Skeptics

⚡ TL;DR

Reverse a char array? Grab a pointer for each end, swap until they meet, and whatever you do—don’t return anything. Two-pointer street magic, Java style:

// Java quick-and-grumpy version
void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {
        char temp = s[left];
        s[left++] = s[right];
        s[right--] = temp;
    }
}

🧠 How Devs Usually Mess This Up

If you thought “Why not just use .reverse(), or maybe return s after I’ve made a shiny new array?”—congratulations, that’s how half the internet misses the point. This problem bans:

• Returning anything (seriously, stop it—interviewers want void and vibes, not fresh arrays).
• Strings instead of arrays: Java’s String is more locked down than a production database Friday at 5pm. You get char[]—embrace it.
• Helper methods like .reverse(), Arrays.copyOf(), or StringBuilder. If you use them, the job gets done, but also, you fail the technical vibe check.
• Recursion for showmanship: Space complexity nightmares just so you can say ‘recursion.’

🔍 What’s Actually Going On

Imagine reversing a conga line without anyone leaving. You grab the hands on the left and right ends, swing them into each other’s spots, and slide inward. No fancy tools; just two pointers and willingness to get your array’s hands dirty (metaphorically—arrays don’t sweat). That’s all: swap, shuffle, done. Going in-place means your algorithm is a memory minimalist, not an array hoarder.

🛠️ PseudoCode

• 1. Set left and right pointers: left = 0, right = s.length - 1
• 2. While left < right:
  • Swap s[left] with s[right]
  • Move left right, right left
• 3. Stop at or after the great pointer handshake (when left >= right).

// Java-flavored algorithm
int left = 0, right = s.length - 1;
while (left < right) {
    // swap elements
    char temp = s[left];
    s[left] = s[right];
    s[right] = temp;
    left++;
    right--;
}
// No need to return, you already messed up the input array.

• Edge case? Odd-length arrays just leave their awkward middle guy sitting pretty. Zero or one element? Still works—the while loop politely ignores redundancy.

💻 The Code

// Java - Two pointers, infinite confidence
public void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Returning the array: You had one job: mutate in place, not invent a new array empire.
• Swapping in-place: Two pointers only. Any auxiliary array means you just invented value-cloning for no reason.
• String errors in Java: String can’t be changed. Mutate char[] only. Save string wizardry for your poetry.
• Runtime and space: O(n) time (since you swing through every element once), O(1) space (since you use a couple variables, and not a suitcase of new arrays).

🧠 Interviewer Brain-Tattoo

“If your reverseString uses extra memory or returns anything at all, your interviewer’s palm will meet their face faster than your pointers ever meet in the middle.”