Is Maximum Swap easy or hard?

Maximum Swap is generally classified as a Medium difficulty problem. The brute-force solution is straightforward, but identifying the greedy optimization using the last occurrence of digits requires understanding how place value affects the final number.

How to solve Maximum Swap in O(n)?

Convert the integer into a digit array and record the last index of each digit from 0 to 9. Iterate from the leftmost digit and check if a larger digit appears later using the stored indices. Swap with the largest possible digit’s last occurrence and stop immediately. This guarantees the maximum improvement in linear time.

What is the best approach for Maximum Swap?

The greedy last-occurrence approach is the best solution. Record the last position of each digit (0–9), then scan the number from left to right and swap the current digit with the largest digit appearing later. This guarantees the maximum possible number using only one swap and runs in O(n) time with O(1) extra space.

What data structure is used in Maximum Swap?

The optimal solution uses a small array or hash map to store the last occurrence of digits 0–9. The number itself is usually converted into a character or integer array so digits can be swapped efficiently.

What is the time complexity of Maximum Swap?

The optimal greedy solution runs in O(n) time where n is the number of digits. A single pass records the last occurrence of each digit, and another pass determines the best swap. Space complexity remains O(1) because the digit lookup array has a fixed size of 10.

Maximum Swap Python or Java solution approach?

Both Python and Java implementations follow the same greedy strategy: convert the number to a digit array, build a last-occurrence array for digits, scan from left to right, and perform one swap with the largest later digit. The algorithm remains O(n) time and O(1) extra space regardless of language.

Is Maximum Swap asked at Google, Amazon, or Meta?

Maximum Swap appears in interview preparation sets for companies like Amazon, Google, and Meta because it tests greedy reasoning and digit manipulation. It’s commonly used to evaluate whether candidates can reduce a brute-force search into a linear-time greedy strategy.

670. Maximum Swap - Practice Online

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 <= 10⁸