Maximum Value after Insertion - Practice Coding Problems

Maximum Value after Insertion - Problem

String Greedy Medium

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.

Examples:

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.

Input & Output

Example 1 — Positive Number

$ Input: n = "73", x = 6

› Output: "763"

💡 Note: Insert 6 before digit 3 (first digit < 6): 7 → 76 → 763. This gives maximum value 763.

Example 2 — Negative Number

$ Input: n = "-55", x = 2

› Output: "-255"

💡 Note: For negative numbers, insert before first digit > x: -5 → -25 → -255. This gives maximum value -255.

Example 3 — Append at End

$ Input: n = "999", x = 5

› Output: "9995"

💡 Note: All digits (9) are ≥ 5, so append 5 at the end: 999 → 9995.

Constraints

1 ≤ n.length ≤ 10⁵
n consists of only digits, does not have leading zeros, and may have a leading negative sign
1 ≤ x ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input

String n and digit x to insert

Strategy

Find optimal position based on positive/negative

Output

Maximum possible value as string

Key Takeaway

🎯 Key Insight: The optimal position depends on the sign - maximize positive numbers by placing larger digits first, minimize absolute value of negative numbers

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to use different strategies for positive vs negative numbers. For positive numbers, insert x before the first digit smaller than x to maximize value. For negative numbers, insert x before the first digit larger than x to minimize the absolute value (thus maximizing the negative number). Best approach is greedy single pass with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Try All Positions	O(n²)	O(n)	Insert digit x at every possible position and find the maximum result
Greedy Single Pass	O(n)	O(1)	Find the optimal insertion position in one pass using greedy strategy

Try All Positions — Algorithm Steps

Generate all possible insertions of x into n
Convert each to integer and find maximum
Return the string with maximum value

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Position 0

Insert x at beginning (if not negative)

Try Position 1

Insert x at position 1

Find Maximum

Compare all candidates

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* n, int x) {
    int len = strlen(n);
    char* best = malloc(len + 2);
    strcpy(best, n);
    
    char xStr[2];
    sprintf(xStr, "%d", x);
    
    // Try inserting x at each position
    for (int i = 0; i <= len; i++) {
        // Skip position 0 if n starts with '-'
        if (i == 0 && n[0] == '-') {
            continue;
        }
        
        char* candidate = malloc(len + 2);
        strncpy(candidate, n, i);
        candidate[i] = '\0';
        strcat(candidate, xStr);
        strcat(candidate, n + i);
        
        // Compare as long long to find maximum
        if (atoll(candidate) > atoll(best)) {
            strcpy(best, candidate);
        }
        
        free(candidate);
    }
    
    return best;
}

int main() {
    char n[100];
    int x;
    
    fgets(n, sizeof(n), stdin);
    n[strcspn(n, "\n")] = 0; // Remove newline
    scanf("%d", &x);
    
    char* result = solution(n, x);
    printf("%s\n", result);
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

O(n) positions to try × O(n) string operations for each insertion

⚠ Quadratic Growth

Space Complexity

O(n)

Store multiple string copies during insertion attempts

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Try All Positions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler