Maximum Swap - Practice Coding Problems

Maximum Swap - Problem

Math Greedy Medium

You are given an integer num. You can swap two digits at most once to get the maximum valued number.

Return the maximum valued number you can get.

Input & Output

Example 1 — Basic Swap

$ Input: num = 2736

› Output: 7632

💡 Note: Swap the first digit 2 with the last digit 6 to get 6732, but the optimal is swapping 2 with 7 to get 7236, then we see swapping positions 1 and 3 gives 7632 which is maximum.

Example 2 — No Improvement Possible

$ Input: num = 9973

› Output: 9973

💡 Note: The digits are already in optimal order from left to right, no single swap can improve the value.

Example 3 — Single Digit

$ Input: num = 1

› Output: 1

💡 Note: Single digit number cannot be improved by swapping.

Constraints

0 ≤ num ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer number as sequence of digits

Process

Find optimal single swap to maximize value

Output

Return maximum possible number after swap

Key Takeaway

🎯 Key Insight: Use greedy approach to find the leftmost position that can be improved by swapping with the rightmost occurrence of a larger digit

Asked in

F Facebook 25 G Google 15

The key insight is to use a greedy approach: record the rightmost position of each digit, then scan from left to find the first position that can be improved by swapping with a larger digit from the right. Best approach is greedy single-pass. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Find Best Single Swap	O(n)	O(1)	Use greedy approach to find the optimal single swap efficiently
Brute Force - Try All Swaps	O(n²)	O(n)	Try every possible pair of digits to swap and return the maximum result

Greedy - Find Best Single Swap — Algorithm Steps

Step 1: Record the rightmost position of each digit (0-9)
Step 2: Scan from left, for each position find the largest digit that appears later
Step 3: When found, swap with the rightmost occurrence of that larger digit
Step 4: Return the result after the single optimal swap

Visualization

Tap to expand

Step-by-Step Walkthrough

Record Positions

Track rightmost position of each digit

Scan Left to Right

Find first improvable position

Make Optimal Swap

Swap with rightmost larger digit

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int num) {
    char digits[20];
    sprintf(digits, "%d", num);
    int n = strlen(digits);
    
    // Record the rightmost position of each digit
    int lastPos[10];
    for (int i = 0; i < 10; i++) {
        lastPos[i] = -1;
    }
    for (int i = 0; i < n; i++) {
        lastPos[digits[i] - '0'] = i;
    }
    
    // Find the first position where we can make a beneficial swap
    for (int i = 0; i < n; i++) {
        // Try to find a larger digit that appears later
        for (int digit = 9; digit > digits[i] - '0'; digit--) {
            if (lastPos[digit] > i) {
                // Swap with the rightmost occurrence of this larger digit
                int j = lastPos[digit];
                char temp = digits[i];
                digits[i] = digits[j];
                digits[j] = temp;
                return atoi(digits);
            }
        }
    }
    
    // No beneficial swap found
    return num;
}

int main() {
    int num;
    scanf("%d", &num);
    int result = solution(num);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to record positions + single pass to find best swap

✓ Linear Growth

Space Complexity

O(1)

Only need array of size 10 to track digit positions + string conversion

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Find Best Single Swap — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler