Constructing Two Increasing Arrays - Practice Coding Problems

Constructing Two Increasing Arrays - Problem

Given 2 integer arrays nums1 and nums2 consisting only of 0 and 1, your task is to calculate the minimum possible largest number in arrays nums1 and nums2, after doing the following.

Replace every 0 with an even positive integer and every 1 with an odd positive integer. After replacement, both arrays should be increasing and each integer should be used at most once.

Return the minimum possible largest number after applying the changes.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [0,1], nums2 = [1]

› Output: 3

💡 Note: Replace nums1=[0,1] with [2,3] and nums2=[1] with [1]. Both arrays are increasing and max value is 3.

Example 2 — All Zeros

$ Input: nums1 = [0,0], nums2 = [0]

› Output: 6

💡 Note: Replace nums1=[0,0] with [2,4] and nums2=[0] with [6]. All even numbers, max is 6.

Example 3 — All Ones

$ Input: nums1 = [1], nums2 = [1,1]

› Output: 5

💡 Note: Replace nums1=[1] with [1] and nums2=[1,1] with [3,5]. All odd numbers, max is 5.

Constraints

1 ≤ nums1.length, nums2.length ≤ 1000
nums1[i], nums2[i] ∈ {0, 1}

Visualization

Tap to expand

Understanding the Visualization

Input

Two binary arrays: nums1=[0,1], nums2=[1]

Transform

Replace 0→even, 1→odd, maintain increasing order

Output

Minimum possible maximum value: 3

Key Takeaway

🎯 Key Insight: Count zeros and ones, then use formula: max(2×zeros, 2×ones-1) for optimal assignment

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to count zeros and ones across both arrays and assign the smallest available numbers. The optimal approach calculates the result mathematically: max(2×zeros, 2×ones-1). Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Backtracking	O(k^n)	O(n)	Try all possible valid assignments and find minimum maximum
Greedy Assignment	O(n)	O(n)	Assign smallest available numbers greedily to minimize maximum
Optimized Counting	O(n)	O(1)	Direct mathematical calculation of minimum maximum value

Brute Force with Backtracking — Algorithm Steps

Step 1: Generate all possible assignments of positive even/odd numbers
Step 2: For each assignment, verify both arrays are strictly increasing
Step 3: Track the minimum maximum value across all valid assignments

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup

Start with empty assignments for both arrays

Branch

Try all valid even/odd numbers for current position

Prune

Skip if number violates increasing order or already used

Code -

solution.c — C

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

int backtrack(int idx1, int idx2, int* used, int* assignment1, int* assignment2, int len1, int len2, int* nums1, int* nums2, int* count1, int* count2) {
    if (idx1 == len1 && idx2 == len(nums2)) {
        int maxVal = 0;
        for (int i = 0; i < *count1; i++) {
            if (assignment1[i] > maxVal) maxVal = assignment1[i];
        }
        for (int i = 0; i < *count2; i++) {
            if (assignment2[i] > maxVal) maxVal = assignment2[i];
        }
        return (*count1 + *count2) == 0 ? INT_MAX : maxVal;
    }
    
    int minMax = INT_MAX;
    
    if (idx1 < len1) {
        int target = nums1[idx1] == 0 ? 2 : 1;
        for (int num = target; num <= 100; num += 2) {
            if (!used[num] && (*count1 == 0 || num > assignment1[*count1 - 1])) {
                used[num] = 1;
                assignment1[(*count1)++] = num;
                int result = backtrack(idx1 + 1, idx2, used, assignment1, assignment2, len1, len2, nums1, nums2, count1, count2);
                if (result < minMax) minMax = result;
                (*count1)--;
                used[num] = 0;
                if (minMax < 50) break;
            }
        }
    }
    
    if (idx2 < len2) {
        int target = nums2[idx2] == 0 ? 2 : 1;
        for (int num = target; num <= 100; num += 2) {
            if (!used[num] && (*count2 == 0 || num > assignment2[*count2 - 1])) {
                used[num] = 1;
                assignment2[(*count2)++] = num;
                int result = backtrack(idx1, idx2 + 1, used, assignment1, assignment2, len1, len2, nums1, nums2, count1, count2);
                if (result < minMax) minMax = result;
                (*count2)--;
                used[num] = 0;
                if (minMax < 50) break;
            }
        }
    }
    
    return minMax;
}

int solution(int* nums1, int len1, int* nums2, int len2) {
    int used[101] = {0};
    int assignment1[50], assignment2[50];
    int count1 = 0, count2 = 0;
    return backtrack(0, 0, used, assignment1, assignment2, len1, len2, nums1, nums2, &count1, &count2);
}

int main() {
    char line1[1000], line2[1000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int nums1[50], nums2[50];
    int len1 = 0, len2 = 0;
    
    char* token = strtok(line1 + 1, ",]");
    while (token) {
        nums1[len1++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    token = strtok(line2 + 1, ",]");
    while (token) {
        nums2[len2++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums1, len1, nums2, len2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

Where k is the range of numbers to try and n is total length of both arrays

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth and temporary arrays for assignment tracking

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~15 min Avg. Time

245 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

Brute Force with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler