CMD Guide
Home › DSA › Company Practice

medium Maximum Swap

Problem Statement

Given a non-negative integer num, return the maximum number, which you can create by swapping any two digits of the number only once. If no swaps can improve the number, return the original number.

Examples

  1. Example 1:

    • Input: 2736
    • Expected Output: 7236
    • Justification: Swapping the first and second digits (2 and 7) results in the largest possible number.

  2. Example 2:

    • Input: 9965
    • Expected Output: 9965
    • Justification: The number is already in its maximum form, so no swap is needed.

  3. Example 3:

    • Input: 7281912
    • Expected Output: 9281712
    • Justification: Swapping the first digit (7) with the first 9 found from the left results in the maximum number.

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Maximum Swap (medium)

1. Why / judgment

At most one swap of two digits to maximize the number. Greedy: find the leftmost position that is smaller than some digit to its right; swap it with the rightmost occurrence of the maximum digit to its right. Implementation: record last index of each digit 0-9; scan left to right; for each position try digits 9 down to current+1 if a later index exists. When-NOT: unlimited swaps -> sort digits descending.

2. Big-O derivation (K11)

Digits d for the number; last[] fill O(d); scan O(d*10)=O(d).
Time O(d), space O(1).
2736->7236; 9965 already max; 7281912->9281712.

3. Pattern + when-NOT (K12)

Name: ONE-SWAP MAXIMIZE DIGITS (GREEDY LAST-OCCURRENCE)

Recognition: non-negative int; at most 1 swap of two digit positions; maximize value.

When-NOT: k swaps -> more complex greedy. Any permutations -> sort desc. Lexicographic string with other constraints -> different.

4. Edge hand-run (K13)

single digit -> itself
sorted descending -> no swap
ties: prefer rightmost max (standard LC choice)

5. Interviewer follow-ups (model answers)

Q1. Why rightmost occurrence of the max digit?
A: Using rightmost keeps optimal for single swap and matches accepted answers.

Q2. Is adjacent bubble one pass enough?
A: No — need global max to the right, not only adjacent swap.

Q3. Leading zeros?
A: num is integer so no leading zero in input; after swap still same length digit string.

6. Short drills

Drill: 1993 -> 9913
Drill: 98368 -> 98863
Drill: prove sorted-desc needs 0 swaps.
✅ Solution Maximum Swap

Problem Statement

Given a non-negative integer num, return the maximum number, which you can create by swapping any two digits of the number only once. If no swaps can improve the number, return the original number.

Examples

  1. Example 1:

    • Input: 2736
    • Expected Output: 7236
    • Justification: Swapping the first and second digits (2 and 7) results in the largest possible number.

  2. Example 2:

    • Input: 9965
    • Expected Output: 9965
    • Justification: The number is already in its maximum form, so no swap is needed.

  3. Example 3:

    • Input: 7281912
    • Expected Output: 9281712
    • Justification: Swapping the first digit (7) with the first 9 found from the left results in the maximum number.

Solution

To solve this problem, the approach revolves around identifying the most significant digit that can be increased by a swap. We traverse the number from right to left, identifying the largest digit seen so far and its index. This is because a larger digit appearing later in the number, when swapped with a smaller digit to its left, will yield a greater value. The key is to find the leftmost digit for which a larger digit exists anywhere to its right. Swapping these two digits will result in the maximum possible number. This approach is effective as it minimizes the swaps and ensures the largest digit possible in the highest place value.

Step-by-Step Algorithm

  1. Convert the given number into an array of its digits for easier manipulation.

  2. Prepare the maxIndexAfter Array:

    • Initialize an array maxIndexAfter to record the index of the maximum digit found to the right of each digit (including itself).
    • Traverse the digit array from right to left.
    • Update maxIndexAfter for each position with the index of the largest digit seen so far.

  3. Perform the Swap:

    • Traverse the digits array from left to right.
    • If digits[i] and digits[maxIndexAfter[i]] are not same, swap both elements.
    • After the first swap, break the loop.

  4. Reconstruct the Number: Convert the digit array back into a single integer.

  5. Return the Result: Provide the modified number as the output.

Algorithm Walkthrough

