Solution by awice


  • 0

    Approach #1: Brute Force [Accepted]

    Intuition

    The number only has at most 8 digits, so there are only 8 choose 2 = 28 available swaps. We can easily brute force them all.

    Algorithm

    We will store the candidates as lists of length len(num). For each candidate swap with positions (i, j), we swap the number and record if the candidate is larger than the current answer, then swap back to restore the original number.

    The 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.

    Java

    class Solution {
        public int maximumSwap(int num) {
            char[] A = Integer.toString(num).toCharArray();
            char[] ans = Arrays.copyOf(A, A.length);
            for (int i = 0; i < A.length; i++) {
                for (int j = i+1; j < A.length; j++) {
                    char tmp = A[i];
                    A[i] = A[j];
                    A[j] = tmp;
                    for (int k = 0; k < A.length; k++){
                        if (A[k] != ans[k]){
                            if (A[k] > ans[k]) {
                                ans = Arrays.copyOf(A, A.length);
                            }
                            break;
                        }
                    }
                    A[j] = A[i];
                    A[i] = tmp;
                }
            }
            return Integer.valueOf(new String(ans));
        }
    }
    

    Python

    def maximumSwap(self, num):
        A = list(str(num))
        ans = A[:]
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                A[i], A[j] = A[j], A[i]
                if A > ans: ans = A[:]
                A[i], A[j] = A[j], A[i]
    
        return int("".join(ans))
    

    Complexity Analysis

    • Time Complexity: $$O(N^3)$$, where $$N$$ is the total number of digits in the input number. For each pair of digits, we spend up to $$O(N)$$ work to compare the final sequences.

    • Space Complexity: $$O(N)$$, the information stored in A.


    Approach #2: Greedy [Accepted]

    Intuition

    At 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.

    Algorithm

    We will compute last[d] = i, the index i of the last occurrence of digit d (if it exists).

    Afterwards, 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.

    Java

    class Solution {
        public int maximumSwap(int num) {
            char[] A = Integer.toString(num).toCharArray();
            int[] last = new int[10];
            for (int i = 0; i < A.length; i++) {
                last[A[i] - '0'] = i;
            }
    
            for (int i = 0; i < A.length; i++) {
                for (int d = 9; d > A[i] - '0'; d--) {
                    if (last[d] > i) {
                        char tmp = A[i];
                        A[i] = A[last[d]];
                        A[last[d]] = tmp;
                        return Integer.valueOf(new String(A));
                    }
                }
            }
            return num;
        }
    }
    

    Python

    class Solution(object):
        def maximumSwap(self, num):
            A = map(int, str(num))
            last = {x: i for i, x in enumerate(A)}
            for i, x in enumerate(A):
                for d in xrange(9, x, -1):
                    if last.get(d, None) > i:
                        A[i], A[last[d]] = A[last[d]], A[i]
                        return int("".join(map(str, A)))
            return num
    

    Complexity Analysis

    • Time Complexity: $$O(N)$$, where $$N$$ is the total number of digits in the input number. Every digit is considered at most once.

    • Space Complexity: $$O(1)$$. The additional space used by last only has up to 10 values.


Log in to reply
 

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