CodeShop
30 Days of LeetCode: Day 3 - The Power of a Single Pointer

30 Days of LeetCode: Day 3 - The Power of a Single Pointer

Raphael Smith's photo
Raphael Smith
·

3 min read

Today's LeetCode challenge taught me a valuable lesson about the elegance of simple solutions. The problem seemed complex at first: remove duplicates from a sorted array while allowing each element to appear at most twice. But the solution hinged on understanding one crucial concept - the power of a single pointer.

The Challenge

The task was to modify a sorted array “in-place”(there’s that term again!) so that each element appears at most twice, keeping the relative order of elements the same. For example:

Input: [1,1,1,2,2,3] Output: [1,1,2,2,3,_] (return 5)

At first, I thought about using booleans and counters to track duplicate occurrences. But a simpler solution used just one pointer, 'k', that served multiple purposes.

The 'k' Pointer Magic

The solution centered around a pointer 'k' that started at index 2. This single pointer cleverly handled three tasks:

  1. Started at 2 because we automatically keep the first two occurrences of any number

  2. Served as a placement pointer - showing where to put the next valid number

  3. Let us check previous occurrences by looking at k-2

let k = 2;  // Start at third position
for (let i = 2; i < nums.length; i++) {
    if (nums[i] !== nums[k-2]) {
        nums[k] = nums[i];
        k++;
    }
}

The Aha Moment

My breakthrough came when I understood why k-2 works. By comparing the current number with the number two positions back from our placement pointer, we could determine if we'd already kept two occurrences of a number. No need for extra variables or complex tracking!

Real-World Business Application

Consider an e-commerce platform's shopping cart system that has a "2 items maximum" policy for flash sales:

Imagine a hot sale where:

  • Each customer can only buy maximum 2 of any item

  • Items are added to cart in order of selection

  • System must efficiently track/limit quantities

  • Thousands of customers are shopping simultaneously

Example scenario:

CopyCustomer adds items: [PS5, PS5, PS5, Xbox, Xbox, Switch]
System maintains: [PS5, PS5, Xbox, Xbox, Switch]

Just like our pointer solution:

  1. The system automatically allows first two of any item

  2. It tracks position for next valid item

  3. Keeps original selection order

  4. Efficiently handles duplicates without extra tracking

Key Takeaways

  1. Sometimes the simplest solution is the most elegant

  2. A single variable can serve multiple purposes

  3. In-place modification doesn't always need complex swapping or tracking

  4. The order of elements in a problem can make certain solutions possible (sorted array in this case)

This problem taught me to look for elegant solutions that might not be immediately obvious. Sometimes, what seems like a complex tracking problem can be solved with just one well-placed pointer.

Tomorrow brings another challenge, but today's lesson about simple solutions will stick with me.

JavaScriptleetcodealgorithms