Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.
Example 1:
Input: 2736 Output: 7236 Explanation: Swap the number 2 and the number 7.
Example 2:
Input: 9973 Output: 9973 Explanation: No swap.
Note:
Intuition
\nThe number only has at most 8 digits, so there are only = 28 available swaps. We can easily brute force them all.
\nAlgorithm
\nWe will store the candidates as lists of length . For each candidate swap with positions , we swap the number and record if the candidate is larger than the current answer, then swap back to restore the original number.
\nThe only detail is possibly to check that we didn\'t introduce a leading zero. We don\'t actually need to check it, because our original number doesn\'t have one.
\n\nComplexity Analysis
\nTime Complexity: , where is the total number of digits in the input number. For each pair of digits, we spend up to time to compare the final sequences.
\nSpace Complexity: , the information stored in .
\nIntuition
\nAt each digit of the input number in order, if there is a larger digit that occurs later, we know that the best swap must occur with the digit we are currently considering.
\nAlgorithm
\nWe will compute , the index of the last occurrence of digit (if it exists).
\nAfterwards, when scanning the number from left to right, if there is a larger digit in the future, we will swap it with the largest such digit; if there are multiple such digits, we will swap it with the one that occurs the latest.
\n\nComplexity Analysis
\nTime Complexity: , where is the total number of digits in the input number. Every digit is considered at most once.
\nSpace Complexity: . The additional space used by only has up to 10 values.
\nAnalysis written by: @awice
\n