Find Score of an Array After Marking All Elements

Asked by:

10 views

Topics:

ArraysGreedy Algorithms

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.

Example 1:

 Input: nums = [2,1,3,4,5,2] Output: 7 Explanation: We mark the elements as follows: - 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,1,3,4,5,2]. - 2 is the smallest unmarked element, so we mark it and its left adjacent element: [2,1,3,4,5,2]. - 4 is the only remaining unmarked element, so we mark it: [2,1,3,4,5,2]. Our score is 1 + 2 + 4 = 7.

Example 2:

 Input: nums = [2,3,5,1,3,2] Output: 5 Explanation: We mark the elements as follows: - 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,3,5,1,3,2]. - 2 is the smallest unmarked element, since there are two of them, we choose the left-most one, so we mark the one at index 0 and its right adjacent element: [2,3,5,1,3,2]. - 2 is the only remaining unmarked element, so we mark it: [2,3,5,1,3,2]. Our score is 1 + 2 + 2 = 5.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Given the constraints on array size and element values, the final score could become quite large. Should I use a 64-bit integer type for the score to prevent potential overflow?
To confirm the selection logic: the tie-breaking rule of using the smallest index is only applied after we've identified multiple unmarked elements that all share the same minimum value, correct?
If an element gets marked because it is adjacent to a chosen element, is it correct to assume that this element can no longer be chosen on its own and its value will never be added to the score?
The algorithm terminates when all elements are marked. Does this mean the process should stop as soon as every index in the array has been marked, regardless of how it was marked?
The problem states the input is an array of positive integers. Can I safely assume the input will never be an empty array and will not contain zeros or negative values?

Brute Force Solution

Approach

The straightforward approach is to simulate the marking process round by round exactly as the rules describe. We repeatedly scan the entire collection of numbers to find the next one to mark, update our score, and continue until no numbers are left.

Here's how the algorithm would work step-by-step:

Start with a total score of zero and consider all numbers in the collection as available.
To begin a round, look through every number from the beginning to find the smallest one that is still available.
If you find multiple instances of the same smallest number, make sure to choose the one that appeared earliest in the original collection.
Once you've identified this specific number, add its value to your running total score.
Now, mark that number as 'used' so it cannot be picked again.
Also, find the numbers that were immediately to its left and right in the original lineup and mark them as 'used' as well.
Repeat this entire process: scan all numbers for the next smallest available one, add it to the score, and mark it and its neighbors.
Keep going until every single number in the collection has been marked as 'used'. The final score is your answer.

Code Implementation

def find_score_brute_force(numbers):
    number_of_elements = len(numbers)
    is_marked = [False] * number_of_elements
    total_score = 0
    elements_marked_count = 0

    # The simulation must run until every element is marked and thus unavailable for future turns.

    while elements_marked_count < number_of_elements:
        current_minimum_value = float('inf')
        index_of_minimum = -1

        # This scan finds the smallest available value, favoring the one with the smallest index in case of a tie.

        for current_index in range(number_of_elements):
            if not is_marked[current_index] and numbers[current_index] < current_minimum_value:
                current_minimum_value = numbers[current_index]
                index_of_minimum = current_index

        # Once the best candidate for this turn is found, its value contributes to the total score.

        total_score += numbers[index_of_minimum]

        # The chosen element and its direct neighbors must be marked as unavailable for subsequent turns.

        if not is_marked[index_of_minimum]:
            is_marked[index_of_minimum] = True
            elements_marked_count += 1

        if index_of_minimum > 0 and not is_marked[index_of_minimum - 1]:
            is_marked[index_of_minimum - 1] = True
            elements_marked_count += 1

        if index_of_minimum < number_of_elements - 1 and not is_marked[index_of_minimum + 1]:
            is_marked[index_of_minimum + 1] = True
            elements_marked_count += 1
            
    return total_score

Big(O) Analysis

Time Complexity

O(n²) – Let n be the number of elements in the input array. The overall process consists of multiple rounds to mark all elements, and the number of rounds is proportional to n. For each round, the algorithm must perform a linear scan through all n positions in the collection to identify the smallest available number at the lowest index. This search operation takes O(n) time. Because this O(n) scan is nested within a process that repeats approximately n times, the total number of operations is on the order of n * n, which simplifies to O(n²).

Space Complexity

O(N) – The simulation requires tracking which numbers are 'still available' versus 'used'. This is achieved by using an auxiliary boolean array of size N, where N is the number of elements in the input collection, to store the marked status of each number. In each round, this array is checked to find the next available element and updated after marking a number and its neighbors. Aside from this array and a single variable for the score, no other significant data structures are needed, making the space usage proportional to the input size.

Optimal Solution

Approach

The most efficient way to solve this is to avoid searching for the smallest available number over and over again. Instead, we can decide the best order to pick numbers in advance by sorting them. Then, we can simply go through this pre-sorted list and pick the numbers whose turn it is, skipping any that have already been marked by a previous move.

