##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2593.html

# 2593. Find Score of an Array After Marking All Elements

## 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.

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

## Solutions

• 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;
}
}

• 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;
}
};

• 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


• func findScore(nums []int) (ans int64) {
h := hp{}
for i, x := range nums {
heap.Push(&h, pair{x, i})
}
n := len(nums)
vis := make([]bool, n)
for len(h) > 0 {
p := heap.Pop(&h).(pair)
x, i := p.x, p.i
ans += int64(x)
vis[i] = true
for _, j := range []int{i - 1, i + 1} {
if j >= 0 && j < n {
vis[j] = true
}
}
for len(h) > 0 && vis[h[0].i] {
heap.Pop(&h)
}
}
return
}

type pair struct{ x, i int }
type hp []pair

func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i].x < h[j].x || (h[i].x == h[j].x && h[i].i < h[j].i) }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

• interface pair {
x: number;
i: number;
}

function findScore(nums: number[]): number {
const q = new PriorityQueue({
compare: (a: pair, b: pair) => (a.x === b.x ? a.i - b.i : a.x - b.x),
});
const n = nums.length;
const vis: boolean[] = new Array(n).fill(false);
for (let i = 0; i < n; ++i) {
q.enqueue({ x: nums[i], i });
}
let ans = 0;
while (!q.isEmpty()) {
const { x, i } = q.dequeue()!;
if (vis[i]) {
continue;
}
ans += x;
vis[i] = true;
if (i - 1 >= 0) {
vis[i - 1] = true;
}
if (i + 1 < n) {
vis[i + 1] = true;
}
while (!q.isEmpty() && vis[q.front()!.i]) {
q.dequeue();
}
}
return ans;
}