Leetcode 2593: Find Score of an Array After Marking All Elements
You are given an array
nums consisting of positive integers. Starting with a score = 0, repeatedly select the smallest unmarked integer, add its value to the score, and mark it along with its adjacent elements (if any). Continue this until all elements are marked, then return the final score.Problem
Approach
Steps
Complexity
Input: The input consists of a single integer array `nums` representing the array of positive integers.
Example: For example, `nums = [3, 2, 5, 4, 1]`.
Constraints:
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
Output: The output is a single integer representing the final score achieved after applying the algorithm.
Example: For `nums = [3, 2, 5, 4, 1]`, the output is `6`.
Constraints:
• The output is an integer representing the final score.
Goal: The goal is to choose the smallest unmarked element, add its value to the score, and mark it along with its adjacent elements until all elements are marked.
Steps:
• 1. Initialize a score variable to 0.
• 2. Use a priority queue to efficiently find the smallest unmarked element.
• 3. Add the value of the chosen element to the score.
• 4. Mark the chosen element and its adjacent elements (if they exist).
• 5. Repeat the process until all elements are marked.
Goal: The input array will have a length between 1 and 10^5. Each element in the array will be a positive integer between 1 and 10^6.
Steps:
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
Assumptions:
• The input array will always contain at least one integer, and each element will be between 1 and 10^6.
• Input: For `nums = [3, 2, 5, 4, 1]`
• Explanation: By following the algorithm, we first select `1`, then `2`, and finally `4`. The final score is `1 + 2 + 3 = 6`.
Approach: The approach involves selecting the smallest unmarked element using a priority queue and applying the algorithm to maximize the score.
Observations:
• We can use a priority queue (min-heap) to efficiently find the smallest unmarked element.
• The greedy approach ensures we select the smallest element at each step to maximize the score.
Steps:
• 1. Create a priority queue to store the elements along with their indices.
• 2. For each element in the priority queue, check if it has already been marked.
• 3. If it is unmarked, add its value to the score and mark it and its adjacent elements.
• 4. Repeat this process until all elements are marked.
Empty Inputs:
• The input array will always contain at least one element, so there will be no empty inputs.
Large Inputs:
• The solution should handle large inputs efficiently with a time complexity of O(n log n).
Special Values:
• If all elements in `nums` are the same, the algorithm should still function correctly.
Constraints:
• The input array will always meet the specified constraints.
long long findScore(vector<int>& nums) {
long long score = 0;
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
int n = nums.size();
unordered_map<int, int> mp;
for(int i = 0; i < n; i++)
pq.push({nums[i], i});
while(!pq.empty()) {
while(!pq.empty() && mp.count(pq.top()[1])) pq.pop();
if(!pq.empty()) {
score += pq.top()[0];
mp[pq.top()[1]] = true;
mp[pq.top()[1] + 1] = true;
mp[pq.top()[1] - 1] = true;
pq.pop();
}
}
return score;
}
1 : Function Definition
long long findScore(vector<int>& nums) {
This is the function definition where we declare 'findScore', which takes a vector of integers as input and returns a long long score.
2 : Variable Initialization
long long score = 0;
We initialize the 'score' variable to 0, which will hold the total score.
3 : Priority Queue
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
We declare a priority queue 'pq' that will store vectors of integers, which will be sorted in increasing order based on the first element of the vectors.
4 : Size of Input
int n = nums.size();
We store the size of the input vector 'nums' in the variable 'n'.
5 : Hash Map
unordered_map<int, int> mp;
We declare an unordered map 'mp' to track which indices have already been processed.
6 : Loop Initialization
for(int i = 0; i < n; i++)
This is a loop that iterates through each element of the input vector 'nums'.
7 : Push to Priority Queue
pq.push({nums[i], i});
We push a vector containing the current element 'nums[i]' and its index 'i' into the priority queue.
8 : While Loop
while(!pq.empty()) {
This is a while loop that continues until the priority queue is empty.
9 : Check Processed Indices
while(!pq.empty() && mp.count(pq.top()[1])) pq.pop();
We check if the top element of the priority queue has already been processed. If it has, we pop it from the queue.
10 : If Not Empty
if(!pq.empty()) {
We proceed if the priority queue is not empty after cleaning out the processed elements.
11 : Add to Score
score += pq.top()[0];
We add the value of the top element in the priority queue (which is the first element of the vector) to the score.
12 : Mark Current Index
mp[pq.top()[1]] = true;
We mark the current index as processed in the 'mp' map.
13 : Mark Adjacent Indices
mp[pq.top()[1] + 1] = true;
We mark the next index as processed.
14 : Mark Adjacent Indices
mp[pq.top()[1] - 1] = true;
We mark the previous index as processed.
15 : Pop from Priority Queue
pq.pop();
We remove the top element from the priority queue after processing it.
16 : Return Score
return score;
We return the calculated score after processing all elements.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is O(n log n) due to the use of a priority queue for selecting the smallest unmarked element.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we need extra space for the priority queue and marking elements.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus