LeetCode 1881 - Maximum Value after Insertion

LeetCode Problem 1881

Difficulty: 🟡 Medium
Topics: String, Greedy

Solution

Problem Understanding

This problem asks us to insert a single digit x into a very large integer n, represented as a string, in a position that maximizes the resulting numerical value.

The integer n can be either positive or negative. Since the number may be extremely large, up to 10^5 characters long, we cannot safely convert it to an integer type in most programming languages. Instead, we must work directly with the string representation.

For a positive number, maximizing the value means making the number as large as possible in the normal numerical sense. Since earlier digits contribute more to the overall value than later digits, we generally want to insert x as early as possible if it improves the number.

For a negative number, the situation is reversed. A number like -123 is larger than -523 because it is less negative. Therefore, to maximize a negative number, we want its magnitude to be as small as possible. This changes the insertion strategy.

The input consists of:

• n, a string representation of an integer
• x, a digit from 1 to 9

The output should be a string representing the maximum possible value after inserting x exactly once.

The constraints tell us several important things:

• n.length can be as large as 100000, which immediately rules out expensive algorithms such as generating all possible insertions and comparing them.
• Digits are guaranteed to be between 1 and 9, meaning there are no zeros in the input.
• Negative numbers always begin with '-'.
• Since the number may exceed normal integer limits, string manipulation is necessary.

There are several edge cases worth identifying early:

• If all digits are already larger than x in a positive number, then x should be appended at the end.
• If all digits are smaller than x in a positive number, x should be inserted near the front.
• For negative numbers, the comparison logic reverses because minimizing magnitude maximizes value.
• If x equals existing digits, multiple insertion positions may produce the same answer.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to try inserting x at every possible position in the string, compute the resulting number, and choose the maximum one.

For a string of length n, there are n + 1 possible insertion points. At each position, we create a new string with x inserted. Then we compare all generated candidates and keep the maximum.

This approach is correct because it exhaustively evaluates every valid insertion possibility, guaranteeing that the best answer is found.

However, it is inefficient. Creating each candidate string takes O(n) time, and we do this for n + 1 positions. Since comparisons may also cost O(n), the total complexity becomes O(n²). With n up to 10^5, this is too slow.

Optimal Greedy Approach

The key observation is that the insertion position can be determined greedily.

For a positive number, earlier digits matter more. We should insert x before the first digit that is smaller than x, because replacing a smaller leading digit with a larger one gives the greatest increase in value.

For example:

n = "469" and x = 5

We scan left to right:

• 4 < 5, insert immediately

Result: "5469"

Any later insertion would be smaller because the first digit would remain 4.

For a negative number, maximizing the value means minimizing the absolute magnitude. We should insert x before the first digit that is larger than x, making the number less negative.

For example:

n = "-763" and x = 5

We scan after the minus sign:

• 7 > 5, insert immediately

Result: "-5763"

This makes the magnitude smaller compared to inserting later.

Since we only scan once and insert at the best position immediately, the solution runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n²)	Try every insertion position and compare results
Optimal	O(n)	O(n)	Single greedy scan to find the best insertion point

Algorithm Walkthrough

1. Convert x into a string so it can be inserted into n.
2. Check whether n is negative by testing if the first character is '-'.
3. If n is positive, scan from left to right and look for the first digit smaller than x.

• If digit < x, insert x before that digit.
• This works because earlier positions have greater significance in decimal representation.

4. If no such digit is found, append x at the end.

• This means every digit was already greater than or equal to x.

5. If n is negative, skip the minus sign and scan the digits.

• Look for the first digit greater than x.

6. When digit > x, insert x before that digit.

• This minimizes the negative magnitude as early as possible.

7. If no valid insertion point exists, append x to the end.

Why it works

The greedy choice works because decimal numbers are lexicographically determined by earlier digits. For positive numbers, inserting x before the first smaller digit maximizes the most significant differing position. For negative numbers, inserting x before the first larger digit minimizes the magnitude at the earliest possible position. Since earlier positions dominate later ones, any delayed insertion would produce a worse result.

Python Solution

class Solution:
    def maxValue(self, n: str, x: int) -> str:
        digit = str(x)

        # Negative number
        if n[0] == '-':
            for i in range(1, len(n)):
                if n[i] > digit:
                    return n[:i] + digit + n[i:]

            return n + digit

        # Positive number
        for i in range(len(n)):
            if n[i] < digit:
                return n[:i] + digit + n[i:]

        return n + digit

The implementation begins by converting x into a string so comparisons can be made directly against characters in n.

The first major branch checks whether the number is negative. If n[0] == '-', we skip index 0 because insertion is not allowed before the minus sign.

For negative numbers, the code searches for the first digit larger than x. Once found, it inserts x immediately and returns the result. Returning immediately is important because the earliest valid position is always optimal.

If no such digit exists, the digit is appended at the end.

