Greedy: Get the maximum number by swapping once

Problem Statement:

Given a number, you need to swap 2 digits to make the maximum value of the number.

Example:

Input num = 1234

Output: 4231

Solution Explanation:

The solution is to find the maximum number by making at most one swap.

If we cannot find a better solution, then return original number.

Below is the approach for the solution:

1. Turn the number into string.

2. Start from right to left.

3. If the current digit is biggest so far, save it. if the current digit is smaller than the bigger one, mark it as swap candidate.

4. if we found 2 digits to swap, we swap them and return the result

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int solution (int num) 
{
    string numstr = to_string(num);

    int l = -1;   
    int r = -1; 
    int maxIndx = -1;   
    int maxDigit = -1;  

    for (int i = numstr.size() - 1; i >= 0; i--) 
    {
        if (numstr[i] - '0' > maxDigit) 
        {
            maxDigit = numstr[i] - '0';
            maxIndx = i;
        }
        else if (numstr[i] - '0' < maxDigit) 
        {
            l = i;
            r = maxIndx;
        }
    }

    if (l == -1) 
    	return num;

    swap(numstr[l], numstr[r]);

    return stoi(numstr);
}

int main() 
{
    int num = 1234;

    cout <<solution(num);
}

Output

4231