2593. Find Score of an Array After Marking All Elements

MediumView on LeetCode

Array Greedy Heap (Priority Queue)Simulation

Time: O(n log n)

Space: O(n)

Intuition

Find score of array: pick max, add to score, remove max and its neighbors. Use max-heap with visited tracking.

Algorithm

1Max-heap. While heap not empty: pop max, if not visited: score += val, mark neighbors visited.

Common Pitfalls

•Greedy max selection. Skip already-removed elements. Linked list or visited array for neighbor tracking.

2593.cs

// Approach: Sort (value, index) pairs; greedily pick smallest unmarked and mark its neighbors.
// Time: O(n log n) Space: O(n)

public class Solution
{
    public long FindScore(int[] nums)
    {
        long ans = 0;
        SortedSet<int[]> numAndIndices = new SortedSet<int[]>(Comparer<int[]>.Create((a, b) =>
            a[0] == b[0] ? a[1].CompareTo(b[1]) : a[0].CompareTo(b[0])));
        bool[] seen = new bool[nums.Length];

        for (int i = 0; i < nums.Length; ++i)
            numAndIndices.Add(new int[] { nums[i], i });

        foreach (var pair in numAndIndices)
        {
            int num = pair[0];
            int i = pair[1];
            if (seen[i])
                continue;
            if (i > 0)
                seen[i - 1] = true;
            if (i + 1 < nums.Length)
                seen[i + 1] = true;
            seen[i] = true;
            ans += num;
        }

        return ans;
    }
}

Was this solution helpful?