Java Solution using Double Ended Queue


  • 0

    Add the occurrence of each digit from last to first of the number, so that our queue for each digit is in non-increasing order.

    Compare last occurrence of each higher digit with the digits appearing from the start of the number(from MSB to LSB). If a mismatch occurs, swap them by polling the first occurrence of that digit in the queue and that is the solution. If a match occurs, poll the last occurrence of the higher digit as that is the visited location now.

    class Solution {
        
        static class DigitOccurences{
            Deque<Integer> q;        
            DigitOccurences(){
                q = new ArrayDeque<Integer>();
            }
        }
        
        public int maximumSwap(int num) {
            char[] ch = String.valueOf(num).toCharArray();
            Solution.DigitOccurences[] d = new Solution.DigitOccurences[10];
            int max_digit = -1;
            
            for(int i=0;i<d.length;++i) d[i] = new Solution.DigitOccurences();
            
            for(int i=ch.length-1;i>=0;--i){
                d[ch[i]-'0'].q.offer(i);
                max_digit = Math.max(max_digit,ch[i]-'0');
            }
            
            for(int i=0;i<ch.length;++i){
                if(ch[i]-'0' < max_digit){
                    swap(ch,i,d[max_digit].q.poll());
                    break;
                }else if(ch[i]-'0' == max_digit){
                    if(!d[max_digit].q.isEmpty()) d[max_digit].q.pollLast();
                    max_digit = getNextMaxDigit(max_digit,d);
                }
            }       
            
            return Integer.parseInt(new String(ch));
        }
        
        public void swap(char[] ch,int index_1,int index_2){
            char temp   = ch[index_1];
            ch[index_1] = ch[index_2];
            ch[index_2] = temp;
        }
        
        public int getNextMaxDigit(int max_digit,Solution.DigitOccurences[] d){
            for(int i=max_digit;i>=0;--i){
                if(!d[i].q.isEmpty()) return i;
            }
            return -1;
        }   
    }
    

Log in to reply
 

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