2593 - Find Score of an Array After Marking All Elements

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

Solution 1: Priority Queue (Min Heap)

Solution 2: Sorting

C++

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

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

PYTHON

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