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 <= 108The idea is to always try and bring the largest possible digit to the leftmost position if it maximizes the number. For this, we can use a map to record the last occurrence of each digit. By iterating through the number, we can then attempt swapping if any larger digit occurs later.
We convert the number to a string of digits and map each digit to its last occurrence in the number. We then iterate through the digits, looking for any larger digit that comes after the current one. If found, we swap them to create the largest possible number.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of digits in num.
Space Complexity: O(1) as the storage is constant due to limited digit size.
Maximum Swaps - Leetcode 670 - Python • NeetCodeIO • 18,883 views views
Watch 9 more video solutions →Practice Maximum Swap with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor