You are given an array nums consisting of positive integers.
Starting with score = 0, apply the following algorithm:
score.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.
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 <= 1051 <= nums[i] <= 106Sort a copy of the array while maintaining the original indices to easily find the smallest element to mark. Use an auxiliary array to track marked elements. This approach finds the next smallest unmarked element in constant time after sorting.
This C code sorts the array with indices maintained, ensures constant time lookup for the smallest element, and tracks marked elements using a simple integer array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing indices and marked status.
Use a priority queue (or min-heap) to efficiently select the smallest element that is unmarked at each step. This reduces the overall time spent searching for the next smallest element in a sorted list, ensuring optimized selection.
In this C implementation, we created a list of elements with values and indices and sorted it. Since a priority queue isn't available natively in C, we sort to simulate the behavior of selecting minimum values.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) for sorting instead of using priority queue directly.
Space Complexity: O(n) for the element list and marking status.
| Approach | Complexity |
|---|---|
| Approach 1: Greedy with Sorting and Marking | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Priority Queue Based Greedy Selection | Time Complexity: O(n log n) for sorting instead of using priority queue directly. |
Find Score of an Array After Marking All Elements | 2 Approaches | Leetcode 2593 | codestorywithMIK • codestorywithMIK • 5,723 views views
Watch 9 more video solutions →Practice Find Score of an Array After Marking All Elements with our built-in code editor and test cases.
Practice on FleetCode