LC-2593 Medium LeetCode

2593. Find Score of an Array After Marking All Elements

Array Hash Table Sorting Heap (Priority Queue) Simulation

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 65% Topics: Array, Hash Table, Sorting, Heap (Priority Queue), Simulation

Reading material

Arrays & Hashing 12 min Sorting 13 min Heaps & Priority Queues 13 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(n)

# simulation, sort, hash table
class Solution(object):
    def findScore(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        idxs = range(len(nums))
        idxs.sort(key=lambda x: (nums[x], x))
        lookup = [False]*len(nums)
        result = 0
        for i in idxs:
            if lookup[i]:
                continue
            lookup[i] = True
            if i-1 >= 0:
                lookup[i-1] = True
            if i+1 < len(lookup):
                lookup[i+1] = True
            result += nums[i]
        return result

Solution from kamyu104/LeetCode-Solutions · MIT