Find Score of an Array After Marking All Elements

MediumArrayHash TableSortingHeap (Priority Queue)Simulation

Solution

export function findScore(nums: number[]): number {
  let answer = 0;
  const marked = new Set<number>();
  const sortedNums = nums
    .map((num, i) => [num, i])
    .sort((a, b) => (a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]));
  for (const [num, i] of sortedNums) {
    if (!marked.has(i)) {
      answer += num;
      marked.add(i + 1);
      marked.add(i - 1);
    }
  }
  return answer;
}

Complexity

  • Time: O(nlogn)O(n \cdot logn)
  • Space: O(n+S)O(n + S)
    • SS: 정렬 알고리즘에 필요한 공간 복잡도