algoadvance

Leetcode 670. Maximum Swap

Problem Statement

670. Maximum Swap

You are given a non-negative integer num. You can swap two digits at most once to get the maximum valued number. Return the maximum valued number you can get.

Example 1:

Input: num = 2736
Output: 7236
Explanation: Swap the digit 2 with the digit 7.

Example 2:

Input: num = 9973
Output: 9973
Explanation: No swap needed because the number is already the largest possible.

Constraints:

• 0 <= num <= 10^8

Clarifying Questions

1. Clarify input format: Is the input always a non-negative integer?
   • Yes.
2. Number of swaps: Can we perform more than one swap?
   • No, only one swap is allowed or you can choose not to swap if the number is already in its maximum possible form.
3. Return type: Should the function return the integer itself or the digits rearranged?
   • The function should return the integer itself.

Strategy

1. Convert to Array of Digits: Convert the integer to a string to easily access individual digits, then convert it into a character array for easier manipulation.
2. Track Maximum Digits: Traverse from right to left and track the maximum digit that appears.
3. Identify Swap: For each digit (from left to right), if there is a higher digit available to swap from the right, perform the swap.
4. Return Result: Convert the character array (modified as needed) back to an integer and return.

Code

Here’s the implementation of the above strategy:

public class Solution {
    public int maximumSwap(int num) {
        char[] digits = Integer.toString(num).toCharArray();
        int n = digits.length;
        
        // Record the last seen position of digit 0-9
        int[] last = new int[10];
        for (int i = 0; i < n; i++) {
            last[digits[i] - '0'] = i;
        }
        
        // Try to find the first place to make a swap to get a bigger number
        for (int i = 0; i < n; i++) {
            for (int d = 9; d > digits[i] - '0'; d--) {
                if (last[d] > i) {
                    // Swap digits[i] and digits[last[d]]
                    char temp = digits[i];
                    digits[i] = digits[last[d]];
                    digits[last[d]] = temp;
                    
                    // Convert the array back to integer and return
                    return Integer.parseInt(new String(digits));
                }
            }
        }
        
        return num; // No swap makes the number larger
    }
}

Time Complexity

• Time Complexity: The primary operations are traversals of the digit array:
  • The first for-loop runs O(n) where n is the number of digits.
  • The second nested loops will result in worst case O(10 * n), but since the inner loop runs at most 10 times, it simplifies to O(n) overall.
  • The overall time complexity is O(n).
• Space Complexity: O(n) due to the array creation which holds the digit characters and auxiliary space for the last array.

This strategy ensures that we identify the optimal digits to swap in a single pass, making the solution efficient and straightforward.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?