1881. Maximum Value after Insertion

MediumGreedyString
Leetcode Link

Problem Description

The problem presents us with two input values: a large integer n represented as a string and an integer digit x which range from 1 to 9. The goal is to insert the digit x into the string representation of n in such a way that the resulting number is maximized. If n is negative, x can be inserted anywhere except before the minus sign.

Here are some key points to keep in mind:

  • We can insert x in between any two digits of n.
  • The challenge is to figure out the most optimal position for x to achieve the largest possible value.
  • The comparison of where to insert x differs based on whether n is negative or positive.

Intuition

The intuition behind the solution stems from understanding how numerical value is affected by the placement of digits. For positive numbers, placing a larger digit towards the left increases the number's value. Thus, for a positive n, we look for the first instance where x is greater than a digit in n, and insert x before this digit to maximize the value.

Conversely, for negative numbers, we want to minimize the value of the negative magnitude to maximize n's value. Therefore, we look for the first digit in n that is smaller than x, and insert x after this digit to ensure the negative number is as small as Ppossible (which makes n as large as possible in the negative domain).

Here’s the step-by-step breakdown of our approach:

  1. If n is positive, iterate through its digits.

    • Find the position where the current digit is smaller than x.
    • Insert x before this digit and return the modified string.

  2. If n is negative, skip the minus sign and iterate through the remaining digits.

    • Find the position where the current digit is larger than x.
    • Insert x after this digit, accounting for the skipped minus sign, and return the modified string.

  3. If no such position is found in the above iterations (all digits of n are either larger than x for positive n, or smaller/equal to x for negative n), insert x at the end of the string.

By following this rule, the solution ensures that n's value is maximized according to the problem's constraints.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following uses divide and conquer strategy?

Solution Approach

The implementation of the solution follows the intuition previously explained. The algorithm is straightforward and can be summarized into the following steps:

  1. Check the Sign of n:

    • Determine if the number n is negative or positive by checking the first character of the string representation of n.

  2. Positive Case (n is not negative):

    • Loop through each digit in n using a for loop.
    • In every iteration, compare the current digit with the given digit x.
    • If the current digit is found to be less than x, use string slicing to insert x before this digit.
    • Return the modified string immediately.

  3. Negative Case (n is negative):

    • Similar to the positive case, use a for loop but start from the second character (skipping the negative sign).
    • Compare each digit with x.
    • If the current digit is greater than x, insert x before this digit.
    • Use string slicing while keeping in mind the negative sign's position (which is at index 0).
    • Return the modified string immediately.

  4. Appending to the End:

    • If the loop completes without finding a suitable position for insertion (which means x is less or equal to all digits in a positive n, or x is less than or equal to all digits in a negative n after the sign), append x at the end of n.

The algorithm does not use any additional data structures, and it relies solely on the properties of string slicing and built-in comparison operators in Python. The solution pattern is iterative and can be classified as a simple linear search, which finds the insertion point by comparing each digit of n with x.

The Python code handles the insertion and string manipulation tasks using concatenation, which adds the string representation of x to the appropriate slice of n. The solution effectively applies the basic concepts of string manipulation with time complexity O(n) where n represents the number of digits in the input string n.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the minimum element can be found in:

Example Walkthrough

Let's illustrate the solution approach with a small example where we have the integer n represented as the string "273" and the integer digit x as 4. The goal is to insert 4 into "273" such that the resulting number is as large as possible.

Following the solution steps:

  1. Check the Sign of n:

    • "273" does not start with a minus sign; therefore, the number is positive.

  2. Positive Case (n is not negative):

    • We start iterating through each digit in "273".
    • Compare first digit 2 with x (4).
    • 2 is less than 4, so this is where 4 should be inserted to maximize the number.
    • Use string slicing to insert 4 before 2 to get "4273".
    • Return modified string "4273" as the answer.

The resulting number is "4273", which is the largest number that can be formed by inserting 4 into "273".

Now, let's consider a negative example with n as "-456" and x as 3.

  1. Check the Sign of n:

    • "-456" starts with a minus sign; therefore, the number is negative.

  2. Negative Case (n is negative):

    • Skip the minus sign and start the iteration from the second character.
    • Compare each digit with x (3).
    • 4 is greater than 3, so we continue to the next digit.
    • 5 is also greater than 3, so we continue.
    • 6 is greater than 3, so we could keep going, but since there are no more digits, 3 will be inserted at the end.
    • Use string slicing while keeping in mind the negative sign's position.
    • The final string will be "-4536".

In the negative case, the largest number we can form by adding 3 to "-456" is "-4536". Here 3 is inserted at the end because each digit in "-456" after the minus sign is larger than 3, making "-4536" the best possible outcome.

