Problem of The Day: Find Score of an Array After Marking All Elements
Problem Statement
Intuition
The problem involves selecting elements from an array while avoiding adjacent elements. The goal is to maximize the sum of the selected elements. The intuition is to always choose the smallest unmarked element and mark its adjacent elements to prevent their selection in subsequent iterations. This greedy approach helps maximize the sum by ensuring we select the next smallest available number.
Approach
We begin by inserting all elements of the array into a min-heap, where the smallest element is always accessible. We maintain a set marked
to track the indices of the elements that have been selected or their adjacent elements that are unavailable.
- Step 1: For each element in the
nums
array, push the number and its index into the heap. - Step 2: While the heap is not empty:
- Pop the smallest element from the heap.
- If the current element’s index is already in the
marked
set, skip it. - Otherwise, add the element’s value to the result
res
. - Mark the current element’s index and its adjacent elements (i.e., the previous and next indices).
This approach ensures that we select elements in the optimal order to maximize the sum while respecting the adjacency constraint.
Complexity
- Time complexity:
- Heap operations (push and pop) each take O(log n) time.
- For each element in the array, we perform a heap push and pop operation, so the total time complexity is O(n log n), where
n
is the number of elements in the array.
- Space complexity:
- The heap stores all
n
elements, so the space complexity is O(n). - The
marked
set also stores at mostn
indices, resulting in an overall space complexity of O(n).
- The heap stores all
Code
import heapq
from typing import List
class Solution:
def findScore(self, nums: List[int]) -> int:
min_heap = []
marked = set()
res = 0
for i, num in enumerate(nums):
heapq.heappush(min_heap, (num, i))
while min_heap:
num, index = heapq.heappop(min_heap)
if index in marked:
continue
res += num
marked.add(index)
marked.add(index + 1)
marked.add(index - 1)
return res