Easy to understand O(n) Java code


  • 0
    A

    We iterate the digits from least significant to most significant. At each digit, we try to swap with the maximum digit that we've seen so far. However, we can only perform this swap if the maximum digit is larger than the current digit (otherwise, the number either stays the same or gets smaller). Following this idea, we find the most significant digit that we can perform a swap at. This will result in the largest number possible.

    The code is not the most concise, but hopefully easy to understand.

    class Solution 
    {
        public int maximumSwap(int num) 
        {
            List<Integer> digits = getDigits(num);
            int maxDigitIndex = 0;
            int leftSwapIndex = 0;
            int rightSwapIndex = 0;
            for(int i = 0; i < digits.size(); i++)
            {
                if(digits.get(i) > digits.get(maxDigitIndex))
                {
                    maxDigitIndex = i;
                }
                //found a better place we can swap the max with
                else if(digits.get(maxDigitIndex) > digits.get(i))
                {
                    leftSwapIndex = maxDigitIndex;
                    rightSwapIndex = i;
                }
            }
            swap(digits, leftSwapIndex, rightSwapIndex);
            return buildNum(digits);
        }
        
        private void swap(List<Integer> items, int leftIndex, int rightIndex)
        {
            int temp = items.get(leftIndex);
            items.set(leftIndex, items.get(rightIndex));
            items.set(rightIndex, temp);
        }
        
        private int buildNum(List<Integer> digits)
        {
            int place = 1;
            int total = 0;
            for(int i = 0; i < digits.size(); i++)
            {
                total += (place * digits.get(i));
                place *= 10;
            }
            return total;
        }
        
        private List<Integer> getDigits(int num)
        {
            List<Integer> digits = new ArrayList<Integer>();
            do
            {
                digits.add(num % 10);
                num /= 10;
            }
            while(num > 0);
            return digits;
        }
    }
    

Log in to reply
 

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