# Maximum Swap
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-swap)
Canonical: https://scaleengineer.com/dsa/problems/maximum-swap
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Companies:** [KLA](https://scaleengineer.com/companies/kla)
---
## Problem
You are given an integer `num`. You can swap two digits at most once to get the maximum valued number.

Return _the maximum valued number you can get_.

**Example 1:**

**Input:** num = 2736
**Output:** 7236
**Explanation:** Swap the number 2 and the number 7.

**Example 2:**

**Input:** num = 9973
**Output:** 9973
**Explanation:** No swap.

**Constraints:**

* `0 <= num <= 108`

# Approaches
## Brute Force - Try All Swaps
This approach exhaustively tries every possible single swap. It iterates through all pairs of digits, swaps them, and evaluates the resulting number. The maximum number found after trying all swaps is the answer. This method guarantees finding the correct answer by exploring the entire search space of single swaps.
**Time:** O(N^3), where N is the number of digits in `num`. There are O(N^2) pairs of digits to swap. For each swap, converting the character array to a string and then to an integer takes O(N) time. · **Space:** O(N), where N is the number of digits in `num`. This space is used to store the character array representation of the number.
**Pros:** Simple to understand and implement.; Guaranteed to be correct as it checks all possibilities.
**Cons:** The time complexity is cubic in the number of digits, making it inefficient, although it passes for the given constraints.; It performs many unnecessary calculations and conversions.
### Explanation
The brute-force method is the most straightforward way to solve the problem. We begin by converting the integer into a sequence of characters, which is easier to manipulate. We then systematically try swapping every digit with every other digit that comes after it. For each swap, we form a new number and compare it with the maximum number we've seen so far. To ensure the original sequence is available for the next pair-swap, we either use a copy of the array for each swap or swap the digits back to their original positions after evaluating the new number. The initial number is also a candidate for the maximum, covering the case where no swap is beneficial.

```java
class Solution {
    public int maximumSwap(int num) {
        char[] digits = String.valueOf(num).toCharArray();
        int maxNum = num;
        for (int i = 0; i < digits.length; i++) {
            for (int j = i + 1; j < digits.length; j++) {
                // Swap
                char temp = digits[i];
                digits[i] = digits[j];
                digits[j] = temp;

                // Update max
                maxNum = Math.max(maxNum, Integer.parseInt(new String(digits)));

                // Swap back to restore the original array for the next iteration
                temp = digits[i];
                digits[i] = digits[j];
                digits[j] = temp;
            }
        }
        return maxNum;
    }
}
```
### Algorithm
*   Convert the input number `num` into a character array `s`.
*   Initialize a variable `maxVal` with the original `num`.
*   Use two nested loops to generate all possible unique pairs of indices `(i, j)` where `i < j`.
*   For each pair `(i, j)`:
    *   Create a temporary copy of the character array `s`.
    *   Swap the characters at indices `i` and `j` in the copy.
    *   Convert the modified character array back into an integer.
    *   Update `maxVal` to be the maximum of its current value and the newly formed integer.
*   After iterating through all possible swaps, `maxVal` will hold the largest number achievable with at most one swap.

## Greedy Search
A greedy approach works by making the locally optimal choice at each step. To maximize the number, we want to place the largest possible digits at the most significant (leftmost) positions. We scan the number from left to right. For each digit, we look for the largest digit to its right. If we find a digit that is smaller than a digit to its right, we've identified a candidate for a swap. We should swap this digit with the largest digit to its right (specifically, the rightmost occurrence of that largest digit) to create the biggest possible number. This swap is performed on the first such digit we find from the left, as this yields the most significant improvement.
**Time:** O(N^2), where N is the number of digits. The nested loops lead to a quadratic runtime. The outer loop runs N times, and the inner loop runs up to N times. · **Space:** O(N), where N is the number of digits. This space is for the character array.
**Pros:** More efficient than the brute-force approach.; Relatively easy to reason about the greedy choice.
**Cons:** The time complexity is quadratic, which is not optimal.
### Explanation
This greedy strategy is more efficient than brute force. We convert the number to a character array and iterate from left to right. For each digit `A[i]`, we scan the rest of the array to its right to find the largest digit available for a swap. If the largest digit to the right is greater than `A[i]`, we perform the swap. The key is to find the leftmost digit `A[i]` that is smaller than some digit to its right, and swap it with the largest of those digits. To handle cases like `1993` where we want `9913` not `9193`, we must swap with the rightmost occurrence of the target digit. Once the single, most effective swap is done, the process terminates.

```java
class Solution {
    public int maximumSwap(int num) {
        char[] digits = String.valueOf(num).toCharArray();
        int n = digits.length;

        for (int i = 0; i < n; i++) {
            int maxIdx = i;
            // Find the index of the largest digit to the right of i
            for (int j = i + 1; j < n; j++) {
                // Use >= to ensure we get the rightmost occurrence of the max digit
                if (digits[j] >= digits[maxIdx]) {
                    maxIdx = j;
                }
            }

            // If a larger digit is found to the right, swap and return
            if (digits[i] < digits[maxIdx]) {
                char temp = digits[i];
                digits[i] = digits[maxIdx];
                digits[maxIdx] = temp;
                return Integer.parseInt(new String(digits));
            }
        }
        // If no swap was made, the number is already the largest
        return num;
    }
}
```
### Algorithm
*   Convert the input number `num` to a character array `A`.
*   Iterate through the array `A` from left to right with an index `i`.
*   For each `i`, find the index `max_idx` of the largest digit in the subarray to its right (`A[i+1]` to `A[n-1]`). To ensure the resulting number is maximized, if the largest digit appears multiple times, `max_idx` should point to its rightmost occurrence.
*   Check if the digit at the current position `A[i]` is smaller than the largest digit found to its right `A[max_idx]`.
*   If it is, this is the first (leftmost) position that can be improved. Swap `A[i]` with `A[max_idx]`.
*   Since only one swap is allowed and we have just performed the most impactful one, convert the modified array `A` back to an integer and return it immediately.
*   If the loop completes without any swaps, the number's digits are already in descending order. Return the original `num`.

## Optimized Greedy (Linear Time)
This is an optimized version of the greedy approach that achieves linear time complexity. The core idea is the same: find the leftmost digit that can be swapped with a larger digit to its right to form a bigger number. Instead of repeatedly scanning for the largest digit in a nested loop, we pre-process the number to find the last known index of each digit (0-9). With this information, for each digit, we can determine in constant time if a better digit exists to its right and where its rightmost position is. This eliminates the quadratic complexity.
**Time:** O(N), where N is the number of digits. Populating the `last_occurrence` array takes O(N). The main loop runs N times, and its inner loop runs at most 10 times (a constant), so the total time is O(N). · **Space:** O(N), where N is the number of digits. O(N) is for the character array, and the `last_occurrence` array takes O(1) space as its size (10) is constant.
**Pros:** Optimal time complexity.; Very efficient, solving the problem with a constant number of passes over the digits.
**Cons:** Slightly more complex to conceptualize due to the pre-computation step.
### Explanation
The linear time solution refines the greedy strategy by being smarter about finding the swap target. First, we pass through the number (as a character array) to record the last index of each digit in a separate `last_occurrence` array. This takes O(N) time. Then, we iterate through the character array a second time, from left to right. For each digit `A[i]`, we check if there's a larger digit (from 9 down to `A[i]+1`) whose last occurrence is to the right of `i`. The first time we find such a case, we've found our optimal swap. We swap `A[i]` with that larger digit and return the resulting number. This check is fast because we can directly look up the position from our `last_occurrence` array.

```java
class Solution {
    public int maximumSwap(int num) {
        char[] digits = String.valueOf(num).toCharArray();
        int n = digits.length;
        int[] lastOccurrence = new int[10];

        // Record the last index of each digit
        for (int i = 0; i < n; i++) {
            lastOccurrence[digits[i] - '0'] = i;
        }

        // Find the first position from the left that can be swapped for a larger digit
        for (int i = 0; i < n; i++) {
            int currentDigit = digits[i] - '0';
            // Try to find a larger digit (from 9 down to currentDigit+1)
            for (int d = 9; d > currentDigit; d--) {
                // If a larger digit exists to the right of the current position
                if (lastOccurrence[d] > i) {
                    // Swap with the rightmost occurrence of that larger digit
                    char temp = digits[i];
                    digits[i] = digits[lastOccurrence[d]];
                    digits[lastOccurrence[d]] = temp;
                    return Integer.parseInt(new String(digits));
                }
            }
        }
        // If no swap was made, the number is already the largest
        return num;
    }
}
```
### Algorithm
*   Convert the input number `num` to a character array `A`.
*   Create an integer array `last_occurrence` of size 10, initialized to 0.
*   Iterate through `A` from left to right to populate `last_occurrence`, where `last_occurrence[d]` will store the index of the last time digit `d` was seen.
*   Iterate through `A` again from left to right (index `i`). This `i` represents the position we are trying to swap from.
*   For each digit `A[i]`, look for a larger digit `d` that could be swapped into this position. We do this by iterating `d` from 9 down to `A[i] - '0' + 1`.
*   For each `d`, check if its last occurrence is to the right of `i` (i.e., `last_occurrence[d] > i`).
*   If such a `d` is found, we have identified the best possible swap: swap `A[i]` with the digit at `A[last_occurrence[d]]`.
*   After the swap, convert the array `A` back to an integer and return it, as we have found the maximum value.
*   If the loops complete without any swap, the number is already optimal. Return the original `num`.

# Solutions
### Java

```java
class Solution {
public
  int maximumSwap(int num) {
    char[] s = String.valueOf(num).toCharArray();
    int n = s.length;
    int[] d = new int[n];
    for (int i = 0; i < n; ++i) {
      d[i] = i;
    }
    for (int i = n - 2; i >= 0; --i) {
      if (s[i] <= s[d[i + 1]]) {
        d[i] = d[i + 1];
      }
    }
    for (int i = 0; i < n; ++i) {
      int j = d[i];
      if (s[i] < s[j]) {
        char t = s[i];
        s[i] = s[j];
        s[j] = t;
        break;
      }
    }
    return Integer.parseInt(String.valueOf(s));
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximumSwap(int num) {
    string s = to_string(num);
    int n = s.size();
    vector<int> d(n);
    iota(d.begin(), d.end(), 0);
    for (int i = n - 2; ~i; --i) {
      if (s[i] <= s[d[i + 1]]) {
        d[i] = d[i + 1];
      }
    }
    for (int i = 0; i < n; ++i) {
      int j = d[i];
      if (s[i] < s[j]) {
        swap(s[i], s[j]);
        break;
      }
    }
    return stoi(s);
  }
};

```

### Python

```python
class Solution:
    def maximumSwap(self, num: int) -> int: s = list(str(num)) n = len(s) d = list(range(n)) for i in range(n - 2, - 1, - 1): if s[i] <= s[d[i + 1]]: d[i] = d[i + 1] for i, j in enumerate(d): if s[i] < s[j]: s[i], s[j] = s[j], s[i] break return int('' . join(s))

```