{x}
blog image

Maximum Value after Insertion

You are given a very large integer n, represented as a string,​​​​​​ and an integer digit x. The digits in n and the digit x are in the inclusive range [1, 9], and n may represent a negative number.

You want to maximize n's numerical value by inserting x anywhere in the decimal representation of n​​​​​​. You cannot insert x to the left of the negative sign.

  • For example, if n = 73 and x = 6, it would be best to insert it between 7 and 3, making n = 763.
  • If n = -55 and x = 2, it would be best to insert it before the first 5, making n = -255.

Return a string representing the maximum value of n​​​​​​ after the insertion.

 

Example 1:

Input: n = "99", x = 9
Output: "999"
Explanation: The result is the same regardless of where you insert 9.

Example 2:

Input: n = "-13", x = 2
Output: "-123"
Explanation: You can make n one of {-213, -123, -132}, and the largest of those three is -123.

 

Constraints:

  • 1 <= n.length <= 105
  • 1 <= x <= 9
  • The digits in n​​​ are in the range [1, 9].
  • n is a valid representation of an integer.
  • In the case of a negative n,​​​​​​ it will begin with '-'.

Solution Explanation for LeetCode 1881: Maximum Value after Insertion

This problem asks us to find the maximum numerical value achievable by inserting a digit x into a string representation of a large integer n. The solution hinges on a greedy approach that leverages the observation that the optimal placement of x depends solely on whether n is positive or negative.

Core Idea:

The optimal insertion point for x is determined by comparing x with the digits of n.

  • Positive n: We insert x before the first digit in n that is smaller than x. This ensures we create the largest possible number. If no such digit exists, x is appended at the end.

  • Negative n: We insert x before the first digit in n (excluding the negative sign) that is larger than x. This minimizes the absolute value of the resulting negative number, thus maximizing its numerical value. If no such digit exists, x is appended at the end.

Algorithm:

  1. Handle Negative Sign: Check if n starts with "-". If so, store this sign and adjust the starting index for digit comparison.

  2. Iterate and Compare: Iterate through the digits of n (starting from the appropriate index based on the sign). For positive n, we find the first digit smaller than x; for negative n, we find the first digit larger than x.

  3. Insert and Return: Insert x at the index found in step 2. If no such index is found (meaning all digits satisfy the opposite comparison), append x to the end of n. Return the modified string.

Time and Space Complexity:

  • Time Complexity: O(m), where m is the length of the input string n. This is because we iterate through the string at most once.

  • Space Complexity: O(1). We use only a constant amount of extra space to store variables and indices.

Code Implementation (Python):

class Solution:
    def maxValue(self, n: str, x: int) -> str:
        i = 0
        if n[0] == "-":  # Handle negative numbers
            i += 1
            while i < len(n) and int(n[i]) <= x:
                i += 1
        else:  # Handle positive numbers
            while i < len(n) and int(n[i]) >= x:
                i += 1
        return n[:i] + str(x) + n[i:]

The code for other languages (Java, C++, Go, TypeScript, Rust, Javascript) follows a very similar structure, only differing in syntax. They all implement the same core algorithm described above. The string manipulation techniques (substring extraction and concatenation) might vary slightly based on the language, but the underlying logic remains consistent.