For positive numbers, the logic is symmetrical but with reversed comparison. We search for the first digit smaller than x. Once found, insertion occurs immediately.

If the scan finishes without finding a valid position, appending at the end produces the largest possible value.

Go Solution

func maxValue(n string, x int) string {
	digit := byte('0' + x)

	// Negative number
	if n[0] == '-' {
		for i := 1; i < len(n); i++ {
			if n[i] > digit {
				return n[:i] + string(digit) + n[i:]
			}
		}

		return n + string(digit)
	}

	// Positive number
	for i := 0; i < len(n); i++ {
		if n[i] < digit {
			return n[:i] + string(digit) + n[i:]
		}
	}

	return n + string(digit)
}

The Go implementation follows exactly the same greedy logic as the Python version.

Instead of converting x into a string, we create a byte representation using:

digit := byte('0' + x)

This works because ASCII digits are consecutive.

String slicing in Go is efficient for this problem because we only perform one insertion after a single scan. Since the input size can reach 10^5, avoiding repeated allocations inside loops is important.

Integer overflow is not a concern because the algorithm never converts the number into an integer type. Everything is handled as string manipulation.

Worked Examples

Example 1

Input:

n = "99"
x = 9

Since the number is positive, we look for the first digit smaller than 9.

Index	Current Digit	Condition (digit < 9)	Action
0	9	False	Continue
1	9	False	Continue

No valid insertion point exists.

Result:

"999"

Example 2

Input:

n = "-13"
x = 2

Since the number is negative, we look for the first digit greater than 2.

Index	Current Digit	Condition (digit > 2)	Action
1	1	False	Continue
2	3	True	Insert before 3

Result:

"-123"

Additional Example

Input:

n = "469"
x = 5

Positive number.

Index	Current Digit	Condition (digit < 5)	Action
0	4	True	Insert before 4

Result:

"5469"

Additional Negative Example

Input:

n = "-763"
x = 5

Negative number.

Index	Current Digit	Condition (digit > 5)	Action
1	7	True	Insert before 7

Result:

"-5763"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single left to right scan through the string
Space	O(n)	Result string construction requires linear space

The algorithm only scans the string once to determine the optimal insertion position, giving linear time complexity. Although the scan itself uses constant extra memory, string slicing and concatenation create a new string of length n + 1, so the total space complexity is O(n).

Test Cases

sol = Solution()

# Provided examples
assert sol.maxValue("99", 9) == "999"  # same digit everywhere
assert sol.maxValue("-13", 2) == "-123"  # negative insertion

# Positive number cases
assert sol.maxValue("73", 6) == "763"  # insert in middle
assert sol.maxValue("123", 9) == "9123"  # insert at front
assert sol.maxValue("987", 1) == "9871"  # append at end
assert sol.maxValue("555", 5) == "5555"  # equal digits

# Negative number cases
assert sol.maxValue("-55", 2) == "-255"  # insert near front
assert sol.maxValue("-123", 9) == "-1239"  # append at end
assert sol.maxValue("-987", 1) == "-1987"  # insert immediately

# Boundary values
assert sol.maxValue("1", 9) == "91"  # smallest length
assert sol.maxValue("9", 1) == "91"  # append case
assert sol.maxValue("-1", 9) == "-19"  # negative single digit

# Stress style cases
assert sol.maxValue("111111", 9) == "9111111"  # large leading insertion
assert sol.maxValue("999999", 1) == "9999991"  # large append

Test	Why
"99", 9	Verifies equal digit behavior
"-13", 2	Confirms negative insertion logic
"73", 6	Tests insertion in the middle
"123", 9	Tests front insertion
"987", 1	Tests appending at the end
"555", 5	Ensures equal digits are handled
"-55", 2	Verifies early insertion for negatives
"-123", 9	Tests negative append case
"1", 9	Single digit boundary
"999999", 1	Large append scenario

Edge Cases

All Digits Are Larger Than x in a Positive Number

Consider:

n = "987"
x = 1

A buggy implementation might try to insert too early. Since every digit is already larger than 1, the best move is appending at the end. The implementation handles this correctly by completing the scan and returning n + digit.

All Digits Are Smaller Than x in a Positive Number

Consider:

n = "123"
x = 9

The optimal insertion point is the beginning because 9 is larger than every existing digit. The implementation finds the first digit smaller than 9 immediately and inserts at index 0.

Negative Numbers with Reversed Logic

Consider:

n = "-763"
x = 5

A common mistake is applying the same comparison logic used for positive numbers. That would incorrectly maximize the absolute magnitude. Instead, for negatives, we insert before the first digit greater than x, making the number less negative. The implementation explicitly branches into separate logic for negative values.

Equal Digits

Consider:

n = "999"
x = 9

Since inserting 9 anywhere gives the same result, the algorithm should remain stable and not insert unnecessarily early. Because the condition checks strictly < for positive numbers and > for negative numbers, equal digits are skipped naturally, and the digit is appended at the end.