Maximum Value after Insertion — Problem & Solution
Maximum Value after Insertion solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Value after Insertion is a medium coding problem on strings and greedy, asked in Amazon and Adobe interviews.
- Difficulty: Medium
- Topics: Strings, Greedy
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a very large integer n written as a string, and a single digit x. Every digit of n and x itself is between 1 and 9, and n may be negative, in which case it starts with '-'.
Insert x once anywhere among the digits of n (not to the left of a minus sign) so that the resulting number is as large as possible, and return it as a string.
For a negative number, larger means closer to zero: -123 is larger than -321.
Example 1
Input: n = "73", x = 6
Output: 763
Explanation: The options are 673, 763 and 736; the largest is 763.
Example 2
Input: n = "-13", x = 2
Output: -123
Explanation: The options are -213, -123 and -132; the largest is -123.
Example 3
Input: n = "99", x = 9
Output: 999
Constraints
1 <= n.length <= 10^51 <= x <= 9the digits of n are in the range [1, 9]n is a valid representation of an integer; a negative n begins with '-'
Hints for Maximum Value after Insertion
Hint 1
Every candidate has the same number of digits, so comparing them is comparing the digit strings from the left.
Hint 2
For a positive number you want
xas early as possible — but only once it beats the digit it displaces.Hint 3
Positive: insert before the first digit smaller than
x. Negative: insert before the first digit larger thanx. If there is none, appendxat the end.
How to solve Maximum Value after Insertion
All results have equal length, so the first position where two candidates differ decides. Place x as early as it improves that first differing digit.
Approach
- If
nis positive, scan its digits from the left and insertxbefore the first digit strictly smaller thanx. - If
nis negative, skip the-and insertxbefore the first digit strictly larger thanx(a smaller magnitude means a larger negative number). - If the scan finds no such digit, append
xat the end.
Why it works
Inserting x before digit i leaves digits 0..i-1 untouched and puts x at position i. For a positive n, if n[i] >= x the candidate that keeps n[i] there is at least as large at the first differing spot, so we keep scanning; the first time n[i] < x, putting x there wins at position i against every later insertion point. For a negative n the magnitude should be as small as possible, which flips the comparison.
Complexity
- Time —
O(n) - Space —
O(n) for the output string
Pitfalls
- Use strict comparisons: when the digit equals
x, inserting before or after it gives the same string, and continuing is what keeps the scan correct for later digits. - Never insert before the minus sign.
- Do not convert
nto a number — it can have 100,000 digits.
Reference solution
Python
def maxValue(n: str, x: int) -> str:
d = str(x)
if n[0] == "-":
for i in range(1, len(n)):
if n[i] > d:
return n[:i] + d + n[i:]
return n + d
for i in range(len(n)):
if n[i] < d:
return n[:i] + d + n[i:]
return n + dJava
public static String maxValue(String n, int x) {
char d = (char) ('0' + x);
int len = n.length();
if (n.charAt(0) == '-') {
for (int i = 1; i < len; i++) if (n.charAt(i) > d) return n.substring(0, i) + d + n.substring(i);
return n + d;
}
for (int i = 0; i < len; i++) if (n.charAt(i) < d) return n.substring(0, i) + d + n.substring(i);
return n + d;
}C++
string maxValue(string n, int x) {
char d = (char)('0' + x);
int len = n.size();
if (n[0] == '-') {
for (int i = 1; i < len; i++) if (n[i] > d) return n.substr(0, i) + d + n.substr(i);
return n + d;
}
for (int i = 0; i < len; i++) if (n[i] < d) return n.substr(0, i) + d + n.substr(i);
return n + d;
}JavaScript
var maxValue = function(n, x) {
var d = String(x);
if (n[0] === "-") {
for (var i = 1; i < n.length; i++) if (n[i] > d) return n.slice(0, i) + d + n.slice(i);
return n + d;
}
for (var j = 0; j < n.length; j++) if (n[j] < d) return n.slice(0, j) + d + n.slice(j);
return n + d;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms