Make Array Strictly Increasing - Practice Coding Problems

Make Array Strictly Increasing - Problem

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

Input & Output

Example 1 — Basic Replacement

$ Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]

› Output: 1

💡 Note: Replace arr1[2] = 3 with arr2[2] = 2. Result: [1,5,2,6,7] is not strictly increasing. Actually replace arr1[1] = 5 with arr2[2] = 2. Result: [1,2,3,6,7] which is strictly increasing with 1 operation.

Example 2 — Multiple Replacements

$ Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]

› Output: 2

💡 Note: Need to replace arr1[1] = 5 and arr1[2] = 3 to make array strictly increasing. Minimum 2 operations required.

Example 3 — Impossible Case

$ Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]

› Output: -1

💡 Note: No way to make the array strictly increasing with available replacement values.

Constraints

1 ≤ arr1.length, arr2.length ≤ 2000
0 ≤ arr1[i], arr2[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays: arr1 to modify, arr2 for replacement values

Process

For each position, choose to keep or replace with optimal value

Output

Minimum operations needed or -1 if impossible

Key Takeaway

🎯 Key Insight: Use dynamic programming to explore all valid choices while binary search optimizes finding the best replacement value

Asked in

G Google 45 a Amazon 32 M Microsoft 28 f Facebook 25

The key insight is that at each position we have two choices: keep the original value or replace it with the smallest valid value from arr2. The optimal approach uses dynamic programming with binary search to efficiently find replacement values. Best approach: DP + Binary Search with Time: O(n * m * log m), Space: O(n * m).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(n * m * max_val)	O(n * max_val)	Optimize brute force by caching results for repeated subproblems
Brute Force with Recursion	O(2^(n*m))	O(n)	Try all possible combinations of keeping or replacing each element
DP with Binary Search Optimization	O(n * m * log m)	O(n * m)	Use sorted arr2 and binary search to find optimal replacement values efficiently

Dynamic Programming with Memoization — Algorithm Steps

Step 1: Create a memoization cache indexed by (position, previous_value)
Step 2: Before solving a subproblem, check if result is already cached
Step 3: If not cached, solve recursively and store the result
Step 4: Return cached result for future identical subproblems

Visualization

Tap to expand

Step-by-Step Walkthrough

Cache

Store results of (position, previous_value) states

Lookup

Check cache before recursive calls

Prune

Avoid redundant calculations

Code -

solution.c — C

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

#define HASH_SIZE 100000

typedef struct HashNode {
    char key[50];
    int value;
    struct HashNode* next;
} HashNode;

HashNode* hashTable[HASH_SIZE];

unsigned int hash(const char* str) {
    unsigned int hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c;
    }
    return hash % HASH_SIZE;
}

int getMemo(int pos, int prevVal) {
    char key[50];
    sprintf(key, "%d,%d", pos, prevVal);
    unsigned int index = hash(key);
    HashNode* node = hashTable[index];
    while (node) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return INT_MAX;
}

void setMemo(int pos, int prevVal, int value) {
    char key[50];
    sprintf(key, "%d,%d", pos, prevVal);
    unsigned int index = hash(key);
    HashNode* node = malloc(sizeof(HashNode));
    strcpy(node->key, key);
    node->value = value;
    node->next = hashTable[index];
    hashTable[index] = node;
}

int solve(int* arr1, int len1, int* arr2, int len2, int pos, int prevVal) {
    if (pos == len1) {
        return 0;
    }
    
    int cached = getMemo(pos, prevVal);
    if (cached != INT_MAX) {
        return cached;
    }
    
    int minOps = INT_MAX;
    
    // Try keeping original value
    if (arr1[pos] > prevVal) {
        int result = solve(arr1, len1, arr2, len2, pos + 1, arr1[pos]);
        if (result != INT_MAX) {
            minOps = minOps < result ? minOps : result;
        }
    }
    
    // Try replacing with each value from arr2
    for (int i = 0; i < len2; i++) {
        if (arr2[i] > prevVal) {
            int result = solve(arr1, len1, arr2, len2, pos + 1, arr2[i]);
            if (result != INT_MAX) {
                int ops = 1 + result;
                minOps = minOps < ops ? minOps : ops;
            }
        }
    }
    
    setMemo(pos, prevVal, minOps);
    return minOps;
}

int solution(int* arr1, int len1, int* arr2, int len2) {
    memset(hashTable, 0, sizeof(hashTable));
    int result = solve(arr1, len1, arr2, len2, 0, INT_MIN);
    return result == INT_MAX ? -1 : result;
}

int* parseArray(char* str, int* len) {
    *len = 0;
    int* arr = malloc(1000 * sizeof(int));
    char* token = strtok(str, "[],");
    while (token != NULL) {
        arr[(*len)++] = atoi(token);
        token = strtok(NULL, "[],");
    }
    return arr;
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    line1[strcspn(line1, "\n")] = 0;
    line2[strcspn(line2, "\n")] = 0;
    
    int len1, len2;
    int* arr1 = parseArray(line1, &len1);
    int* arr2 = parseArray(line2, &len2);
    
    printf("%d\n", solution(arr1, len1, arr2, len2));
    
    free(arr1);
    free(arr2);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n * m * max_val)

Each unique (position, previous_value) state is computed once, with n positions and up to m*max_val possible previous values

✓ Linear Growth

Space Complexity

O(n * max_val)

Memoization cache stores results for all unique states plus recursion stack

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 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

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler