The O(n) Club: LeetCode 670 Maximum Swap — Greedy Digit Hustle Unleashed

The O(n) Club: LeetCode 670 Maximum Swap — Greedy Digit Hustle Unleashed

⚡ TL;DR

Got a non-negative integer? Swap two digits (once) to get the biggest number you can. Brute force tries every pair like it’s got nothing better to do, but the smart crowd does it in O(n):

// Please, don't brute force this in production:
public int maximumSwap(int num) {
    char[] arr = String.valueOf(num).toCharArray();
    int max = num;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            char tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
            max = Math.max(max, Integer.parseInt(new String(arr)));
            tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    return max;
}

🧠 How Devs Usually Mess This Up

Most folks fall for the classic: “Swap any time you spot a bigger digit to the right!” But swapping at the first sign of hope is how you end up with a tepid result, not a chart-topper. Others burn time swapping every pair (hello, O(n²) and interviewer yawns). Pro-tip: the first chance to upgrade isn’t always the best one. Also: sorting the digits? That’s cheating and the problem police will find you.

🔍 What’s Actually Going On

Think of your number as a conga line where the biggest, flashiest dancers should be right up front. Your goal: locate the first spot where some wallflower (smaller digit) is blocking a party monster (larger digit) from the right. And here’s the real twist: if that bigger digit shows up more than once to the right, always swap with its last occurrence. That way, your biggest star gets closer to the front, and your number gets maximum runway. It’s maximum swap, not maximum fumble.

🛠️ PseudoCode

• Convert your number to a character array. (Doing this with pure arithmetic is Java masochism.)
• Make an int array last[10] to hold the rightmost index of every digit (0-9):

  char[] arr = String.valueOf(num).toCharArray();
  int[] last = new int[10];
  for (int i = 0; i < arr.length; i++) {
      last[arr[i] - '0'] = i;
  }

• Loop left to right. For each position i (digit d):
  • For x = 9 down to d + 1:
  • If last[x] > i, swap digits at i and last[x], then break (one swap per customer!).
• Parse arr back to int and return.

• If you can’t improve (already maxed), just hand the original number back.

💻 The Code

public int maximumSwap(int num) {
    char[] arr = String.valueOf(num).toCharArray();
    int[] last = new int[10]; // rightmost position for each digit
    for (int i = 0; i < arr.length; i++) {
        last[arr[i] - '0'] = i;
    }
    for (int i = 0; i < arr.length; i++) {
        int d = arr[i] - '0';
        for (int x = 9; x > d; x--) {
            if (last[x] > i) {
                char tmp = arr[i];
                arr[i] = arr[last[x]];
                arr[last[x]] = tmp;
                return Integer.parseInt(new String(arr));
            }
        }
    }
    return num;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• No swap needed: Already descending order? 1-swap can’t help. Just return the original number and look smug.
• Single-digit numbers (and friendly zeros): No swap, no gain, but at least you didn’t mess up the input.
• Swapping with the first rather than the last occurrence of a high digit? Rookie mistake; costs you points (and digits higher in the number = bigger swing).
• Don’t brute force. This O(n) trick passes recruiter lightning-rounds and keeps your codebase running in the real world.

🧠 Interviewer Brain-Tattoo

“In the club of digits, the biggest number always cuts the velvet rope—just once is all you need.”