← Back to Index

📚 Maximum Swap – Java Cheat Sheet

📌 What Is It?

The Maximum Swap problem involves finding the largest number possible by swapping two digits in a given non-negative integer. You can perform at most one swap.

🧱 Pattern Template

Greedy Algorithm

class Solution {
    public int maximumSwap(int num) {
        char[] digits = Integer.toString(num).toCharArray();
        int n = digits.length;

        // Track the maximum digit and its index from the right
        int maxIdx = n - 1;
        int leftIdx = -1, rightIdx = -1;

        // Traverse the digits from right to left
        for (int i = n - 2; i >= 0; i--) {
            if (digits[i] > digits[maxIdx]) {
                maxIdx = i; // Update the max index
            } else if (digits[i] < digits[maxIdx]) {
                // Found a potential swap
                leftIdx = i;
                rightIdx = maxIdx;
            }
        }

        // If a swap is possible, perform it
        if (leftIdx != -1) {
            char temp = digits[leftIdx];
            digits[leftIdx] = digits[rightIdx];
            digits[rightIdx] = temp;
        }

        // Return the result as an integer
        return Integer.parseInt(new String(digits));
    }
}

▶️ View Animation

🎥 Video Explanation

For a detailed explanation, watch this video: Maximum Swap Problem Explanation by NeetCode IO

📊 Time Complexity

• Time Complexity: O(N), where N is the number of digits in the input number.
• Space Complexity: O(1), as we use only a constant amount of extra space.

✅ Use Cases

• Maximizing the value of a number with minimal changes.
• Solving problems involving digit manipulation.

📘 Common LeetCode Problems

• 670. Maximum Swap [Medium] Greedy

🧪 Example

Input: num = 2736
Output: 7236

Explanation:
- Swap the digits 2 and 7 to get the largest number 7236.

💡 Pro Tips

• Use a greedy approach to find the first digit that can be swapped to maximize the number.
• Keep track of the last occurrence of each digit to efficiently find the best swap.
• If no swap is possible, return the original number.