#670

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Swap

Given an integer, swap at most two digits once to produce the largest possible number using greedy digit selection.

Problem Statement

You are given a non-negative integer num. You can swap two digits at most once to create the largest possible number. Return the resulting maximum number after at most one swap.

For example, if num = 2736, swapping the 2 and 7 yields 7236, which is the largest possible. If num = 9973, no swap increases the number, so the output is 9973. Constraints: 0 <= num <= 108.

Examples

Example 1

Input: num = 2736

Output: 7236

Swap the number 2 and the number 7.

Example 2

Input: num = 9973

Output: 9973

No swap.

Constraints

0 <= num <= 108

Solution Approach

Track Last Occurrences of Digits

Store the last index for each digit from 0 to 9 to quickly identify potential swap candidates. This ensures that any swap uses the largest available digit to maximize the result.

Identify Greedy Swap Position

Iterate through the number from left to right, and for each digit, check if a higher digit exists later. Swap with the rightmost larger digit to guarantee a maximal increase while respecting the single-swap limit.

Execute Swap and Return Result

Perform the identified swap once, convert the digits back into an integer, and return it. If no higher digit exists later, return the original number. This preserves the invariant of maximizing the leftmost digits first.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The algorithm scans the digits once to store their last occurrences (O(n)) and then iterates again to find the swap (O(n)), with space O(n) to store digit indices. Overall, time and space complexity are both linear relative to the number of digits.

What Interviewers Usually Probe

The candidate immediately recognizes that only one swap is allowed and aims for maximal leftmost digits.
The candidate uses a mapping of last occurrences to efficiently identify swap opportunities.
The candidate considers edge cases like numbers with descending digits or repeated maximum digits.

Common Pitfalls or Variants

Common pitfalls

Swapping the first higher digit without considering the rightmost occurrence may produce a suboptimal result.
Not handling numbers where no swap improves the result leads to incorrect output.
Confusing digit indices after converting between string and integer representation can cause off-by-one errors.

Follow-up variants

Allow multiple swaps to maximize the number, changing the problem from single-swap greedy to iterative maximization.
Find the maximum number by swapping non-adjacent digits only, introducing additional positional constraints.
Apply the same greedy swapping strategy to decimal or negative numbers, requiring careful handling of signs and decimal points.

FAQ

What is the main strategy for Maximum Swap?

The main strategy is to use a greedy approach: track the last occurrence of each digit and swap the first smaller digit with the largest digit appearing later.

Can we swap more than once in Maximum Swap?

No, the problem allows at most one swap. Swapping multiple times would require a different algorithm.

How do we handle numbers where swapping does not increase the value?

If no larger digit exists later for any position, the original number is already maximal and should be returned unchanged.

What are common mistakes in implementing Maximum Swap?

Common mistakes include swapping the first higher digit without checking rightmost occurrence or mismanaging indices when converting between string and integer.

How does the greedy choice plus invariant pattern apply here?

It ensures the leftmost digits are maximized first by swapping with the largest possible digit later, preserving the invariant that earlier digits are optimal.

terminal

Solution

Solution 1: Greedy Algorithm

First, we convert the number into a string $s$. Then, we traverse the string $s$ from right to left, using an array or hash table $d$ to record the position of the maximum number to the right of each number (it can be the position of the number itself).

1

2

3

4

5

6

7

8

9

10

11

12

13

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))

Solution 2: Space Optimized Greedy

#### TypeScript

1

2

3

4

5

6

7

8

9

10

11

12

13

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))

Continue Practicing

#738 monotone increasing digits #781 rabbits in forest #910 smallest range ii