We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Earliest Second to Mark Indices II

Number: 3289

Difficulty: Hard

Paid? No

Companies: MathWorks

Problem Description

You are given two 1-indexed integer arrays: nums (of length n) and changeIndices (of length m). Initially, none of the indices in nums is “marked.” In each second s (from 1 to m, in order) you may do exactly one of the following: • Choose any index i in [1,n] and decrement nums[i] by 1. • Set nums[changeIndices[s]] to any non-negative value. • Choose an index i in [1,n] (only allowed when nums[i] is 0) and mark index i. • Do nothing. Your objective is to mark all indices (each mark operation can only be done when the corresponding nums[i] is 0). Return the earliest second in [1, m] at which it is possible – by choosing operations optimally – to eventually mark every index in nums, or -1 if it is impossible.

Key Insights

  • The problem is about scheduling operations in a fixed order (seconds 1…m) so that every index is “zeroed” (via decrements or a “set-to-0” operation) before being marked.
  • Every marked index requires two parts: first reducing nums[i] to 0 (either by applying enough decrements or using a “set” operation) and then performing a mark op.
  • For each index with a positive value, you can either spend nums[i] decrement ops or, if available, one “set” op (which resets the number to 0 in one op) provided that there is a second s (<= T) where changeIndices[s]==i.
  • Precomputing the earliest occurrence (in the changeIndices array) for every index i simplifies checking eligibility for a “set” op.
  • We can use binary search over T (the candidate answer between n and m) to check if, within T seconds, we can schedule enough “zeroing” and marking operations.

Space and Time Complexity

Time Complexity: O(m + n·log(m))
Space Complexity: O(n)

Solution

We observe that every complete plan must include exactly n mark operations (one per index). This leaves T – n seconds to make each index eligible for marking by “zeroing” it. For each index i: • If nums[i] is already 0, no zeroing operations are needed. • If nums[i] > 0, there are two choices:

  • Use decrement operations for a total cost of nums[i] operations.
  • If there is any second s in the range [1, T] with changeIndices[s] == i then use a “set” op for cost 1. Thus, if index i is eligible (i.e. it appears at least once in changeIndices[1..T]) and nums[i] > 0, we can “zero” it in only 1 op; otherwise, we must use nums[i] decrement ops. For a given T (candidate seconds), we sum the “zeroing” cost over all indices and add n (for the mark operations). The plan is feasible if the total operations do not exceed T. With this feasibility check in hand, we perform a binary search for the smallest T in [n, m] that meets the requirement. Precomputing each index’s earliest occurrence in changeIndices speeds up the per-candidate check.

Code Solutions

Below are implementations in Python, JavaScript, C++ and Java. Each solution contains detailed, line‐by‐line comments.

# Python solution
def earliestSecond(nums, changeIndices):
    n = len(nums)
    m = len(changeIndices)
    # Create an array (1-indexed) for the earliest second each index appears in changeIndices.
    earliest_occurrence = [float('inf')] * (n + 1)
    for second, index in enumerate(changeIndices, 1):
        # Only update if this is the first time we see index.
        if second < earliest_occurrence[index]:
            earliest_occurrence[index] = second

    # Helper function to check feasibility for candidate T seconds.
    def can_finish(T):
        # We must reserve n seconds for marking operations.
        available_zero_ops = T - n
        cost = 0
        for i in range(1, n + 1):
            if nums[i - 1] == 0:
                # Already zeroized; no op needed.
                continue
            if earliest_occurrence[i] <= T:
                # Eligible for set op; cost is 1.
                cost += 1
            else:
                # No chance to use set op; need to use decrement operations.
                cost += nums[i - 1]
            # Early exit if cost exceeds available operations.
            if cost > available_zero_ops:
                return False
        # If total zeroing cost is within available operations, T is feasible.
        return cost <= available_zero_ops

    # Binary search for smallest T in range [n, m]
    left, right = n, m
    ans = -1
    while left <= right:
        mid = (left + right) // 2
        if can_finish(mid):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans

# Example usage:
print(earliestSecond([3, 2, 3], [1, 3, 2, 2, 2, 2, 3]))  # Expected output: 6
print(earliestSecond([0, 0, 1, 2], [1, 2, 1, 2, 1, 2, 1, 2]))  # Expected output: 7
print(earliestSecond([1, 2, 3], [1, 2, 3]))  # Expected output: -1
← Back to All Questions