Solution Implementation

1class Solution:
2    def maxValue(self, n: str, x: int) -> str:
3        # Check if the number n is positive
4        if n[0] != '-':
5            # Loop through each character in the number
6            for i, char in enumerate(n):
7                # If the current digit is less than x, insert x before it
8                if int(char) < x:
9                    return n[:i] + str(x) + n[i:]
10            # If not inserted, add x to the end of the number
11            return n + str(x)
12        else:
13            # The number n is negative, skip the '-' sign and start from the next digit
14            for i, char in enumerate(n[1:]):
15                # If the current digit is greater than x, insert x before it
16                if int(char) > x:
17                    return n[:i + 1] + str(x) + n[i + 1:]
18            # If x has not been inserted yet, add it to the end of the number
19            return n + str(x)
20
1class Solution {
2    public String maxValue(String n, int x) {
3        // Initialize the index variable i to 0
4        int i = 0;
5
6        // If the first character is not a '-'
7        if (n.charAt(0) != '-') {
8            // Loop through the string until we find a digit less than x
9            for (; i < n.length() && n.charAt(i) - '0' >= x; ++i) {
10                // No body for this for loop as it's just used to find the breakpoint
11            }
12        } else {
13            // If the first character is '-', start with the second character
14            // Loop through the string until we find a digit greater than x
15            for (i = 1; i < n.length() && n.charAt(i) - '0' <= x; ++i) {
16                // No body for this for loop as it's just used to find the breakpoint
17            }
18        }
19      
20        // Concatenate the string parts and the integer x:
21        // 1. Substring from the start to i (the breakpoint)
22        // 2. The integer x, converted to a string
23        // 3. The remaining substring from i to the end of the string
24        return n.substring(0, i) + x + n.substring(i);
25    }
26}
27
1class Solution {
2public:
3    // Function to insert the digit 'x' into the string 'n' to achieve the highest possible value.
4    string maxValue(string n, int x) {
5        int position = 0; // Initialize the insertion position
6
7        // If the number is positive
8        if (n[0] != '-') {
9            // Iterate over the string until we find a digit less than 'x'
10            for (; position < n.size() && (n[position] - '0') >= x; ++position)
11                ; // The loop body is empty since all work is done in the condition
12        } else { // If the number is negative
13            // Start from position 1 to skip the minus sign
14            for (position = 1; position < n.size() && (n[position] - '0') <= x; ++position)
15                ; // Again, the loop body is empty
16        }
17
18        // Insert 'x' into the found position and construct the new string
19        return n.substr(0, position) + to_string(x) + n.substr(position);
20    }
21};
22
1/**
2 * Function to insert the maximum value.
3 * Inserts an integer digit `x` into the string representation of a non-negative integer `n`,
4 * at such a position that the new integer is as large as possible.
5 *
6 * @param {string} n - The string representation of the number into which `x` has to be inserted.
7 * @param {number} x - The integer digit to insert into `n`.
8 * @return {string} - The resulting string after insertion of `x`.
9 */
10function maxValue(n: string, x: number): string {
11    // Convert the string `n` into an array of characters
12    let numberArray: string[] = [...n];
13  
14    // Determine the sign of the number (positive by default)
15    let sign: number = 1;
16  
17    // Starting index for the iteration, adjusted if the number is negative
18    let index: number = 0;
19  
20    // If the first character is a minus sign, update the `sign` and `index`
21    if (numberArray[0] === '-') {
22        sign = -1;
23        index++;
24    }
25  
26    // Find the position to insert `x` by iterating over the characters of `n`
27    // For a positive number, it stops before the first digit smaller than `x`
28    // For a negative number, it stops before the first digit larger than `x`
29    while (index < n.length && (parseInt(numberArray[index]) - x) * sign >= 0) {
30        index++;
31    }
32  
33    // Insert `x` into the correct position in the array of characters
34    numberArray.splice(index, 0, x.toString());
35  
36    // Join the array back into a string and return the result
37    return numberArray.join('');
38}
39
40// The maxValue function can now be called with TypeScript syntax
41// Example usage: let result: string = maxValue('123', 5);
42
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used to implement recursion?

Time and Space Complexity

The time complexity of the given code is O(n) where n is the length of the input string. The for-loop iterates over the string characters at most once. In each iteration, it performs constant time operations (comparisons and integer conversions). Therefore, the total time taken is linear with respect to the length of the input string.

The space complexity of the code is O(1) (disregarding the input and the output). The reason is that the code only uses a fixed number of variables (i, c, x), and creating the final string output doesn't count towards additional space since the output is required and does not contribute to the space used by the algorithm itself.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