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.
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.
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
