670. Maximum Swap

Time: O(n)

Space: O(1)

Intuition

Swap at most one pair of digits to maximize. For each digit from left to right, find if there's a larger digit to its right (rightmost occurrence). Swap with first such opportunity.

Algorithm

1Store last occurrence index of each digit (0-9).
2From left to right, for each digit d: check if there's a larger digit (9 down to d+1) whose last occurrence is to the right.
3If found, swap and return.

Example Walkthrough

Input: num=2736

1.Last[6]=3, last[7]=2, last[3]=1, last[2]=0.
2.Index 0: digit=2, check 9..3: 7 at idx 2 > 0 → swap. 7236.

Output: 7236

Common Pitfalls

•Use the rightmost occurrence of the larger digit to ensure maximum gain.

670.cs

// Approach: Record the last occurrence of each digit 0–9; for each position
// find the rightmost larger digit and do a single swap.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MaximumSwap(int num)
    {
        char[] s = num.ToString().ToCharArray();
        int[] lastIndex = new int[10]; // {digit: last index}

        for (int i = 0; i < s.Length; ++i)
            lastIndex[s[i] - '0'] = i;

        for (int i = 0; i < s.Length; ++i)
        {
            for (int d = 9; d > s[i] - '0'; --d)
            {
                if (lastIndex[d] > i)
                {
                    s[lastIndex[d]] = s[i];
                    s[i] = (char)('0' + d);
                    return int.Parse(new string(s));
                }
            }
        }

        return num;
    }
}

Was this solution helpful?