Skip to main content
Talentd

Maximum Value after Insertion - Solution & Explanation

MediumStringGreedy15 min readAsked at: Amazon
Practice this problem

Problem Statement

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.

  • For example, if n = 73 and x = 6, it would be best to insert it between 7 and 3, making n = 763.
  • If 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 <= 105
  • 1 <= x <= 9
  • The digits in n​​​ are in the range [1, 9].
  • n is a valid representation of an integer.
  • In the case of a negative n,​​​​​​ it will begin with '-'.

Approach Overview

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 1: Insert Digit into Positive or Negative Number

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:

  • If the number is positive, insert 'x' at the first position where 'x' is greater than the current digit.
  • If the number is negative, insert 'x' at the first position where 'x' is less than the current digit, after the negative sign.

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'.

Code

PythonCC++JavaC#JavaScript

Python

C

C++

Java

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Optimizing Negative and Positive Insertion

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.

Code

PythonCC++JavaC#JavaScript

Python

C

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n), similar to approach one.
Space Complexity: O(1), in place string transformations.

Try this approach in the editor →

Approach 3: Greedy

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).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Insert Digit into Positive or Negative Number

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.

Optimizing Negative and Positive Insertion

Time Complexity: O(n), similar to approach one.
Space Complexity: O(1), in place string transformations.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 InsertionO(n)O(1)Optimal approach for interviews and production; single scan of the string

Video Solution

Maximum Value after Insertion 🔥| Leetcode 1881 | Contest 243 • Ayushi Sharma • 965 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Value after Insertion easy or hard?
Maximum Value after Insertion is typically classified as a Medium problem. The implementation is short, but the challenge is recognizing that positive and negative numbers require different greedy insertion rules.
Maximum Value after Insertion Python/Java solution
In Python or Java, iterate through the string representation of the number and check each digit against x using the greedy rule. Once the correct index is found, build the new string using substring concatenation. The implementation runs in O(n) time.
How to solve Maximum Value after Insertion in O(n)?
Traverse the number string once. If the number is positive, insert the digit x before the first digit smaller than x. If the number is negative, insert x before the first digit greater than x to minimize the negative magnitude. If no position satisfies the condition, append the digit at the end.
What is the best approach for Maximum Value after Insertion?
The optimal solution uses a greedy string scan. For positive numbers, insert the digit before the first digit smaller than x. For negative numbers, insert before the first digit larger than x. This guarantees the maximum possible value in O(n) time and O(1) extra space.
Is Maximum Value after Insertion asked at Google/Amazon/Meta?
Greedy string manipulation problems like this appear frequently in interviews at large tech companies including Amazon, Google, and Meta. Variants that involve inserting digits or modifying numeric strings to optimize value are common screening questions.
What data structure is used in Maximum Value after Insertion?
The problem primarily uses string processing with a greedy traversal. No complex data structures are required—just iterating through characters and constructing the resulting string after determining the insertion position.
What is the time complexity of Maximum Value after Insertion?
The optimal greedy approach runs in O(n) time where n is the length of the number string, because the algorithm scans the string once to find the correct insertion point. Space complexity is O(1) excluding the output string.

Ready to solve this problem?

Practice Maximum Value after Insertion with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring