# Java Solution using Double Ended Queue

• 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;
}
}
``````

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