## Wednesday, May 2, 2018

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