Skip to content

2593. Find Score of an Array After Marking All Elements 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  long long findScore(vector<int>& nums) {
    long long ans = 0;
    set<pair<int, int>> numAndIndices;
    vector<bool> seen(nums.size());

    for (int i = 0; i < nums.size(); ++i)
      numAndIndices.insert({nums[i], i});

    for (const auto& [num, i] : numAndIndices) {
      if (seen[i])
        continue;
      if (i > 0)
        seen[i - 1] = true;
      if (i + 1 < nums.size())
        seen[i + 1] = true;
      seen[i] = true;
      ans += num;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public long findScore(int[] nums) {
    long ans = 0;
    TreeSet<Pair<Integer, Integer>> numAndIndices =
        new TreeSet<>((a, b)
                          -> a.getKey().equals(b.getKey()) ? a.getValue() - b.getValue()
                                                           : a.getKey() - b.getKey());
    boolean[] seen = new boolean[nums.length];

    for (int i = 0; i < nums.length; ++i)
      numAndIndices.add(new Pair<>(nums[i], i));

    for (Pair<Integer, Integer> pair : numAndIndices) {
      final int num = pair.getKey();
      final int i = pair.getValue();
      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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def findScore(self, nums: List[int]) -> int:
    ans = 0
    seen = set()

    for num, i in sorted([(num, i) for i, num in enumerate(nums)]):
      if i in seen:
        continue
      seen.add(i - 1)
      seen.add(i + 1)
      seen.add(i)
      ans += num

    return ans