Leetcode # 2593. Find Score of an Array After Marking All Elements

Problem

https://leetcode.com/problems/find-score-of-an-array-after-marking-all-elements

Solution: Sorting

Sort by Multiple Keys

Time Complexity: O(len(nums) * log(len(nums)))
Space Complexity: O(len(nums))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def findScore(self, nums: List[int]) -> int:
    nums = [[n, i] for i, n in enumerate(nums)]
    nums.sort(key=lambda e: (e[0], e[1]))
    marked, score = set(), 0
    for n, i in nums:
      if i in marked: continue
      score += n
      marked.add(i)
      if i - 1 >= 0: marked.add(i - 1)
      if i + 1 < len(nums): marked.add(i + 1)
    return score

Solution: Priority Queue (heapq)

Time Complexity: O(len(nums) * log(len(nums)))
Space Complexity: O(len(nums))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def findScore(self, nums: List[int]) -> int:
    pq = []
    for i, n in enumerate(nums):
      heappush(pq, (n, i)) # Max Time Complexity: O(log(len(nums)))
    
    marked, score = set(), 0
    while pq:
      n, i = heappop(pq) # Max Time Complexity: O(log(len(nums)))
      if i in marked: continue
      print(n, i)
      score += n
      marked.add(i)
      if i - 1 >= 0: marked.add(i - 1)
      if i + 1 < len(nums): marked.add(i + 1)
    return score

Last Updated on 2024/12/15 by A1go