Maximum Value after Insertion

Maximum Value after Insertion is a sign-aware greedy string problem. Scan from left to right and insert x at the first position where keeping the old digit would make the final number worse: before the first digit smaller than x for positive numbers, or before the first digit larger than x for negative numbers. If no such position appears, append x at the end.

Problem Statement

You are given a string n that represents a very large integer and a digit x from 1 to 9. The string may start with a minus sign, and if it does, you are not allowed to insert x before that sign. Your job is to place x somewhere in the decimal representation so the resulting integer is as large as possible.

This problem turns on how sign changes the greedy rule. For a positive number, you want larger digits as early as possible, so you insert x before the first digit that is smaller than x. For a negative number, the larger numerical value is the less negative one, so you instead insert x before the first digit that is greater than x. If no such digit exists, place x at the end.

Examples

Example 1

Input: n = "99", x = 9

Output: "999"

The result is the same regardless of where you insert 9.

Example 2

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

Output: "-123"

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 Approach

Use a sign-aware greedy scan

The core invariant is that earlier digits dominate later digits in lexicographic comparison for equal-length signed forms. For a positive n, the first place where digit < x is the earliest position that improves the value, so inserting later would miss a bigger prefix. For a negative n, maximizing the number means minimizing the magnitude after the minus sign, so the first place where digit > x is the best insertion point.

Handle positive and negative cases separately

If n does not start with -, scan every digit from left to right and insert x before the first digit smaller than x. If n starts with -, begin scanning after the sign and insert x before the first digit larger than x. This is the exact failure mode many candidates miss: reusing the positive comparison for negatives produces a more negative result instead of a larger number.

Build the answer in one pass

Once the insertion index is found, return the prefix plus x plus the suffix. If the scan never finds a valid earlier position, append x at the end of the string. This keeps the solution linear and avoids unnecessary numeric conversion, which would break on the very large input size allowed by Maximum Value after Insertion.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

A single left-to-right scan finds the insertion point, and building the final string touches each character at most once, so the time complexity is O(n). The output string is one character longer than the input, so the space complexity is O(n) if you count the returned string, or O(1) extra space aside from output construction.

What Interviewers Usually Probe

• They mention that n is stored as a string because numeric conversion is unsafe at this size.
• They hint that the negative case is the same scan shape but with the opposite comparison rule.
• They care about the first valid insertion point, which is the greedy invariant that makes later positions suboptimal.

Common Pitfalls or Variants

Common pitfalls

• Using the positive-number rule on negative input and inserting before a smaller digit instead of a larger one.
• Trying every insertion position and comparing full candidate strings, which is unnecessary and too slow for n.length up to 10^5.
• Converting n into an integer type, which can overflow and also ignores that this is a string-order greedy problem.

Follow-up variants

• Return the minimum value after insertion instead of the maximum, which flips the comparison rule for both signs.
• Insert a digit into a non-negative decimal string with leading-zero rules, where the insertion condition must respect formatting constraints.
• Insert multiple digits from a second string, where the single-step greedy rule becomes a merge-style decision process.

FAQ

What is the main pattern in Maximum Value after Insertion?

It is a greedy string scan with an invariant about the earliest digit that improves the final value. For positive numbers, insert before the first digit smaller than x. For negative numbers, insert before the first digit larger than x because a smaller magnitude means a larger signed value.

Why is the first valid position always optimal?

Because earlier digits have more weight than later digits. Once you find a position where placing x improves the prefix, any later insertion keeps a worse prefix and cannot recover that loss with later digits.

Why does the negative case use the opposite comparison?

A negative number is larger when its absolute value is smaller. After the minus sign, you want the digit sequence to become smaller as early as possible, so you place x before the first digit that is greater than x.

Do equal digits matter in the insertion rule?

Yes. If the current digit equals x, inserting before it does not improve the prefix, so you keep scanning. That is why n = 99 and x = 9 can return 999 no matter where 9 is inserted.

Can I solve Maximum Value after Insertion by brute force?

You could generate every insertion and compare results, but that costs too much for long strings and hides the real interview insight. The intended solution is the one-pass greedy rule based on the sign and the first improving position.