Maximum Value After Insertion - Leetcode Solution

Problem Statement:

You are given a very large integer n, represented as a string, and an integer digit x. The digits of the integer n are numbered from 1 to n's length in left to right order.

You want to insert x into n such that n will be the maximum number possible. You can insert x anywhere in the string.

Return the maximum number you can get without changing the order of the digits.

Solution:

To find the maximum number after the insertion, we need to find the rightmost index where we can insert the digit x to get the maximum value. To do this, we can traverse the string n from left to right and find the first index i where the digit at index i is less than the digit x.

Once we find such an index i, we can insert the digit x at index i and return the new string as the answer.

If we do not find any such index i, it means that all the digits in the string n are greater than or equal to the digit x. In this case, we can insert x at the end of the string n to get the maximum value.

Here is the implementation of the above approach:

def maxValue(n: str, x: int) -> str: # initialize the flag to False flag = False

# iterate the string from left to right
for i in range(len(n)):
    # if the digit at index i is less than x
    if n[i] < str(x):
        # insert x at index i and return the new string
        return n[:i] + str(x) + n[i:]
    
    # if the digit at index i is greater than x
    elif n[i] > str(x):
        # set the flag to true
        flag = True
        
# if all the digits are greater than or equal to x
# insert x at the end of the string
if flag:
    return n + str(x)

# if all the digits are less than or equal to x
# insert x at the beginning of the string
else:
    return str(x) + n

Time Complexity:

The time complexity of the above implementation is O(n), where n is the length of the given string n.

Space Complexity:

The space complexity of the above implementation is O(n), where n is the length of the given string n.

1