Consider the Input 7281912.

  1. Initialization:

    • Convert to digit array: [7, 2, 8, 1, 9, 1, 2].
    • Initialize maxIndexAfter array with the same length as the digit array.

  2. Preparing the maxIndexAfter Array:

    • Start from the rightmost digit.
    • Iteration 1 (Index 6): Digit 2, maxIndexAfter[6] = 6.
    • Iteration 2 (Index 5): Digit 1, maxIndexAfter[5] = 6 (as 2 is the maximum seen so far).
    • Iteration 3 (Index 4): Digit 9, maxIndexAfter[4] = 4.
    • Continue updating maxIndexAfter for each digit.
    • Final maxIndexAfter array: [4, 4, 4, 4, 4, 6, 6].

  3. Performing the Swap:

    • Traverse from left to right.
    • Iteration 1 (Index 0): Digit 7, compare with maxIndexAfter[0] (digit at index 4 which is 9), so swap them.
    • As soon as the first swap opportunity is found, break the loop.
    • Array after swap: [9, 2, 8, 1, 7, 1, 2].

  4. Reconstructing the Number:

    • Convert array back to number: 9281712.

  5. Returning the Result:

    • Return 9281712.

Code

java
public class Solution {

  public int maximumSwap(int num) {
    char[] digits = Integer.toString(num).toCharArray();
    int[] maxIndexAfter = new int[digits.length];
    int maxIdx = digits.length - 1;

    // Finding the index of the maximum digit after each digit
    for (int i = digits.length - 1; i >= 0; i--) {
      if (digits[i] > digits[maxIdx]) {
        maxIdx = i;
      }
      maxIndexAfter[i] = maxIdx;
    }

    // Swapping the first non-maximum digit
    for (int i = 0; i < digits.length; i++) {
      if (digits[i] != digits[maxIndexAfter[i]]) {
        char temp = digits[i];
        digits[i] = digits[maxIndexAfter[i]];
        digits[maxIndexAfter[i]] = temp;
        break;
      }
    }

    return Integer.parseInt(new String(digits));
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    System.out.println(solution.maximumSwap(2736)); // Output: 7236
    // Example 2
    System.out.println(solution.maximumSwap(9965)); // Output: 9965
    // Example 3
    System.out.println(solution.maximumSwap(7281912)); // Output: 9281712
  }
}

Complexity Analysis

Time Complexity: O(n)

The process of converting the number to a digit array and traversing it (both for preparing maxIndexAfter and finding the swap position) each take O(n) time, linearly dependent on the number of digits (n).

Space Complexity: O(n)

The algorithm requires space proportional to the number of digits (n) for storing the digit array and the maxIndexAfter array, leading to O(n) space complexity.

🎯 STRICT STANDOUT — Solution Maximum Swap

1. Why / judgment

Fill last[0..9] with final index of each digit in decimal string. For i from left, for d from 9 down to digit[i]+1: if last[d]>i, swap i with last[d] and return. First improvement is optimal (leftmost position maximized). Trace 2736: at 2 find last[7]=1>0 -> swap -> 7236.

2. Big-O derivation (K11)

O(d*10)=O(d). Space O(1) last array.
7281912: at 7 last[9]=4 -> 9281712.
Already max -> original.

3. Pattern + when-NOT (K12)

Name: DIGIT LAST-INDEX GREEDY ONE SWAP

Recognition: maximize number with at most 1 swap.

When-NOT: Multiple swaps free -> sort. Lex smallest with one swap -> different target.

4. Edge hand-run (K13)

0 -> 0
Careful with int conversion after swap on string.

5. Interviewer follow-ups (model answers)

Q1. Why try high digits first at position i?
A: Largest possible digit at leftmost improvable place maximizes MSD contribution.

Q2. Could two candidate maxima conflict?
A: Single swap ends algorithm; first left success is enough.

Q3. String vs int arithmetic?
A: String/digit array avoids overflow and eases indexing.

6. Short drills

Drill: 98368->98863
Drill: 115->511
Drill: no-swap proof when nonincreasing
🧩 Pattern · Arrays

Recognize it: Scan once tracking what you need (running max/sum), or precompute a prefix-sum / hash → turn O(n²) into O(n).

▶ Visualize this problem (step it, predict each fork)
⛶ Open this problem debugger in explore mode
🤖 Don't fully get this? Learn it with Claude

Stuck on Maximum Swap? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Maximum Swap** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Maximum Swap** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Maximum Swap**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Maximum Swap**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Valid Triangle NumberValid Parenthesis String →