Watch 10 video solutions for Maximum Value after Insertion, a medium level problem involving String, Greedy. This walkthrough by Ayushi Sharma has 960 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |