# Find Score of an Array After Marking All Elements
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-score-of-an-array-after-marking-all-elements)
Canonical: https://scaleengineer.com/dsa/problems/find-score-of-an-array-after-marking-all-elements
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Heap (Priority Queue)
**Companies:** [Visa](https://scaleengineer.com/companies/visa)
---
## Problem
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 <= 105`
* `1 <= nums[i] <= 106`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. It repeatedly scans the entire array to find the smallest unmarked element, adds it to the score, and then marks it along with its neighbors.
**Time:** O(N^2). The outer `while` loop can run up to `N` times. In each iteration, we scan the entire array of `N` elements to find the minimum. This results in a quadratic time complexity. · **Space:** O(N). We use a boolean array `marked` of size `N` to store the state of each element.
**Pros:** Simple to understand and implement.; Directly follows the problem description.
**Cons:** Highly inefficient due to the repeated linear scan for the minimum element.; Will result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the constraints.
### Explanation
The brute-force method follows the problem statement literally. We maintain a boolean array `marked` to keep track of which elements have been marked. In each step of the algorithm, we need to find the smallest unmarked element. To do this, we perform a linear scan through the `nums` array, ignoring any elements where `marked[i]` is true. We keep track of the minimum value seen so far and its index.

Once we find the smallest unmarked element at `minIndex`, we add its value `nums[minIndex]` to our running `score`. Then, we mark this element and its neighbors. We set `marked[minIndex]` to true. If `minIndex - 1` is a valid index, we set `marked[minIndex - 1]` to true. Similarly, if `minIndex + 1` is a valid index, we set `marked[minIndex + 1]` to true. We repeat this entire process until all elements in the array are marked.

```java
class Solution {
    public long findScore(int[] nums) {
        int n = nums.length;
        boolean[] marked = new boolean[n];
        long score = 0;
        int markedCount = 0;

        while (markedCount < n) {
            int minVal = Integer.MAX_VALUE;
            int minIndex = -1;

            // Find the smallest unmarked element with the smallest index
            for (int i = 0; i < n; i++) {
                if (!marked[i]) {
                    if (nums[i] < minVal) {
                        minVal = nums[i];
                        minIndex = i;
                    } 
                    // Tie-breaking (smallest index) is handled naturally by the loop's direction
                }
            }

            if (minIndex == -1) {
                break; // All elements are marked
            }

            // Add to score
            score += nums[minIndex];

            // Mark the element and its neighbors
            if (!marked[minIndex]) {
                marked[minIndex] = true;
                markedCount++;
            }
            if (minIndex > 0 && !marked[minIndex - 1]) {
                marked[minIndex - 1] = true;
                markedCount++;
            }
            if (minIndex < n - 1 && !marked[minIndex + 1]) {
                marked[minIndex + 1] = true;
                markedCount++;
            }
        }
        return score;
    }
}
```
The tie-breaking rule (smallest index) is naturally handled by the linear scan from left to right. If two elements have the same minimum value, the one with the smaller index will be found and stored first.
### Algorithm
*   Initialize a `long` variable `score` to 0.
*   Create a boolean array `marked` of the same size as `nums`, initialized to `false`.
*   Use a counter `markedCount` to track the number of marked elements.
*   Loop until `markedCount` equals the length of `nums`.
*   Inside the loop, find the smallest unmarked element by iterating through the entire array.
*   Add the found element's value to `score`.
*   Mark the chosen element and its two adjacent elements (if they exist and are not already marked), updating `markedCount`.
*   Return the final `score`.

## Sorting with Index Tracking
A more efficient approach involves pre-processing the array to determine the order in which elements should be considered. The rule is to pick the smallest value, with ties broken by the smallest index. This is a standard sorting criterion. We can create pairs of `(value, index)`, sort them, and then iterate through the sorted list to calculate the score.
**Time:** O(N log N). The dominant operation is sorting the `N` elements, which takes `O(N log N)`. The subsequent iteration through the sorted elements takes `O(N)`. · **Space:** O(N). We need `O(N)` space for the `indexedNums` array to store values and indices, and another `O(N)` for the `marked` array.
**Pros:** Much more efficient than the brute-force approach.; Guaranteed to pass within the time limits for the given constraints.
**Cons:** Requires extra space proportional to the input size to store the indexed pairs for sorting.
### Explanation
The bottleneck in the brute-force approach is repeatedly finding the minimum element. We can optimize this by figuring out the order of selection upfront. The problem states we should always pick the available element with the smallest value, and use the smallest index as a tie-breaker. This is equivalent to sorting the elements based on their value, and then their original index.

We first create a data structure, like a 2D array or a list of custom objects, to store both the value and the original index of each element from the input array `nums`. Then, we sort this structure. After sorting, we can iterate through the elements in their prioritized order.

For each element `(value, index)` in our sorted list, we check a `marked` array to see if the element at this original `index` has already been marked by a previous step. If it hasn't, we add its `value` to the `score` and mark the element itself and its adjacent neighbors in the original array layout. If it's already marked, we simply skip it and move to the next element in the sorted list.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public long findScore(int[] nums) {
        int n = nums.length;
        int[][] indexedNums = new int[n][2];
        for (int i = 0; i < n; i++) {
            indexedNums[i][0] = nums[i];
            indexedNums[i][1] = i;
        }

        // Sort by value, then by index for tie-breaking
        Arrays.sort(indexedNums, (a, b) -> {
            if (a[0] != b[0]) {
                return Integer.compare(a[0], b[0]);
            } else {
                return Integer.compare(a[1], b[1]);
            }
        });

        boolean[] marked = new boolean[n];
        long score = 0;

        for (int i = 0; i < n; i++) {
            int val = indexedNums[i][0];
            int index = indexedNums[i][1];

            if (!marked[index]) {
                score += val;
                marked[index] = true;
                if (index > 0) {
                    marked[index - 1] = true;
                }
                if (index < n - 1) {
                    marked[index + 1] = true;
                }
            }
        }
        return score;
    }
}
```
This approach processes each element from the sorted list once, making it much faster.
### Algorithm
*   Create a list of pairs or a 2D array to store `(value, original_index)` for each element in `nums`.
*   Sort this list. The primary sorting key is the value (ascending), and the secondary key is the index (ascending).
*   Initialize a `long` variable `score` to 0.
*   Create a boolean array `marked` of size `N`, initialized to `false`.
*   Iterate through the sorted list of pairs `(val, idx)`.
*   For each pair, if the element at `idx` is not already marked:
    *   Add `val` to `score`.
    *   Mark the element at `idx` and its neighbors (`idx-1` and `idx+1`) as true.
*   Return the final `score`.

## Using a Min-Heap (Priority Queue)
This approach is similar in efficiency to sorting but uses a min-heap (Priority Queue) data structure. A min-heap is ideal for repeatedly finding and removing the minimum element from a collection. We populate a min-heap with all elements (as `(value, index)` pairs) and then iteratively extract the minimum, update the score, and mark elements.
**Time:** O(N log N). Inserting `N` elements into the priority queue takes `O(N log N)`. The main loop runs up to `N` times, and each `poll` operation takes `O(log N)`, leading to a total time complexity of `O(N log N)`. · **Space:** O(N). The priority queue can store up to `N` elements, and the `marked` array also requires `O(N)` space.
**Pros:** Efficient and a natural fit for problems requiring repeated extraction of minimum/maximum elements.; Asymptotically equivalent in performance to the sorting approach.
**Cons:** Can have slightly higher constant factor overhead compared to sorting in some language implementations.; Requires extra space for the heap and the marked array.
### Explanation
Instead of sorting all elements at once, we can use a min-heap (implemented as a `PriorityQueue` in Java) to maintain the set of available elements and efficiently retrieve the one with the highest priority (smallest value, then smallest index).

First, we populate the priority queue with pairs of `(value, index)` for every element in the input array. The priority queue is configured with a custom comparator to order pairs first by value, and then by index in case of a tie.

Then, we enter a loop that continues as long as the priority queue is not empty. In each iteration, we extract the element with the highest priority (the minimum). We then check our `marked` array to see if this element has already been marked by a previous step (as a neighbor of another chosen element). If it's already marked, we discard it and proceed to the next iteration. If not, it's a valid choice. We add its value to the `score` and mark it and its neighbors in the `marked` array.

```java
import java.util.PriorityQueue;

class Solution {
    public long findScore(int[] nums) {
        int n = nums.length;
        // PriorityQueue stores [value, index]
        // It's a min-heap ordered by value, then index.
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) {
                return Integer.compare(a[0], b[0]);
            } else {
                return Integer.compare(a[1], b[1]);
            }
        });

        for (int i = 0; i < n; i++) {
            pq.offer(new int[]{nums[i], i});
        }

        boolean[] marked = new boolean[n];
        long score = 0;

        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int val = top[0];
            int index = top[1];

            if (!marked[index]) {
                score += val;
                marked[index] = true;
                if (index > 0) {
                    marked[index - 1] = true;
                }
                if (index < n - 1) {
                    marked[index + 1] = true;
                }
            }
        }
        return score;
    }
}
```
This method is conceptually similar to the sorting approach but processes elements dynamically rather than in a pre-sorted batch.
### Algorithm
*   Create a min-heap (Priority Queue) that orders elements first by value, then by index.
*   Insert all `(nums[i], i)` pairs into the min-heap.
*   Initialize a `long` variable `score` to 0.
*   Create a boolean array `marked` of size `N`, initialized to `false`.
*   While the min-heap is not empty:
    *   Extract the top element `(val, idx)` from the heap.
    *   If the element at `idx` is already marked, ignore it and continue.
    *   If it's not marked:
        *   Add `val` to `score`.
        *   Mark the element at `idx` and its neighbors (`idx-1` and `idx+1`) as true.
*   Return the final `score`.

# Solutions
### Java

```java
class Solution {
public
  long findScore(int[] nums) {
    int n = nums.length;
    boolean[] vis = new boolean[n];
    PriorityQueue<int[]> q =
        new PriorityQueue<>((a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    for (int i = 0; i < n; ++i) {
      q.offer(new int[]{nums[i], i});
    }
    long ans = 0;
    while (!q.isEmpty()) {
      var p = q.poll();
      ans += p[0];
      vis[p[1]] = true;
      for (int j : List.of(p[1] - 1, p[1] + 1)) {
        if (j >= 0 && j < n) {
          vis[j] = true;
        }
      }
      while (!q.isEmpty() && vis[q.peek()[1]]) {
        q.poll();
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long findScore(vector<int> &nums) {
    int n = nums.size();
    vector<bool> vis(n);
    using pii = pair<int, int>;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    for (int i = 0; i < n; ++i) {
      q.emplace(nums[i], i);
    }
    long long ans = 0;
    while (!q.empty()) {
      auto [x, i] = q.top();
      q.pop();
      ans += x;
      vis[i] = true;
      if (i + 1 < n) {
        vis[i + 1] = true;
      }
      if (i - 1 >= 0) {
        vis[i - 1] = true;
      }
      while (!q.empty() && vis[q.top().second]) {
        q.pop();
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findScore(self, nums: List[int]) -> int: n = len(nums) vis = [False] * n q = [(x, i) for i, x in enumerate(nums)] heapify(q) ans = 0 while q: x, i = heappop(q) ans += x vis[i] = True for j in (i - 1, i + 1): if 0 <= j < n: vis[j] = True while q and vis[q[0][1]]: heappop(q) return ans

```