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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Earliest Second to Mark Indices I

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each index in nums can only be marked when its value is decremented to zero.
  • The order of operations matters as we have a fixed number of seconds (m) to mark all indices.
  • We need to track which indices can be marked at each second based on the decremented values.
  • If any index in nums is not referenced in changeIndices, marking all indices is impossible.

Space and Time Complexity

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

Solution

The solution involves iterating over the changeIndices array to keep track of how many times we can mark each index and how many decrements are needed for each index in nums. We can use a degreed array to count how many times we need to decrement each index. We will use a queue to efficiently manage the marking operations as we simulate each second.

Code Solutions

def earliestMarking(nums, changeIndices):
    n = len(nums)
    m = len(changeIndices)
    
    # Array to track how many times we need to decrement each index
    decrement_needed = [0] * (n + 1)
    
    # Count how many times each index is referenced in changeIndices
    for idx in changeIndices:
        decrement_needed[idx] += 1
    
    marked = [False] * (n + 1)
    seconds = 0
    
    for second in range(1, m + 1):
        index = changeIndices[second - 1]
        
        # Perform a decrement operation if there's still decrement needed
        if nums[index - 1] > 0:
            nums[index - 1] -= 1
        
        # Check if we can mark the current index
        if nums[index - 1] == 0 and not marked[index]:
            marked[index] = True
            decrement_needed[index] -= 1
            
            # If all marked, return current second
            if all(marked[1:]):
                return second
        
        # If decrement is still needed, we can keep track of it
        if decrement_needed[index] > 0:
            decrement_needed[index] -= 1
            
    return -1 if not all(marked[1:]) else m
← Back to All Questions