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.
n = 73 and x = 6, it would be best to insert it between 7 and 3, making n = 763.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 <= 1051 <= x <= 9n are in the range [1, 9].n is a valid representation of an integer.n, it will begin with '-'.Problem Overview: You are given a numeric string n that may represent a positive or negative integer and a digit x. Insert x somewhere in the string so the resulting number is as large as possible. The tricky part is handling positive and negative numbers differently while keeping the operation efficient.
Approach 1: Try All Insertion Positions (Brute Force) (Time: O(n^2), Space: O(n))
The straightforward idea is to try inserting the digit x at every possible index in the string. For a string of length n, generate n + 1 candidate strings, convert or compare them as numbers, and track the maximum. Each insertion creates a new string of length n+1, so building and comparing candidates costs O(n) time. Overall complexity becomes O(n^2). This approach is easy to reason about but inefficient for large inputs.
Approach 2: Greedy Insertion Based on Sign (Time: O(n), Space: O(1))
A more efficient strategy comes from observing how digit placement affects numeric value. For positive numbers, you want the inserted digit to appear before the first digit that is smaller than x. This ensures the highest possible value because larger digits earlier increase the magnitude. Scan the string left to right and insert when x > current_digit. If no such position appears, append x at the end.
Negative numbers behave differently because a larger absolute value makes the number smaller. Here, you want the result to be as close to zero as possible. Insert x before the first digit that is greater than x. This reduces the magnitude of the negative number. If no such position exists, append the digit at the end. The algorithm only scans the string once and performs a single insertion.
This technique relies on a simple greedy rule and basic string traversal. No extra data structures are required, making the space complexity O(1) aside from the output string. The reasoning behind the rule is a classic example of a greedy decision: choose the earliest position that improves the final value.
Recommended for interviews: The greedy linear scan is the expected solution. Interviewers want to see that you recognize how digit ordering affects numeric value and adjust the rule for positive vs. negative numbers. Mentioning the brute force approach first demonstrates baseline problem analysis, but implementing the O(n) greedy solution shows strong algorithmic intuition.
This approach involves iterating through the string representation of the number and inserting the digit 'x' at the appropriate position to maximize the number. Consider whether the number is positive or negative:
Convert 'x' to a string. Based on whether 'n' is positive or negative, identify the correct position to insert 'x'. The function iterates through the digits of 'n', comparing each digit with 'x' to determine the first spot where inserting 'x' will maximize the number. If no such position is found, append 'x' to the end of 'n'.
Time Complexity: O(n) because we may need to iterate through all the digits of 'n'.
Space Complexity: O(1) since it operates in-place without additional data structures.
A variation of approach one, focusing on using built-in methods for insertion instead of manual iteration. This can help highlight optimized operations via built-in language features or libraries.
This Python solution similar to the previous but fewer condition checks leveraging Python's slicing capabilities to efficiently manage insertion.
Time Complexity: O(n), similar to approach one.
Space Complexity: O(1), in place string transformations.
If n is negative, we need to find the first position greater than x and insert x at that position. If n is positive, we need to find the first position less than x and insert x at that position.
The time complexity is O(m), where m is the length of n. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Insert Digit into Positive or Negative Number | Time Complexity: O(n) because we may need to iterate through all the digits of 'n'. |
| Optimizing Negative and Positive Insertion | Time Complexity: O(n), similar to approach one. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Try All Insertion Positions (Brute Force) | O(n^2) | O(n) | Useful for initial reasoning or very small inputs where simplicity matters |
| Greedy Sign-Based Insertion | O(n) | O(1) | Optimal approach for interviews and production; single scan of the string |
Maximum Value after Insertion 🔥| Leetcode 1881 | Contest 243 • Ayushi Sharma • 960 views views
Watch 9 more video solutions →Practice Maximum Value after Insertion with our built-in code editor and test cases.
Practice on FleetCode