2593. Find Score of an Array After Marking All Elements LeetCode Solution

In this guide, you will get 2593. Find Score of an Array After Marking All Elements LeetCode Solution with the best time and space complexity. The solution to Find Score of an Array After Marking All Elements problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Find Score of an Array After Marking All Elements solution in C++
  4. Find Score of an Array After Marking All Elements solution in Java
  5. Find Score of an Array After Marking All Elements solution in Python
  6. Additional Resources
2593. Find Score of an Array After Marking All Elements LeetCode Solution image

Problem Statement of Find Score of an Array After Marking All Elements

You are given an array nums consisting of positive integers.
Starting with score = 0, apply the following algorithm:

Choose the smallest integer of the array that is not marked. If there is a tie, choose the one with the smallest index.
Add the value of the chosen integer to score.
Mark the chosen element and its two adjacent elements if they exist.
Repeat until all the array elements are marked.

Return the score you get after applying the above algorithm.

Example 1:

Input: nums = [2,1,3,4,5,2]
Output: 7
Explanation: We mark the elements as follows:
– 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,1,3,4,5,2].
– 2 is the smallest unmarked element, so we mark it and its left adjacent element: [2,1,3,4,5,2].
– 4 is the only remaining unmarked element, so we mark it: [2,1,3,4,5,2].
Our score is 1 + 2 + 4 = 7.

See also  2855. Minimum Right Shifts to Sort the Array LeetCode Solution

Example 2:

Input: nums = [2,3,5,1,3,2]
Output: 5
Explanation: We mark the elements as follows:
– 1 is the smallest unmarked element, so we mark it and its two adjacent elements: [2,3,5,1,3,2].
– 2 is the smallest unmarked element, since there are two of them, we choose the left-most one, so we mark the one at index 0 and its right adjacent element: [2,3,5,1,3,2].
– 2 is the only remaining unmarked element, so we mark it: [2,3,5,1,3,2].
Our score is 1 + 2 + 2 = 5.

Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 106

Complexity Analysis

  • Time Complexity: O(n\log n)
  • Space Complexity: O(n)

2593. Find Score of an Array After Marking All Elements LeetCode Solution in C++

class Solution {
 public:
  long long findScore(vector<int>& nums) {
    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;
  }
};
/* code provided by PROGIEZ */

2593. Find Score of an Array After Marking All Elements LeetCode Solution in Java

class Solution {
  public long findScore(int[] nums) {
    long ans = 0;
    TreeSet<Pair<Integer, Integer>> numAndIndices =
        new TreeSet<>(Comparator.comparing(Pair<Integer, Integer>::getKey)
                          .thenComparing(Pair<Integer, Integer>::getValue));
    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;
  }
}
// code provided by PROGIEZ

2593. Find Score of an Array After Marking All Elements LeetCode Solution in Python

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
# code by PROGIEZ

Additional Resources

See also  3386. Button with Longest Push Time LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.