Maximum Value after Insertion

Med

#1717Time: O(L^2). The loop runs `O(L)` times. Inside the loop, string insertion using `StringBuilder.insert()` takes `O(L)`, and `BigInteger` creation and comparison also take `O(L)`. This results in a quadratic time complexity.Space: O(L), where L is the length of `n`. We need space to store the candidate strings and their `BigInteger` representations. The space required for each is proportional to L.

Patterns

Greedy

Data structures

String

Prompt

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 <= 10⁵
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 '-'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves generating every possible number that can be formed by inserting the digit x into the string n at all valid positions. Then, it compares these generated numbers to find the maximum one. This method is straightforward but computationally expensive.

Algorithm

Determine the starting index for insertion (0 for positive numbers, 1 for negative numbers).
Iterate through all possible insertion indices from the determined start index to the end of the string (n.length()).
For each index, construct a new candidate string by inserting the digit x.
Since the number n can be very large, convert the candidate string to a BigInteger to handle its numerical value correctly.
Keep track of the string that corresponds to the maximum BigInteger value encountered so far.
After iterating through all possibilities, the string associated with the overall maximum value is the answer.

Walkthrough

The core idea is to systematically try every possible insertion point. For a string of length L, there are L+1 possible places to insert a new character. We generate each of these new strings.

To accurately compare the numerical values, especially given that n can be very large, we must use a data type that can handle arbitrary-precision integers, such as BigInteger in Java. We iterate, generate a candidate string, convert it to a BigInteger, and compare it with the maximum value found so far. If the new value is greater, we update our maximum.

For example, if n = "-13" and x = 2, the valid insertion indices are 1, 2, and 3 (after the '-' sign). This generates "-213", "-123", and "-132". Comparing their BigInteger values (-213, -123, -132), we find that -123 is the maximum.

