Scale Engineer

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

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.

import java.math.BigInteger; class Solution {    public String maxValue(String n, int x) {        String maxString = null;        BigInteger maxVal = null;         // Determine the starting position for insertion.        // For negative numbers, we cannot insert before the '-'.        int start = n.charAt(0) == '-' ? 1 : 0;                // Iterate through all possible insertion points.        for (int i = start; i <= n.length(); i++) {            StringBuilder sb = new StringBuilder(n);            sb.insert(i, x);            String currentString = sb.toString();            BigInteger currentVal = new BigInteger(currentString);             // If it's the first one or the current value is greater, update max.            if (maxVal == null || currentVal.compareTo(maxVal) > 0) {                maxVal = currentVal;                maxString = currentString;            }        }        return maxString;    }}

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.

Solutions

class Solution {public  String maxValue(String n, int x) {    int i = 0;    if (n.charAt(0) != '-') {      for (; i < n.length() && n.charAt(i) - '0' >= x; ++i)        ;    } else {      for (i = 1; i < n.length() && n.charAt(i) - '0' <= x; ++i)        ;    }    return n.substring(0, i) + x + n.substring(i);  }}

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 →

Next problem