Leetcode discuss: 1053. Previous Permutation With One Swap

 Here is the link. 

Jan. 18, 2021
Introduction
It is last algorithm in one of premimum Microsoft mock onsite. I worked on the idea to use upper bound 10^4, lower time complexity to linear, record last occurrence each integer from 0 to 10000 backward in the array.

Case study
Input: arr = [3,2,1]
Output: [3,1,2]
Explanation: Swapping 2 and 1.

By practicing a lot of arrays, it was slowly for me to figure out how to come out the largest smallest integer.

My first approach is to assume that each integer in the array is from 0 to 9. So only 10 choices for integer. Last occurrence of digit is recorded from left to right.

For example, backward from last index = 2, current = 1, previous = 2, so it is possible to make it largest smaller. Index = 1, value 2 can be replaced by a digit smaller than 2, just brute force from 2, decrement one by one to search, 1 is found and it's latest occurrence is 2.

Next expand the array size to 10^4, the idea is the same.

Advice
I like to write down advice for me to be humble. I practice over 600 algorithm on Leetcode, and also won Gold medal on Hackerrank. But I was confused in the mock interview with last two algorithms.

First it is not good to have negative talk to myself, keep myself humble. Stay curious, and continue to spend time after the mock interview.

For my case, I made two mistakes, first it is not digits from 0 to 9, actually it is 0 to 10000. Secondly I did not like to read my own code to fix the bug after I wrote a solution. I ran Visual Studio debugger and then moved the statement to set

lastPos[current] = i;  

statement before if statement inside the for loop.

Time complexity
It is important to avoid brute force solution, find all pairs to swap and then keep the minimum one, which is O(N^3), N is the length of the array, since O(N^2) for all possible swaps, O(N) to compare integer array with maximum integer array.

My solution is O(N * M), N is the length of the array, M is the upper bound of arr[i].

The following code passes online judge.

public class Solution {
    public int[] PrevPermOpt1(int[] numbers) {
        if(numbers == null || numbers.Length == 0)
        {
            return new int[0];
        }
        
        var length = numbers.Length; 
        const int SIZE = 10000; 
        var lastPos = new int[SIZE];  // 10^4, not 10
        for(int i = 0; i < SIZE; i++)
        {
            lastPos[i] = -1; 
        }
        
        var swap = new int[length];
        for(int i = 0; i < length; i++)
        {
            swap[i] = numbers[i]; 
        }
        
        for(int i = length - 1; i >= 1; i--)
        {
            var current = numbers[i];
            var previous = numbers[i - 1];                       
            
            lastPos[current] = i; 
            
            if(previous > current)
            {
                for(int smaller = previous - 1; smaller >= 1; smaller--)
                {
                    if(lastPos[smaller] != -1)    
                    {
                        // swap two numbers
                        // i-1, largest[smaller]
                        var front = i - 1; 
                        var back = lastPos[smaller];
                        
                        swap[front] = smaller; 
                        swap[back]  = previous; 
                        
                        return swap;                        
                    }
                }                           
            }                        
        }
        
        return swap;                
    }
}