Earliest Second to Mark Indices I - Practice Coding Problems

Earliest Second to Mark Indices I - Problem

You are given two 1-indexed integer arrays, nums and changeIndices, having lengths n and m, respectively.

Initially, all indices in nums are unmarked. Your task is to mark all indices in nums.

In each second s, in order from 1 to m (inclusive), you can perform one of the following operations:

Choose an index i in the range [1, n] and decrement nums[i] by 1.
If nums[changeIndices[s]] is equal to 0, mark the index changeIndices[s].
Do nothing.

Return an integer denoting the earliest second in the range [1, m] when all indices in nums can be marked by choosing operations optimally, or -1 if it is impossible.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,2]

› Output: 8

💡 Note: We need to decrement nums[0] twice, nums[1] twice, and mark all indices. Index 3 appears first at position 5, so we need at least 8 seconds to complete all operations.

Example 2 — Impossible Case

$ Input: nums = [1,0,1,0], changeIndices = [1,2]

› Output: -1

💡 Note: changeIndices only covers indices 1 and 2, but we need to mark indices 1,2,3,4. Since indices 3 and 4 never appear, it's impossible.

Example 3 — All Zeros

$ Input: nums = [0,1,0], changeIndices = [1,2,3]

› Output: 3

💡 Note: nums[1] needs 1 decrement. All indices appear exactly once, so we need 3 seconds: decrement nums[1], mark index 2, mark index 3, then we can mark index 1.

Constraints

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 10⁹
1 ≤ changeIndices.length ≤ 5000
1 ≤ changeIndices[i] ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

nums array and changeIndices schedule

Process

Decrement values and mark when they reach 0

Output

Minimum time to mark all indices

Key Takeaway

🎯 Key Insight: Binary search on time, then check if we have enough operations to decrement and mark all indices

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to use binary search on the answer space. We binary search on the minimum time needed, and for each candidate time, check if it's feasible using a greedy approach. Best approach is Binary Search on Answer with Time: O(n log m), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try Every Second	O(m²n)	O(n)	Try each second from 1 to m and simulate the marking process
Binary Search on Answer	O(n log m + m log m)	O(n)	Binary search on the answer with greedy feasibility check

Brute Force - Try Every Second — Algorithm Steps

For each second t from 1 to m
Simulate the marking process up to second t
Check if all indices can be marked
Return the first valid second

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Second 1

Can we mark all indices by second 1?

Try Second 2

Can we mark all indices by second 2?

Continue

Keep trying until we find the minimum

Code -

solution.c — C

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

bool canMark(int* nums, int numsSize, int* changeIndices, int changeSize, int seconds) {
    int* numsCopy = (int*)malloc(numsSize * sizeof(int));
    bool* marked = (bool*)calloc(numsSize, sizeof(bool));
    int* lastOccur = (int*)malloc(numsSize * sizeof(int));
    bool* hasOccur = (bool*)calloc(numsSize, sizeof(bool));
    
    memcpy(numsCopy, nums, numsSize * sizeof(int));
    
    for (int i = 0; i < seconds; i++) {
        int idx = changeIndices[i] - 1;
        lastOccur[idx] = i;
        hasOccur[idx] = true;
    }
    
    for (int i = 0; i < numsSize; i++) {
        if (!hasOccur[i]) {
            free(numsCopy); free(marked); free(lastOccur); free(hasOccur);
            return false;
        }
    }
    
    for (int second = 0; second < seconds; second++) {
        int idx = changeIndices[second] - 1;
        
        if (lastOccur[idx] == second) {
            if (numsCopy[idx] == 0) {
                marked[idx] = true;
            } else {
                free(numsCopy); free(marked); free(lastOccur); free(hasOccur);
                return false;
            }
        } else {
            if (numsCopy[idx] > 0) {
                numsCopy[idx]--;
            }
        }
    }
    
    for (int i = 0; i < numsSize; i++) {
        if (!marked[i]) {
            free(numsCopy); free(marked); free(lastOccur); free(hasOccur);
            return false;
        }
    }
    
    free(numsCopy); free(marked); free(lastOccur); free(hasOccur);
    return true;
}

int solution(int* nums, int numsSize, int* changeIndices, int changeSize) {
    for (int t = 1; t <= changeSize; t++) {
        if (canMark(nums, numsSize, changeIndices, changeSize, t)) {
            return t;
        }
    }
    return -1;
}

int main() {
    // Simple parsing for demo - would need proper JSON parsing in practice
    printf("-1\n"); // Placeholder
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n)

For each of m seconds, we simulate m operations on n elements

✓ Linear Growth

Space Complexity

O(n)

Copy of nums array for simulation

⚡ Linearithmic Space

12.4K Views

Medium Frequency

~35 min Avg. Time

445 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 - Try Every Second — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler