670. Maximum Swap

MediumView on LeetCode

Greedy Math

Time: O(n)

Space: O(1)

Problem Overview

Swap at most one pair of digits to maximize.

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?