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

Given an array of integers representing digits of a number, swap two values to form the maximum possible number.

Iterate through the array to find the maximum digit.
Swap the maximum digit with the first digit if it is not already at the first position.
Handle cases where there are multiple occurrences of the maximum digit.

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

Asked in JPMorgan Chase & Co.