Simple idea with only two pass with O(n) time and O(1) space


  • 0
    W

    As we can see, to get the maximum value after swap, we would intuitively swap the right most and largest digit with the left most and smallest digit. So the largest digits can have the most weight to form the maximum value.

    My idea is simple, swap the largest "abnormal" digit with the smallest "normal" digit.
    Here I define "abnormal" to "the digits are in descending order for if all the digits are in descending order we don't have to swap anymore. So there are two steps:

    1. Find the largest digit in the right "abnormal" part. We can first traverse to find the end of the "normal" digit and let the index be normal_end; and then find the maximum in the digits whose indexes are larger than normal_end;

    2. traverse from the normal_end to the left most to swap the found maximum digit to its "right" place, which meanings that after the swap the normal part is still "normal", i.e, in descending order.

    Here is my cpp code with explanation:

    class Solution {
    public:
        int maximumSwap(int num) {
    	string digits = to_string(num);
    	int len = digits.size();
    
    	if (len < 2) return num;
    	int normal_end = 0, max_index = -1;
    
    	// find the first digit that is "abnormal"
    	while (normal_end < len - 1 && digits[normal_end] >= digits[normal_end + 1])
    	  normal_end++;
    
    	if (normal_end == len - 1) return num; // in this case, the original num is in descending order, no need to swap
    
    	max_index = normal_end + 1; // initialize the index of the maximum after the normal_end.
    
    	// traverse the digits after the normal_end to find the maximum index
    	int max_start = max_index;
    	while (max_start < len) {
    	  if (digits[max_start] >= digits[max_index]) {
    		max_index = max_start;
    	  }
    	  max_start++;
    	}
    
    	//traverse back to swap the maximum value to the right position following the descending order
    	int max_temp = normal_end;
    	while (max_temp >= 0 && digits[max_temp] < digits[max_index]) {
    	  max_temp--;
    	}
    
    	//swap the largest abnormal digit to its right place at the normal part.
    	swap(digits[max_temp + 1], digits[max_index]);
    	int res = std::stoi(digits);
    	return res;
      }
    };
    
    

Log in to reply
 

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