Maximum Number by One Swap

You are provided with an array of N integers representing the digits of a number. You are allowed to perform an operation where you can swap the values at two different indices to form a maximum possible number. The operation can be used at most once.

Example:

Input:

array = [1, 3, 2, 7]

Output:

[7, 3, 2, 1]

Explanation:

From the array, the number represented is 1327. By swapping elements, the largest number 7321 is obtained by swapping the first and last digits.

Constraints:

1

Question

Maximum Number by One Swap

You are provided with an array of N integers representing the digits of a number. You are allowed to perform an operation where you can swap the values at two different indices to form a maximum possible number. The operation can be used at most once.

Example:

Input:

array = [1, 3, 2, 7]

Output:

[7, 3, 2, 1]

Explanation:

From the array, the number represented is 1327. By swapping elements, the largest number 7321 is obtained by swapping the first and last digits.

Constraints:

1 <= T <= 100
2 <= N <= 10⁴
0 <= A[i] <= 9
Where 'A[i]' refers to the 'ith' element of the array.
Time limit: 1 second

Note:

Arrays might have leading zeros, such as [0, 3, 5, 7], which represents the number 357.

Accepted Answer

def find_maximum_number(arr):
    n = len(arr)
    
    # Convert the array to a string for easy manipulation
    str_arr = list(map(str, arr))
    
    # Find the last occurrence of each digit
    last_occurrence = {int(x): i for i, x in enumerate(str_arr)}
    
    # Iterate through the array to find the first place where a swap can maximize the number
    for i in range(n):
        current_digit = int(str_arr[i])
        
        # Check for a larger digit to the right of the current position
        for d in range(9, current_digit, -1):
            if d in last_occurrence and last_occurrence[d] > i:
                # Swap the current digit with the larger digit found
                str_arr[i], str_arr[last_occurrence[d]] = str_arr[last_occurrence[d]], str_arr[i]
                
                # Return the maximum number formed
                return int(''.join(str_arr))
    
    # If no swap is made, the number is already the largest possible
    return int(''.join(str_arr))

# Example usage
arr = [2, 3, 1, 9, 5]
print(find_maximum_number(arr))  # Output: 93125