Maximum Value after Insertion

Medium
1227.

Maximum Value after Insertion

Maximum Value after Insertion is a medium coding problem on strings and greedy, asked in Amazon and Adobe interviews.

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^5
  • 1 <= x <= 9
  • the digits of n are in the range [1, 9]
  • n is a valid representation of an integer; a negative n begins with '-'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} n
 * @param {number} x
 * @return {string}
 */
var maxValue = function(n, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= x <= 9
  • the 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

  1. Hint 1

    Every candidate has the same number of digits, so comparing them is comparing the digit strings from the left.

  2. Hint 2

    For a positive number you want x as early as possible — but only once it beats the digit it displaces.

  3. Hint 3

    Positive: insert before the first digit smaller than x. Negative: insert before the first digit larger than x. If there is none, append x at 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

  1. If n is positive, scan its digits from the left and insert x before the first digit strictly smaller than x.
  2. If n is negative, skip the - and insert x before the first digit strictly larger than x (a smaller magnitude means a larger negative number).
  3. If the scan finds no such digit, append x at 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 n to 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 + d

Java

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