# Maximum Value after Insertion
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-value-after-insertion)
Canonical: https://scaleengineer.com/dsa/problems/maximum-value-after-insertion
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## Problem
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
## Brute Force: Generate and Compare All Possibilities
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Greedy Single-Pass Approach
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.
**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`.
**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.
### Explanation
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).

```java
class Solution {
    public String maxValue(String n, int x) {
        int len = n.length();
        boolean isNegative = n.charAt(0) == '-';
        
        // The loop finds the first position to insert.
        // For positive numbers, we look for the first digit < x.
        // For negative numbers, we look for the first digit > x.
        int i = isNegative ? 1 : 0;
        while (i < len) {
            int digit = n.charAt(i) - '0';
            if (isNegative) {
                if (x < digit) {
                    break; // Found insertion point for negative
                }
            } else { // Positive
                if (x > digit) {
                    break; // Found insertion point for positive
                }
            }
            i++;
        }
        
        // Use StringBuilder for efficient insertion.
        StringBuilder sb = new StringBuilder(n);
        sb.insert(i, x);
        return sb.toString();
    }
}
```
### 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"`).

# Solutions
### Java

```java
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);
  }
}

```

### JavaScript

```javascript
/** * @param {string} n * @param {number} x * @return {string} */ var maxValue =
  function (n, x) {
    let nums = [...n];
    let sign = 1,
      i = 0;
    if (nums[0] == " - ") {
      sign = -1;
      i++;
    }
    while (i < n.length && (nums[i] - x) * sign >= 0) {
      i++;
    }
    nums.splice(i, 0, x);
    return nums.join("");
  };

```

### CPP

```cpp
class Solution {
public:
  string maxValue(string n, int x) {
    int i = 0;
    if (n[0] != '-')
      for (; i < n.size() && n[i] - '0' >= x; ++i)
        ;
    else
      for (i = 1; i < n.size() && n[i] - '0' <= x; ++i)
        ;
    return n.substr(0, i) + to_string(x) + n.substr(i);
  }
};

```

### Python

```python
class 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 )
```