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;        
                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){
                max_digit = Math.max(max_digit,ch[i]-'0');
            for(int i=0;i<ch.length;++i){
                if(ch[i]-'0' < max_digit){
                }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.