2593. Find Score of an Array After Marking All Elements - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You are given an integer array nums. Initially, the score is 0. You perform the following operations until all elements are marked (i.e., considered processed):

Find the smallest unmarked element in nums and add its value to the score.
Mark this element and its adjacent elements (if they exist).
Repeat until all elements are marked.

Return the final score.

Example Inputs and Outputs:

Input: nums = [2,1,3,4,5,2]
Output: 7
Explanation: The optimal order of operations is:
- Pick 1, mark 1 and its neighbors → nums = [X, X, X, 4, 5, 2], score = 1
- Pick 2 (next smallest unmarked), mark 2 and its neighbor → nums = [X, X, X, 4, X, X], score = 3
- Pick 4 (last remaining unmarked element), mark 4 → nums = [X, X, X, X, X, X], score = 7
Input: nums = [4,2,3,6,5]
Output: 7
Explanation:
- Pick 2, mark 2 and its neighbors → nums = [X, X, X, 6, 5], score = 2
- Pick 5, mark 5 and its neighbor → nums = [X, X, X, X, X], score = 7
(In this sequence, picking 2 first causes 4 and 3 to be marked (skipped in scoring), and picking 5 next causes 6 to be marked. Only 2 and 5 contribute to the score, totaling 7.)

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6

Hints to Solve the Problem

Sorting Can Help: Sorting nums (while keeping track of original indices) allows you to process elements in ascending order of value.
Tracking Marked Elements: Use an auxiliary structure (like a boolean array or a set) to keep track of which indices have been marked. This way, you know when to skip an element because it or its neighbors were already marked by a previous operation.
Efficient Selection: By sorting initially, you avoid repeatedly searching for the next smallest unmarked element. This gives a more efficient selection process than scanning the array for the minimum on each iteration.

Approaches to Solve the Problem

Approach 1: Sorting with a Boolean Marking Array

Idea:
Sort the array along with their original indices. Iterate through the sorted list of values, and for each value (from smallest to largest), if it hasn't been marked yet, add it to the score and mark it and its adjacent elements as processed. Using the sorted order guarantees that whenever you encounter an unmarked element, it is the smallest remaining unmarked element.

We create a list of tuples (num, index) for each element in nums and sort it by num (the value).
Maintain a boolean array marked of the same length as nums to indicate whether each index has been marked.
Iterate over the sorted value-index pairs:
- If the current index is not yet marked, add the value to the score.
- Mark the current index and its neighbors (index - 1 and index + 1 if they exist) as True in the marked array.
Continue this until all elements are marked or you finish iterating through the sorted list.

This approach works because marking an element (and its neighbors) will effectively skip those positions in any future considerations. By processing in sorted order, you ensure that each time you add a value to the score, it is the smallest possible remaining value.

Complexity Analysis:

Time Complexity: O(n log n) due to the sorting step. The subsequent single pass through the sorted elements is O(n), making sorting the dominant factor.
Space Complexity: O(n) for the additional data structures (the sorted list of pairs and the marking array).

Python Code:

Python3

. . . .

Java Code:

Java

. . . .

Why this works: By sorting, we ensure that whenever we decide to add an element's value to the score, it is the smallest among the remaining unmarked elements. Marking its neighbors prevents those larger (or equal) adjacent values from being added later, effectively "skipping" them in favor of the smaller one we've just added. This greedy strategy yields the correct final score.

Step-by-Step Walkthrough

Let's walk through the approach using the first example nums = [2,1,3,4,5,2]:

Sort with Indices: Transform nums into pairs with indices: [(2,0), (1,1), (3,2), (4,3), (5,4), (2,5)]. Sorting by value gives: [(1,1), (2,0), (2,5), (3,2), (4,3), (5,4)]. This sorted list tells us the order in which we'll consider values.
Initialize Markers: Create a marked array of the same length (all initialized to False) to keep track of marked indices. Start with score = 0.
Iterate and Mark: Go through the sorted list:
- Look at (1,1). Since index 1 is not yet marked, add 1 to score (now score = 1). Mark index 1 and its neighbors (index 0 and 2) as True in marked.
- Next is (2,0). Index 0 is already marked (from the previous step), so skip it (we don't add this 2 to the score because it was adjacent to the 1 we picked).
- Next (2,5). Index 5 is not marked, so add 2 to score (now score = 3). Mark index 5 and its neighbors (index 4 is the left neighbor; index 6 doesn't exist) as marked.
- Next (3,2). Index 2 is already marked, skip it.
- Next (4,3). Index 3 is not marked, add 4 to score (now score = 7). Mark index 3 and its neighbors (index 2 and 4, which are already marked by previous steps).
- Next (5,4). Index 4 is already marked, skip it.
All Marked: At this point, all indices have been marked. The final score is 7, which matches the expected result.

Each time we picked the smallest available number and marked its position and neighbors, effectively removing a chunk of the array from further consideration. This process continues until no elements remain unmarked.

Common Mistakes and Edge Cases

Not marking neighbors correctly: Forgetting to mark the adjacent elements will cause those values to be added again later, leading to an incorrect (usually higher) score. Always mark both the left and right neighbor of the chosen element, if they exist.
Handling duplicate values: When sorting, duplicates will be adjacent in the sorted order. Ensure that you still check if an index is already marked before adding its value. Duplicates in value but at adjacent indices could cause one to mark the other.
Edge Case – single element: If the array has only one element, the algorithm should simply return that element's value as the score. (The single element is the smallest unmarked by default, add it, mark it, done.)

Alternative Variations

Consider how the problem or solution might change with some variations:

What if adjacent elements are not marked? If we did not mark adjacent elements upon picking one, then the score would simply be the sum of all elements (since we'd eventually pick every element). The marking of neighbors is what causes some elements to be skipped in the score.
What if elements are removed instead of just marked? Removing the picked element and its neighbors from the array each time would yield the same score outcome as marking (since marked elements are essentially skipped). This variation turns the problem into one of removing intervals from an array, and the score is the sum of the chosen elements.
What if you could only mark after skipping k elements? That would complicate the strategy, potentially turning it into a different kind of interval scheduling or dynamic programming problem, where you can take one element and then must skip the next k elements (a generalization of the house robber scenario).

Delete and Earn (LeetCode 740): A similar concept where if you take (earn) points from a number, you effectively remove its adjacent values (like removing all instances of that number's neighbors). It can be solved using a strategy derived from the House Robber problem.
House Robber (LeetCode 198): A classic dynamic programming problem where you cannot take two adjacent numbers. It’s related in the sense that choosing a number prevents immediate neighbors from being chosen.
Interval Scheduling Maximization (Greedy): Although not an array problem, it deals with selecting intervals such that none overlap, analogous to marking off neighbors when an interval (or element) is chosen. The greedy strategy of always picking the next interval that finishes first is similar in spirit to always picking the smallest available element here.