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

Find Score of an Array After Marking All Elements

Number: 2695

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Bloomberg

Problem Description

Given an array of positive integers, simulate the following process starting with score = 0:

  1. Pick the smallest unmarked element. If there’s a tie, choose the one with the smallest index.
  2. Add its value to score.
  3. Mark the chosen element and its adjacent elements (if they exist).
  4. Repeat until all elements are marked. Return the final score.

Key Insights

  • Sorting indices by their element values (and by index in case of ties) allows us to simulate the process efficiently.
  • Maintaining a marked array helps quickly check whether an element (or its neighbors) has already been processed.
  • Once an element is marked (or one of its neighbors is marked), it will be skipped in further processing.
  • The overall complexity is dominated by sorting, making this approach efficient for large arrays.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the indices.
Space Complexity: O(n) for the auxiliary boolean array and storage of indices.

Solution

The strategy is to pre-sort the indices of the array based on the element values (and indices for ties). Then, iterate over these indices. For every unmarked index, add its value to the score and mark it as well as its adjacent neighbors (if available). This approach emulates the process of choosing the smallest unmarked element at each step without needing to repeatedly scan the array.

Code Solutions

# Python solution with detailed comments

def findScore(nums):
    # Number of elements in the array
    n = len(nums)
    # Array to keep track of marked elements
    marked = [False] * n
    # Initialize total score
    score = 0
    # Create a list of indices sorted first by value then by index
    sorted_indices = sorted(range(n), key=lambda i: (nums[i], i))
    
    # Iterate through each index in sorted order
    for i in sorted_indices:
        # If the current index is not marked
        if not marked[i]:
            # Add the value at this index to the score
            score += nums[i]
            # Mark the current index
            marked[i] = True
            # Mark the left adjacent element if it exists
            if i - 1 >= 0:
                marked[i - 1] = True
            # Mark the right adjacent element if it exists
            if i + 1 < n:
                marked[i + 1] = True
                
    return score

# Example usage:
print(findScore([2,1,3,4,5,2]))  # Expected output: 7
print(findScore([2,3,5,1,3,2]))  # Expected output: 5
← Back to All Questions