1import java.math.BigInteger;2 3class Solution {4    public String maxValue(String n, int x) {5        String maxString = null;6        BigInteger maxVal = null;7 8        // Determine the starting position for insertion.9        // For negative numbers, we cannot insert before the '-'.10        int start = n.charAt(0) == '-' ? 1 : 0;11        12        // Iterate through all possible insertion points.13        for (int i = start; i <= n.length(); i++) {14            StringBuilder sb = new StringBuilder(n);15            sb.insert(i, x);16            String currentString = sb.toString();17            BigInteger currentVal = new BigInteger(currentString);18 19            // If it's the first one or the current value is greater, update max.20            if (maxVal == null || currentVal.compareTo(maxVal) > 0) {21                maxVal = currentVal;22                maxString = currentString;23            }24        }25        return maxString;26    }27}

Complexity

Time

O(L^2). The loop runs `O(L)` times. Inside the loop, string insertion using `StringBuilder.insert()` takes `O(L)`, and `BigInteger` creation and comparison also take `O(L)`. This results in a quadratic time complexity.

Space

O(L), where L is the length of `n`. We need space to store the candidate strings and their `BigInteger` representations. The space required for each is proportional to L.

Trade-offs

Pros

Conceptually simple and easy to understand.
Guaranteed to find the correct answer by exploring the entire search space.

Cons

Highly inefficient with a time complexity of O(L^2), where L is the length of n.
Will likely result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the constraints.
Relies on the BigInteger class, which can introduce performance overhead compared to direct string or character manipulation.

A much more efficient approach is to use a greedy strategy. The decision of where to insert x can be made in a single pass through the string n. The logic hinges on the goal: for positive numbers, we want to make the number larger; for negative numbers, we want to make the number's magnitude smaller.

Algorithm

First, check if the number n is positive or negative by looking at its first character.
Case 1: n is positive. To maximize the value, we want to place x as far to the left as possible, before a digit that is smaller than x. Iterate from left to right (index 0 to len-1) and find the first index i where the digit n[i] is numerically less than x.
Case 2: n is negative. To maximize the value (make it less negative), we want to make its magnitude as small as possible. This is achieved by placing x as far to the left as possible, before a digit that is larger than x. Iterate from left to right (index 1 to len-1) and find the first index i where the digit n[i] is numerically greater than x.
If an insertion index i is found in either case, insert x at that position and return the result. A StringBuilder is efficient for this operation.
If the loop completes without finding an insertion point, it means x should be appended to the end of the string n to satisfy the condition (e.g., for n="765", x=4, result is "7654").

Walkthrough

The key insight is that a number's value is most influenced by its most significant digits (those on the left).

For Positive Numbers: To make a number n larger, we should insert x at the leftmost position i such that x is greater than the digit originally at n[i]. This places a larger digit at a higher-value position, guaranteeing the maximum possible result. For example, given n = "73" and x = 6, we scan left-to-right. 7 is not less than 6. 3 is less than 6. So we insert 6 before 3 to get "763".

For Negative Numbers: To make a negative number larger (i.e., closer to zero), we must make its absolute value smaller. We do this by inserting x at the leftmost position i (after the '-' sign) such that x is smaller than the digit originally at n[i]. This minimizes the magnitude at the most significant position possible. For example, given n = "-55" and x = 2, we scan left-to-right. The first 5 is greater than 2. We insert 2 before it to get "-255", which is greater than "-525" or "-552".

This greedy choice is optimal because any other placement would result in a smaller number (for the positive case) or a more negative number (for the negative case).

1class Solution {2    public String maxValue(String n, int x) {3        int len = n.length();4        boolean isNegative = n.charAt(0) == '-';5        6        // The loop finds the first position to insert.7        // For positive numbers, we look for the first digit < x.8        // For negative numbers, we look for the first digit > x.9        int i = isNegative ? 1 : 0;10        while (i < len) {11            int digit = n.charAt(i) - '0';12            if (isNegative) {13                if (x < digit) {14                    break; // Found insertion point for negative15                }16            } else { // Positive17                if (x > digit) {18                    break; // Found insertion point for positive19                }20            }21            i++;22        }23        24        // Use StringBuilder for efficient insertion.25        StringBuilder sb = new StringBuilder(n);26        sb.insert(i, x);27        return sb.toString();28    }29}

Complexity

Time

O(L), where L is the length of `n`. We perform a single pass to find the insertion point, which takes O(L) time. The insertion into a `StringBuilder` also takes O(L) time in the worst case (if insertion is at the beginning), as it requires shifting subsequent characters. This is the optimal time complexity for this problem.

Space

O(L). A `StringBuilder` or a new string is created to hold the result, which requires space proportional to the length of `n`.

Trade-offs

Pros

Optimal time complexity of O(L).
Extremely efficient and easily passes for large inputs.
Avoids costly BigInteger conversions by using direct character comparisons.

Cons

The logic is split into two distinct cases (positive and negative), which requires careful implementation to avoid errors.

Solutions

Solution

1class Solution {2public3  String maxValue(String n, int x) {4    int i = 0;5    if (n.charAt(0) != '-') {6      for (; i < n.length() && n.charAt(i) - '0' >= x; ++i)7        ;8    } else {9      for (i = 1; i < n.length() && n.charAt(i) - '0' <= x; ++i)10        ;11    }12    return n.substring(0, i) + x + n.substring(i);13  }14}

1/** * @param {string} n * @param {number} x * @return {string} */ var maxValue =2  function (n, x) {3    let nums = [...n];4    let sign = 1,5      i = 0;6    if (nums[0] == " - ") {7      sign = -1;8      i++;9    }10    while (i < n.length && (nums[i] - x) * sign >= 0) {11      i++;12    }13    nums.splice(i, 0, x);14    return nums.join("");15  };

1class Solution {2public:3  string maxValue(string n, int x) {4    int i = 0;5    if (n[0] != '-')6      for (; i < n.size() && n[i] - '0' >= x; ++i)7        ;8    else9      for (i = 1; i < n.size() && n[i] - '0' <= x; ++i)10        ;11    return n.substr(0, i) + to_string(x) + n.substr(i);12  }13};

1class Solution : def maxValue ( self , n : str , x : int ) -> str : if n [ 0 ] != '-' : for i , c in enumerate ( n ): if int ( c ) < x : return n [: i ] + str ( x ) + n [ i :] return n + str ( x ) else : for i , c in enumerate ( n [ 1 :]): if int ( c ) > x : return n [: i + 1 ] + str ( x ) + n [ i + 1 :] return n + str ( x )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem