MediumMathGreedyUpdated Sep 2026

670. Maximum Swap

Asked at Apple

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Math

Companies

1

Problem

You are given a non-negative integer num. You may swap two of its digits at most once. Swapping is optional — you can also do nothing.

Return the largest number you can produce. Leading zeros are not allowed, so you can never move a 0 into the first position if that would create a shorter number.

The key idea: a swap only helps if you move a bigger digit into an earlier (more significant) position. The earlier the position, the more the swap is worth.

One swap, biggest gain

digits27360123Position 0 holds a 2, but a 7 sits to its right —swapping them is the best move.
Moving a bigger digit left is always worth more than moving it right, so we look for the earliest position that can improve.

Constraints

  • ●0 <= num <= 10^8
  • ●num is a non-negative integer
  • ●At most one swap of two digits is allowed

Examples

Example 1
Inputnum = 2736
Output7236
WhySwapping the 2 and the 7 puts the largest digit in the front, which is the biggest possible gain. 7236 > 2736.
Example 2
Inputnum = 9973
Output9973
WhyThe digits are already in decreasing order, so no swap can make the number bigger. Return it unchanged.

Asked At

1 companies
CompanyDifficulty
AppleMediumView all Apple questions →

How to Think About It

1

Brute force: generate all possible swaps of two digits and track the maximum.

2

Think about what makes a swap beneficial: you want to move a larger digit to a more significant position.

3

Scan from left to right and record the last occurrence of each digit (0-9).

4

For each position, check if any larger digit exists to its right; if so, swap with the last such occurrence.

5

If no beneficial swap is found, the number is already maximal — return it as is.

Optimal Approach

Convert the number to a character array. Scan from right to left, tracking the index of the maximum digit seen so far. Simultaneously scan from left to right; at the first position where a smaller digit appears but a larger digit exists to its right, perform the swap and return. This greedy approach runs in O(n) time with O(1) space since digits are bounded 0-9.

Greedy: last occurrence of each digit

digits27360123Step 1 — last[7] = 1, the rightmost 7 in the numberdigits27360123Step 2 — at index 0 the digit is 2, and a larger digit(7) exists to the right, so swap themdigits72360123Step 3 — result is 7236, the maximum possible valuefor i, d in enumerate(digits): find largest k > d with last[k] > i swap and return
Record where each digit appears last, then scan left to right and swap the first position that has a bigger digit to its right.
ComplexityTime O(n)Space O(1)We scan the digits a constant number of times, and the digit alphabet is only 0-9, so the extra space is constant.

What Trips People Up in Real Interviews

1

Clarify that at most two digits are swapped (exactly one swap or zero swaps if already optimal).

2

Edge case: single-digit numbers need no swap.

3

Edge case: numbers with all identical digits return unchanged.

4

Explain why tracking last occurrence of each digit avoids incorrect swaps when duplicates exist.

5

Walk through a trace with number 9973 → answer is 9973 (no improvement possible).

Solution Code

O(n) time
def maximumSwap(num: int) -> int:
    digits = list(str(num))
    last = {int(d): i for i, d in enumerate(digits)}
    for i, d in enumerate(digits):
        for k in range(9, int(d), -1):
            if last.get(k, -1) > i:
                digits[i], digits[last[k]] = digits[last[k]], digits[i]
                return int(''.join(digits))
    return num

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Maximum Swap problem?

Given a non-negative integer, you can swap at most two digits to form the largest possible number. Return the maximum value you can obtain. The input is guaranteed to fit within a 32-bit signed integer.

How do you solve Maximum Swap?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Maximum Swap?

Maximum Swap is asked at Apple. It is a medium difficulty problem.

What are common mistakes on Maximum Swap?
  • Clarify that at most two digits are swapped (exactly one swap or zero swaps if already optimal).
  • Edge case: single-digit numbers need no swap.
  • Edge case: numbers with all identical digits return unchanged.
  • Explain why tracking last occurrence of each digit avoids incorrect swaps when duplicates exist.
  • Walk through a trace with number 9973 → answer is 9973 (no improvement possible).