1 minute read

Problem Statement

problem

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 most n indices, resulting in an overall space complexity of O(n).

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