2695. Find Score Of An Array After Marking All Elements¶

LeetCode Problem View on GitHub

2695. Find Score of an Array After Marking All Elements

Medium

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¶

class Solution {
    static class Pair {
        int node;
        int ind;
        public Pair(int node, int ind) {
            this.node = node;
            this.ind = ind;
        }
    }
    static class sorting implements Comparator<Pair> {
        @Override
        public int compare(Pair first , Pair second) {
            int op1 = Integer.compare(first.node, second.node);
            if(op1 != 0) return op1;
            return Integer.compare(first.ind , second.ind);
        }
    }
    public long findScore(int[] nums) {
        int n = nums.length;
        PriorityQueue<Pair> pq = new PriorityQueue<>(new sorting());
        for(int i = 0; i < n; i++) pq.offer(new Pair(nums[i], i));
        HashSet<Integer> visited = new HashSet<>();
        long total = 0;
        while(pq.size() > 0) {
            Pair current = pq.poll();
            if(visited.contains(current.ind)) continue;
            total += current.node;
            visited.add(current.ind);
            if(current.ind -1 >= 0) visited.add(current.ind - 1);
            if(current.ind + 1 < n) visited.add(current.ind + 1);
        }
        return total;
    }
}

Complexity Analysis¶

• Time Complexity: O(?)
• Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here