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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7

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 <= 10^5
  • 1 <= nums[i] <= 10^6

Solution

Video explanation

Here is the video explaining this method in detail. Please check it out:

Method 1 - Naive way to finding min element in array

Here is the approach:

  1. Initial Setup:
    • Start with a score (score = 0).
    • Use a boolean array to keep track of which elements are marked.
  2. Iteration:
    • Continuously search for the smallest unmarked integer in the array.
    • Add the value of this integer to score.
    • Mark this integer and its adjacent elements (if they exist) as processed.
    • Repeat the steps until all elements are marked.
  3. Termination:
    • The process stops when all elements in the nums array are marked.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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

        while (true) {
            int minVal = Integer.MAX_VALUE;
            int minIndex = -1;

            for (int i = 0; i < n; i++) {
                if (!marked[i] && nums[i] < minVal) {
                    minVal = nums[i];
                    minIndex = i;
                }
            }

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

            // Add the minimum value to score
            score += nums[minIndex];

            // Mark the chosen element and its adjacent elements
            if (minIndex > 0) marked[minIndex - 1] = true;
            marked[minIndex] = true;
            if (minIndex < n - 1) marked[minIndex + 1] = true;
        }

        return score;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def find_score(self, nums: List[int]) -> int:
        n: int = len(nums)
        marked: List[bool] = [False] * n
        score: int = 0

        while True:
            min_val: int = float('inf')
            min_index: int = -1

            for i in range(n):
                if not marked[i] and nums[i] < min_val:
                    min_val = nums[i]
                    min_index = i

            if min_index == -1:
                break  # All elements are marked

            # Add the minimum value to score
            score += nums[min_index]

            # Mark the chosen element and its adjacent elements
            if min_index > 0:
                marked[min_index - 1] = True
            marked[min_index] = True
            if min_index < n - 1:
                marked[min_index + 1] = True

        return score

Complexity

  • ⏰ Time complexity: O(n^2)
    • Finding the smallest unmarked element in each iteration takes O(n).
    • In the worst case, this operation is repeated n times, leading to a total time complexity of O(n^2).
  • 🧺 Space complexity: O(n)
    • We use an additional boolean array of size n to keep track of marked elements, making the space complexity O(n).

Method 2 - Using Minheap

The key observation for an efficient solution is that we need to repeatedly find the smallest unmarked element and mark it along with its adjacent elements. Using a min-heap (priority queue) allows us to efficiently retrieve the smallest element in logarithmic time. By marking adjacent elements immediately upon processing the smallest element, we ensure that these elements are not reconsidered in future iterations, preserving the constraint of marking and managing all elements efficiently.

Here is the approach:

  1. Initial Setup:
    • Create a priority queue (min-heap) and insert each element of the array along with its index into the heap.
    • Maintain a boolean array to keep track of which elements are marked.
  2. Processing Elements:
    • Continuously extract the smallest element from the heap.
    • If the extracted element is already marked, skip it.
    • If it is unmarked, add its value to the score and mark it.
    • Additionally, mark its adjacent elements (if they exist).
  3. Termination:
    • The process stops when all elements of the array are either extracted from the heap or marked.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
    public long findScore(int[] nums) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) return a[0] - b[0];
            else return a[1] - b[1];
        });
        
        int n = nums.length;
        for (int i = 0; i < nums.length; i++) {
            pq.add(new int[]{nums[i], i});
        }
        
        boolean[] marked = new boolean[n];
        long ans = 0;
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int currNum = curr[0];
            int currIdx = curr[1];
            
            if (marked[currIdx]) {
	            continue;
	        }
            ans += currNum;
            marked[currIdx] = true;
            if (currIdx + 1 < n) {
	            marked[currIdx + 1] = true;
	        }
            if (currIdx - 1 >= 0) {
	            marked[currIdx - 1] = true;
	        }
        }
        
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def find_score(self, nums: List[int]) -> int:
        n: int = len(nums)
        pq: List[List[int]] = [[nums[i], i] for i in range(n)]
        heapq.heapify(pq)
        marked: List[bool] = [False] * n
        ans: int = 0
        
        while pq:
            curr: List[int] = heapq.heappop(pq)
            curr_num: int = curr[0]
            curr_idx: int = curr[1]
            
            if marked[curr_idx]:
                continue
            ans += curr_num
            marked[curr_idx] = True
            if curr_idx + 1 < n:
                marked[curr_idx + 1] = True
            if curr_idx - 1 >= 0:
                marked[curr_idx - 1] = True
        
        return ans

Complexity

  • ⏰ Time complexity: O(n log n)
    • Inserting all elements into the min-heap initially takes O(n log n).
    • Each extraction and insertion operation in the heap is O(log n).
    • Given that each element is processed once, the total time complexity for heap operations is O(n log n).
  • 🧺 Space complexity: O(n)