Here's how the algorithm would work step-by-step:

First, make a note of every number along with its original position in the line.
Now, sort these numbers based on their value, from smallest to largest. If two numbers have the same value, the one that appeared earlier in the original line goes first.
You'll also need a way to track which positions in the original line have been marked. Think of it as a checklist, where initially, nothing is checked off.
Begin by looking at the first number in your new, sorted list.
Check your list to see if this number's original position has already been marked.
If its original position is not yet marked, this is the number you'll process. Add its value to your running score.
After adding to the score, mark off its original position on your checklist. Also, mark off the positions immediately to its left and right.
If you find that a number's original position was already marked, you do nothing. Just ignore it and move to the next number in your sorted list.
Continue this process for every number in your sorted list. The total score you've accumulated at the end is the final answer.

Code Implementation

class Solution:
    def findScore(self, nums: list[int]) -> int:
        number_of_elements = len(nums)

        # Create pairs of (value, index) to sort by value, then by original position for tie-breaking.
        value_index_pairs_list = []
        for index in range(number_of_elements):
            value_index_pairs_list.append((nums[index], index))
        
        value_index_pairs_list.sort()

        # Use a boolean array to efficiently track which elements have been marked and should be skipped.
        is_element_marked = [False] * number_of_elements
        
        total_score = 0
        for current_value, original_index in value_index_pairs_list:

            # For each number in our prioritized list, we first check if its original spot is still available.
            if is_element_marked[original_index]:
                continue
            
            total_score += current_value
            
            # After scoring an element, we must mark it and its neighbors to prevent them from being picked.
            is_element_marked[original_index] = True
            if original_index > 0:
                is_element_marked[original_index - 1] = True
            if original_index < number_of_elements - 1:
                is_element_marked[original_index + 1] = True
                
        return total_score

Big(O) Analysis

Time Complexity

O(n log n) – Let n be the number of elements in the input array. The algorithm's runtime is dominated by the initial sorting step. Creating pairs of numbers and their original indices takes O(n) time. Sorting these n pairs based on their values and original indices requires O(n log n) time. After sorting, iterating through the n pairs to check if an element is marked and update the score is a single pass, which takes O(n) time. Since the sorting cost is the most significant, the overall time complexity simplifies to O(n log n).

Space Complexity

O(N) – The primary space usage comes from step 1, where we create a new data structure to store N pairs, each containing a number and its original index. Step 3 requires an additional 'checklist' to track the marked status of all N original positions, which is typically implemented as a boolean array of size N. Since both of these auxiliary data structures scale linearly with the number of elements in the input array, the overall space complexity is O(N).

Edge Cases

Case	How to Handle
Array with a single element.	The algorithm correctly adds the single element's value to the score and terminates as it's the only element to mark.
Maximum-sized input (up to 10^5 elements).	An efficient O(N log N) approach using sorting or a min-heap is required to prevent a Time Limit Exceeded error.
Score accumulation leads to integer overflow.	The variable accumulating the score must be a 64-bit integer type as the total can exceed the capacity of a 32-bit integer.
Array contains all identical values.	The tie-breaking rule is correctly managed by processing elements based on their original index as a secondary criterion after their value.
Choosing an element at an array boundary (index 0 or N-1).	The logic must perform bounds checking to ensure it only attempts to mark valid adjacent indices within the array.
An element's neighbor is already marked from a previous step.	The marking process must be idempotent, meaning re-marking an already marked element does not alter the state or outcome.
Input array is already sorted in ascending order.	The solution must correctly skip over elements that get marked by their smaller, preceding neighbors in the sorted list.
Smallest values are located at the end of the array.	Pre-sorting the numbers with their indices ensures the algorithm correctly identifies the true minimum regardless of its position.

Array with a single element.

How to Handle:

The algorithm correctly adds the single element's value to the score and terminates as it's the only element to mark.

Maximum-sized input (up to 10^5 elements).

How to Handle:

An efficient O(N log N) approach using sorting or a min-heap is required to prevent a Time Limit Exceeded error.

Score accumulation leads to integer overflow.

How to Handle:

The variable accumulating the score must be a 64-bit integer type as the total can exceed the capacity of a 32-bit integer.

Array contains all identical values.

How to Handle:

The tie-breaking rule is correctly managed by processing elements based on their original index as a secondary criterion after their value.

Choosing an element at an array boundary (index 0 or N-1).

How to Handle:

The logic must perform bounds checking to ensure it only attempts to mark valid adjacent indices within the array.

An element's neighbor is already marked from a previous step.

How to Handle:

The marking process must be idempotent, meaning re-marking an already marked element does not alter the state or outcome.

Input array is already sorted in ascending order.

How to Handle:

The solution must correctly skip over elements that get marked by their smaller, preceding neighbors in the sorted list.

Smallest values are located at the end of the array.

How to Handle:

Pre-sorting the numbers with their indices ensures the algorithm correctly identifies the true minimum regardless of its position.