670. Maximum Swap

// LeetCode URL: https://leetcode.com/problems/maximum-swap/

/**
 * Greedy Approach
 *
 * Use buckets to record the last position of digit 0 ~ 9 in this num.
 *
 * Loop through the num array from left to right. For each position, we check
 * whether there exists a larger digit in this num (start from 9 to current
 * digit). We also need to make sure the position of this larger digit is behind
 * the current one. If we find it, simply swap these two digits and return the
 * result.
 *
 * Time Complexity: O(9 * N) = O(N)
 *
 * Space Complexity: O(10) = O(1)
 *
 * N = Number of digits in the input number.
 */
class Solution {
    public int maximumSwap(int num) {
        if (num <= 11) {
            return num;
        }
        char[] digits = Integer.toString(num).toCharArray();

        int[] lastIdx = new int[10];

        for (int i = 0; i < digits.length; i++) {
            lastIdx[digits[i] - '0'] = i;
        }

        for (int i = 0; i < digits.length; i++) {
            for (int k = 9; k > digits[i] - '0'; k--) {
                if (lastIdx[k] > i) {
                    char tmp = digits[i];
                    digits[i] = digits[lastIdx[k]];
                    digits[lastIdx[k]] = tmp;
                    return Integer.valueOf(new String(digits));
                }
            }
        }

        return num;
    }
}