Problem Description

You are given a string representation of an integer n (which may be negative), and a digit x (0 ≤ x ≤ 9). Your task is to insert x anywhere in the string n such that the resulting integer (after insertion) is maximized. The function should return the resulting string.

• The input n is a string, which can be positive or negative (may start with a minus sign).
• You can insert x at any position (including at the beginning or end).
• Return the resulting string value after the optimal insertion.

Constraints:

• 1 ≤ n.length ≤ 10⁵
• n consists of digits, and may start with a minus sign for negative numbers.
• 0 ≤ x ≤ 9

Thought Process

At first glance, you might consider trying every possible position to insert x and then comparing the resulting numbers to find the maximum. However, with large input sizes, this brute-force approach would be inefficient.

Instead, we can observe that to maximize the value:

• If n is positive, we want x to appear as early as possible, but only before a digit that is less than x.
• If n is negative, the number becomes less negative (and thus larger) if we insert x before the first digit that is greater than x.

Solution Approach

Let's break down the solution step by step:

1. Check if n is negative:
   • If n starts with '-', treat it as a negative number and process accordingly.
2. Iterate through the digits:
   • For positive numbers, scan from left to right. Insert x before the first digit that is less than x.
   • For negative numbers, scan from left to right (skipping the '-'). Insert x before the first digit that is greater than x.
3. Edge Cases:
   • If no such digit is found, insert x at the end of the string.
4. Return the result:
   • Construct the new string by inserting x at the identified position.

This approach ensures only one pass through the string, making it efficient for large inputs.

Example Walkthrough

Example 1:
n = "99", x = 9

• Scan from left to right: all digits (9) are equal to x.
• No digit is less than x, so insert x at the end.
• Result: "999"

Example 2:
n = "-13", x = 2

• Negative number, scan after '-'.
• First digit is 1, which is less than x (2), so keep scanning.
• Second digit is 3, which is greater than x (2).
• Insert x before 3: "-123"

Example 3:
n = "235", x = 4

• First digit is 2, which is less than 4.
• Insert before 2: "4235"

Time and Space Complexity

Brute-force approach:

• Try all possible insertions (O(N)), convert each to integer (O(N)), and find the max.
• Total time: O(N²), which is too slow for large inputs.
• Space: O(N) for temporary strings.

• Single scan through the string: O(N) time.
• Space: O(N) for the result string.

This makes the optimized approach efficient and scalable.

Summary

To maximize the value after inserting a digit into a number string, we scan the string once to find the optimal insertion point based on whether the number is positive or negative. This avoids unnecessary computation and leverages the properties of number ordering. The solution is elegant, efficient, and handles all edge cases, making it suitable for large inputs.

Code Implementation

def maxValue(n: str, x: int) -> str:
    x = str(x)
    if n[0] == '-':
        # Negative number: insert x before first digit > x
        for i in range(1, len(n)):
            if n[i] > x:
                return n[:i] + x + n[i:]
        return n + x
    else:
        # Positive number: insert x before first digit < x
        for i in range(len(n)):
            if n[i] < x:
                return n[:i] + x + n[i:]
        return n + x
      

class Solution {
public:
    string maxValue(string n, int x) {
        char c = x + '0';
        if (n[0] == '-') {
            // Negative number: insert x before first digit > x
            for (int i = 1; i < n.size(); ++i) {
                if (n[i] > c) {
                    return n.substr(0, i) + c + n.substr(i);
                }
            }
            return n + c;
        } else {
            // Positive number: insert x before first digit < x
            for (int i = 0; i < n.size(); ++i) {
                if (n[i] < c) {
                    return n.substr(0, i) + c + n.substr(i);
                }
            }
            return n + c;
        }
    }
};
      

class Solution {
    public String maxValue(String n, int x) {
        char c = (char) (x + '0');
        if (n.charAt(0) == '-') {
            // Negative number: insert x before first digit > x
            for (int i = 1; i < n.length(); ++i) {
                if (n.charAt(i) > c) {
                    return n.substring(0, i) + c + n.substring(i);
                }
            }
            return n + c;
        } else {
            // Positive number: insert x before first digit < x
            for (int i = 0; i < n.length(); ++i) {
                if (n.charAt(i) < c) {
                    return n.substring(0, i) + c + n.substring(i);
                }
            }
            return n + c;
        }
    }
}
      

var maxValue = function(n, x) {
    x = x.toString();
    if (n[0] === '-') {
        // Negative number: insert x before first digit > x
        for (let i = 1; i < n.length; ++i) {
            if (n[i] > x) {
                return n.slice(0, i) + x + n.slice(i);
            }
        }
        return n + x;
    } else {
        // Positive number: insert x before first digit < x
        for (let i = 0; i < n.length; ++i) {
            if (n[i] < x) {
                return n.slice(0, i) + x + n.slice(i);
            }
        }
        return n + x;
    }
};