LeetCode 670 - Maximum Swap

https://leetcode.com/problems/maximum-swap/description/

---

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:

1. The given number is in the range [0, 108]

X.

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 $\text{last[d] = i}$, the index $\text{i}$ of the last occurrence of digit $\text{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.

    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;
    }
https://leetcode.com/problems/maximum-swap/discuss/107068/Java-simple-solution-O(n)-time

public int maximumSwap(int num) {

char[] nums = String.valueOf(num).toCharArray();

// 332()49 return

Optional<Integer> incPos = findFirstIncreasingPos(nums);

if (!incPos.isPresent()) {

// 321

return num;

}

int maxPos = findMaxPosition(nums, incPos.get());

int firstLesserPos = findFirstLesserPos(nums, incPos.get(), nums[maxPos]);

swap(nums, firstLesserPos, maxPos);

return Integer.parseInt(String.valueOf(nums));

}

// not including end

private int findFirstLesserPos(char[] nums, int end, char ch) {

for (int i = 0; i < end; i++) {

if (nums[i] < ch) { // not >

return i;

}

}

throw new RuntimeException("should never happen");

}

private void swap(char[] nums, int i, int j) {

char tmp = nums[i];

nums[i] = nums[j];

nums[j] = tmp;

}

// precondition: size >1

// 1234 return pos:1

private Optional<Integer> findFirstIncreasingPos(char[] nums) {

for (int i = 1; i < nums.length; i++) {

if (nums[i] > nums[i - 1])

return Optional.of(i);

}

return Optional.empty();

}

// precondition: must exist

// 32123()

private int findMaxPosition(char[] nums, int start) {

int maxPos = start;

for (int i = start; i < nums.length; i++) {

if (nums[i] >= nums[maxPos]) {

maxPos = i;

}

}

return maxPos;

}

https://leetcode.com/problems/maximum-swap/discuss/120360/O(n)-time-and-O(1)-space-without-using-array

I am visualizing this problem as a monotonic line from right to left with dips. So, I am traversing the number from right to left.
Objective 1- To find the number just before the dip with Max possible value. I am recording it as max and its index as maxI.

Objective 2 - To find a dip which is farthest from right. I am recording it as min and its index as minI.

If I find a dip, I am updating the max value. If there is a smaller value after the max value, then I am updating the min. Whenever there is an update in min and max, I record their Indexes and use them at the time of recreating the number.

    public int maximumSwap(int num) {
        int numC = num;
        
        int min = Integer.MAX_VALUE;
        int minI = -1;
        
        int max = Integer.MIN_VALUE;
        int maxI = -1;
        
        int pre = -1;
        int i = 0;
        
        int lmax = Integer.MIN_VALUE;
        int lmaxI = -1;
        
        //find out min and max values and their index in the num
        while(num != 0){
            int cur = num % 10;
            num = num / 10;
            
            //record increase in max value locally
            if(cur > lmax){
                lmax = cur;
                lmaxI = i +1 ;
            }
            
            //record if there is a dip
            if(cur < pre && max < lmax){
                max = lmax;
                maxI = lmaxI;
            }
            //record min value
            if(cur < max && minI < i+1){
                min = cur;
                minI = i + 1;
            }
            i++;
            pre = cur;
        }
        
        int result = 0;
        
        // re-create that number by swaping min and max
        while(i != 0){
            if(i == maxI){
                result =  result  + (min *  (int)(Math.pow(10,i-1)));
            }
            else if(i == minI){
                result =  result + (max * (int)(Math.pow(10,i-1)));
            }
            else result = result + ((numC / (int)(Math.pow(10,i -1 ))) * (int)(Math.pow(10,i-1)));
            
            numC = numC % (int)(Math.pow(10,i-1)) ;
            i--;
        }
        return result;
    }

X.

• 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)$ time to compare the final sequences.
• Space Complexity: $O(N)$, the information stored in $\text{A}$.

    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));
    }