Find score of an array after marking all elements

Array Hash Table Sorting Heap (Priority Queue) Simulation

64.5% acceptance

Feb 25, 2026

940

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_score(nums: Vec<i32>) -> i64 {
    // Algorithm: always pick smallest unmarked element (ties: smallest index),
    // add to score, mark it and its two adjacent elements.
    // Use a min-heap of (value, index).
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;
    let n = nums.len();
    let mut heap: BinaryHeap<Reverse<(i32, usize)>> = (0..n)
      .map(|i| Reverse((nums[i], i)))
      .collect();
    let mut marked = vec![false; n];
    let mut score = 0i64;
    while let Some(Reverse((val, i))) = heap.pop() {
      if marked[i] { continue; }
      score += val as i64;
      marked[i] = true;
      if i > 0 { marked[i - 1] = true; }
      if i + 1 < n { marked[i + 1] = true; }
    }
    score
  }
}