Java O(n) time O(n) space using Map w/ explanation


  • 0
    X
      public int maximumSwap(int num) {
        if (num < 10) return num;
        int[] digits = new int[9]; // largest giving number is 10^8
        LinkedList<Integer>[] indices = new LinkedList[10]; //value-index map
    
        // use an array `digits` to represent given number
        int len = 0;
        while (num != 0) {
          int d = num % 10;
          if (indices[d] == null) {
            indices[d] = new LinkedList<>();
          }
          indices[d].add(len);
    
          digits[len++] = d;
          num /= 10;
        }
    
        // iterate over `digits` from higher to lower, and choose the largest number if it's possible
        // when we meet the first number that get the maximum value, but different with its original position, we found the swap
        int hiPosition = len - 1;
        for (int n = 9; n >= 0; n--) {
          if (indices[n] == null) continue;
          while (!indices[n].isEmpty() && indices[n].getLast() == hiPosition) {
            indices[n].removeLast();
            hiPosition--;
          }
          if (!indices[n].isEmpty()) {
            swap(digits, hiPosition, indices[n].getFirst());
            break;
          }
        }
    
        // change the array back to number
        int res = 0;
        for (int i = len - 1; i >= 0; i--) {
          res *= 10;
          res += digits[i];
        }
        return res;
      }
    

Log in to reply
 

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