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 I

Number: 3292

Difficulty: Medium

Paid? No

Companies: MathWorks

Problem Description

Given two 1-indexed integer arrays – nums and changeIndices – you start with all indices in nums unmarked. In every second (from 1 to m, where m is the length of changeIndices) you may choose one of three operations: • Decrement any element in nums by 1. • If the element at the index specified by changeIndices for that second is 0, then mark that index. • Do nothing. Your goal is to mark every index of nums. Return the earliest second (in the range [1, m]) at which it is possible to mark every index when you choose your operations optimally, or -1 if it is impossible.

Key Insights

  • An index i can only be marked at those seconds s where changeIndices[s] equals i.
  • In order to mark index i, you must perform enough decrement operations so that nums[i] becomes 0 before using a marking operation.
  • Each marking operation “uses” one second (specifically a second at which changeIndices gives that index) and decrement operations must all be scheduled in earlier seconds.
  • The problem can be converted into a scheduling task: for each index i define a "task" with processing time equal to nums[i] (the required number of decrements) and a deadline equal to one of the seconds (an occurrence in changeIndices for index i) that is used to mark i. To maximize decrement time, you want to postpone the marking as much as possible.
  • Feasibility for a candidate total time X seconds (X from 1 to m) can be checked by, for each index, picking the latest occurrence (≤ X) of i in changeIndices as its deadline. Then sort these tasks by deadline and see if, when scheduled greedily, all required decrement operations can be completed before their deadlines (remember that the marking happens at the deadline so only seconds strictly before are available for decrements).

Space and Time Complexity

Time Complexity: O(n log n + m) per candidate X; using binary search over [1, m] gives overall O(m * (n log n)). Since m,n ≤ 2000, this is acceptable. Space Complexity: O(m + n), for storing occurrence lists and tasks.

Solution

We solve the problem using binary search on the candidate seconds X (from 1 to m). For each candidate X, we check if it is feasible to schedule all required decrement operations and marking operations within the first X seconds.

Step 1. Preprocess changeIndices: • For each index from 1 to n, store all seconds (positions) where it appears.

Step 2. Feasibility check for a given X: • For each index i, determine if there is at least one occurrence in changeIndices within [1, X]. If not, X is not feasible. • For each index i, choose the latest occurrence (≤ X) as its deadline. This is optimal because it gives maximum available time for performing decrements. • Think of index i as a “task” that requires nums[i] decrement operations (processing time) and that must finish these operations before the marking second (deadline). Note that because the marking operation happens at the deadline, the available time to perform the decrements is (deadline - 1). • Sort the tasks in increasing order of their deadline. • Iterate over the tasks and maintain a running total of decrement operations “scheduled”. For each task, if after adding nums[i] the total exceeds (deadline - 1), then the candidate X is not feasible.

Step 3. Use binary search to find the minimum X for which the feasibility condition holds. If no X works, return -1.

The following code implementations in various languages follow this approach.

Code Solutions

# Python solution with detailed comments
def earliestSecondToMark(nums, changeIndices):
    n = len(nums)
    m = len(changeIndices)
    # Build occurrence lists for each index (1-indexed) in nums.
    occurrences = [[] for _ in range(n+1)]
    for sec, idx in enumerate(changeIndices, start=1):
        occurrences[idx].append(sec)

    # Check feasibility for a candidate second X.
    def feasible(X):
        tasks = []
        # For each index i in 1..n, set a deadline = latest occurrence <= X
        for i in range(1, n+1):
            # If no operation time available for index i, then not feasible.
            if not occurrences[i] or occurrences[i][0] > X:
                return False
            # Binary search: find the last occurrence <= X.
            lo, hi = 0, len(occurrences[i]) - 1
            best = occurrences[i][0]
            while lo <= hi:
                mid = (lo + hi) // 2
                if occurrences[i][mid] <= X:
                    best = occurrences[i][mid]
                    lo = mid + 1
                else:
                    hi = mid - 1
            # Append tuple (deadline, required decrement count)
            tasks.append((best, nums[i-1]))
        # Sort tasks by their deadline, ascending.
        tasks.sort(key=lambda x: x[0])
        total_decrements = 0
        # For each task, ensure that cumulative decrements do not exceed available slots.
        for deadline, required in tasks:
            total_decrements += required
            # Each marking occupies the deadline second so available decrement slots 
            # before the marking is (deadline - 1)
            if total_decrements > deadline - 1:
                return False
        return True

    # Binary search the minimal X between n and m.
    low, high = 1, m
    ans = -1
    while low <= high:
        mid = (low + high) // 2
        if feasible(mid):
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
    return ans

# Example usage:
if __name__ == "__main__":
    # Example 1:
    nums1 = [2, 2, 0]
    changeIndices1 = [2, 2, 2, 2, 3, 2, 2, 1]
    print(earliestSecondToMark(nums1, changeIndices1))  # Expected output: 8
← Back to All Questions