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

Find Score of an Array After Marking All Elements

Difficulty: Medium

Problem Description

You are given an array nums consisting of positive integers. Starting with score = 0, apply the following algorithm:

  • Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
  • Add the value of the chosen integer to score.
  • Mark the chosen element and its two adjacent elements if they exist.
  • Repeat until all the array elements are marked. Return the score you get after applying the above algorithm.

Key Insights

  • The algorithm repeatedly selects the smallest unmarked element and marks it along with its neighbors.
  • Efficiently tracking the smallest unmarked element is crucial, which can be achieved using a priority queue (min-heap).
  • Marking elements can be achieved using an array to keep track of which elements have already been marked.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting and priority queue operations. Space Complexity: O(n) - for the marked array and the priority queue.

Solution

The solution involves using a min-heap to efficiently retrieve the smallest unmarked element. We also maintain a boolean array to track which elements are marked. The algorithm proceeds as follows:

  1. Insert all elements with their indices into a min-heap.
  2. Continuously extract the minimum element from the heap.
  3. If the element is unmarked, add its value to the score and mark it along with its neighbors.
  4. Repeat until all elements are marked.

Code Solutions

import heapq

def findScore(nums):
    n = len(nums)
    score = 0
    marked = [False] * n
    min_heap = [(num, i) for i, num in enumerate(nums)]
    
    # Create a min-heap
    heapq.heapify(min_heap)

    while min_heap:
        value, index = heapq.heappop(min_heap)
        
        # Check if the current element is already marked
        if marked[index]:
            continue
        
        # Add to score and mark the element and its neighbors
        score += value
        marked[index] = True
        if index - 1 >= 0:
            marked[index - 1] = True
        if index + 1 < n:
            marked[index + 1] = True
            
    return score
← Back to All Questions