Java O(n) time O(n) space w/ Explanation


  • 3
    G

    Before I start my explanation, it is important to note the greedy algorithm at play here. If there is a less significant digit bigger than a more significant digit, the number always increases by switching them. To achieve the maximum number after a swap, you have to swap with the most significant digit possible. Additionally, you want to make sure that the digit you swap with that more significant number is as big as possible.

    The algorithm is as follows:

    1. Traverse num from the least significant digit to the most significant digit, making sure to store the numbers as you go (I store the numbers I see in a List). While traversing, keep track of the maximum number seen so far.

    2. If the current number is smaller than the maximum number you have seen so far, I set the swap indices to those two indices (indices of max, less significant digit and more significant, smaller digit). Otherwise, if the current number is bigger than max, reset the max.

    3. At the end, swap the designated swap indices in the List, then convert the List back to a number for returning.

    My variable naming conventions:

    maxSeen holds the maximum number I have seen, maxIdx holds the index for that max number, power holds the index of the currently visiting number, and the swapIdx's hold the indices to be swapped.

    class Solution {
        public int maximumSwap(int num) {
            int maxSeen = 0, maxIdx = -1, power = 0, swapIdx1 = 0, swapIdx2 = 0;
            List<Integer> list = new ArrayList<>();
            while(num > 0){
                int digit = num % 10;
                list.add(digit);
                if(maxSeen > digit){
                    swapIdx1 = power;
                    swapIdx2 = maxIdx;
                }
                else if(digit > maxSeen){
                    maxSeen = digit;
                    maxIdx = power;
                }
                num = num/10;
                power++;
            }
            
            Collections.swap(list, swapIdx1, swapIdx2);
    
            int result = 0;
            for(int i = 0; i < list.size(); i++){
                result += (int)(Math.pow(10, i) * list.get(i));
            }
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.