Find Score of an Array After Marking All Elements solution and explanation
Google
9 more videos on this problem
Find Score of an Array After Marking All Elements | 2 Approaches | Leetcode 2593 | codestorywithMIKcodestorywithMIK · 28:16 · 7K views
Find Score of an Array After Marking All Elements | Leetcode 2593Techdose · 11:17 · 3K views
Find Score of an Array After Marking All Elements || Ordered Set || Leetcode-2593Aryan Mittal · 7:16 · 1K views
2593. Find Score of an Array After Marking All Elements | leetcode daily challenge | shashcode30ShashCode · 22:37 · 1K views
Leetcode 2593: Find Score of an Array After Marking All ElementsAlgorithms Casts · 7:41 · 724 views
LeetCode 2593 Find Score of an Array After Marking All Elements | Sorting | HashTable | VisaCode Harmony · 14:35 · 453 views
Find Score of an Array After Marking All Elements | Biweekly Contest 100codingMohan · 9:21 · 237 views
2593. Find Score of an Array After Marking All Elements (Leetcode Easy)Programming Live with Larry · 5:12 · 223 views
Find Score of an Array After Marking All Elements | Leetcode 2593 | Sorting | C++ | BiWeekly 100Tech Courses · 9:16 · 174 views
2593. Find Score of an Array After Marking All ElementsLet's Do It · 9:18 · 151 views
The problem
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.
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] <= 106
Approach overview
Problem Overview: You repeatedly pick the smallest unmarked element in the array, add its value to a running score, then mark that element and its immediate neighbors. The process continues until every element becomes marked. The challenge is efficiently selecting the smallest available element while ensuring already-marked indices are skipped.
Approach 1: Greedy with Sorting and Marking (O(n log n) time, O(n) space)
This approach sorts the elements by value while keeping their original indices. After sorting, iterate through the pairs (value, index) from smallest to largest. If the current index is not marked, add its value to the score and mark index, index - 1, and index + 1. A boolean array tracks which positions are already marked so they are skipped later. Sorting guarantees that the smallest available value is processed first, which satisfies the greedy requirement. This method is simple to implement and works well when you want predictable iteration over elements.
The algorithm uses ideas common in sorting and array traversal problems. Sorting costs O(n log n), while the marking operations remain constant time per element.
Approach 2: Priority Queue Based Greedy Selection (O(n log n) time, O(n) space)
Instead of sorting upfront, push every element into a min-heap as (value, index). Each step pops the smallest value from the heap. If its index is already marked, discard it and continue. Otherwise, add the value to the score and mark the element and its neighbors. The heap dynamically maintains the smallest candidate at the top, which matches the greedy rule of always choosing the minimum unmarked element.
This solution uses a heap (priority queue) to simulate the selection process. Each push and pop operation costs O(log n), leading to overall O(n log n) complexity. The approach is flexible when the selection order must be dynamically maintained rather than precomputed.
Recommended for interviews: The greedy idea is the real test here: always select the smallest unmarked value and invalidate its neighbors. The sorting approach is usually the cleanest explanation during interviews because it processes elements once after ordering them. The priority queue version demonstrates stronger familiarity with greedy selection structures and is useful when discussing alternatives that avoid full sorting.
Approach 1: Approach 1: Greedy with Sorting and Marking
Sort 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.
def find_score(nums):
n = len(nums)
score = 0
marked = [False] * n
sorted_nums = sorted((num, i) for i, num in enumerate(nums))
for value, index in sorted_nums:
if not marked[index]:
score += value
if index > 0:
marked[index - 1] = True
marked[index] = True
if index < n - 1:
marked[index + 1] = True
return score
# Example usage
nums = [2, 1, 3, 4, 5, 2]
print(find_score(nums))import java.util.*;
public class ArrayScore {
public static int findScore(int[] nums) {
int n = nums.length;
int score = 0;
boolean[] marked = new boolean[n];
List<int[]> sorted = new ArrayList<>();
for (int i = 0; i < n; i++) {
sorted.add(new int[] {nums[i], i});
}
sorted.sort(Comparator.comparingInt(a -> a[0]));
for (int[] element : sorted) {
int value = element[0];
int index = element[1];
if (!marked[index]) {
score += value;
if (index > 0) marked[index - 1] = true;
marked[index] = true;
if (index < n - 1) marked[index + 1] = true;
}
}
return score;
}
public static void main(String[] args) {
int[] nums = {2, 1, 3, 4, 5, 2};
System.out.println(findScore(nums));
}
}#include <vector>
#include <iostream>
#include <algorithm>
int findScore(std::vector<int>& nums) {
int score = 0;
int n = nums.size();
std::vector<bool> marked(n, false);
std::vector<std::pair<int, int>> sorted;
for (int i = 0; i < n; ++i) {
sorted.push_back({nums[i], i});
}
std::sort(sorted.begin(), sorted.end());
for (const auto& p : sorted) {
int value = p.first;
int index = p.second;
if (!marked[index]) {
score += value;
if (index > 0) marked[index - 1] = true;
marked[index] = true;
if (index < n - 1) marked[index + 1] = true;
}
}
return score;
}
int main() {
std::vector<int> nums = {2, 1, 3, 4, 5, 2};
std::cout << findScore(nums) << std::endl;
return 0;
}function findScore(nums) {
const n = nums.length;
let score = 0;
const marked = new Array(n).fill(false);
const sorted = nums.map((num, idx) => [num, idx]).sort((a, b) => a[0] - b[0]);
for (const [value, index] of sorted) {
if (!marked[index]) {
score += value;
if (index > 0) marked[index - 1] = true;
marked[index] = true;
if (index < n - 1) marked[index + 1] = true;
}
}
return score;
}
// Example usage
const nums = [2, 1, 3, 4, 5, 2];
console.log(findScore(nums));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return ((int*)a)[0] - ((int*)b)[0];
}
int findScore(int* nums, int numsSize) {
int score = 0;
int marked[numsSize];
for (int i = 0; i < numsSize; ++i) marked[i] = 0;
int sorted[numsSize][2];
for (int i = 0; i < numsSize; ++i) {
sorted[i][0] = nums[i];
sorted[i][1] = i;
}
qsort(sorted, numsSize, sizeof(sorted[0]), compare);
for (int i = 0; i < numsSize; ++i) {
int index = sorted[i][1];
if (!marked[index]) {
score += sorted[i][0];
if (index > 0) marked[index - 1] = 1;
marked[index] = 1;
if (index < numsSize - 1) marked[index + 1] = 1;
}
}
return score;
}
int main() {
int nums[] = {2, 1, 3, 4, 5, 2};
int size = sizeof(nums)/sizeof(nums[0]);
printf("%d\n", findScore(nums, size));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int FindScore(int[] nums) {
int n = nums.Length;
int score = 0;
bool[] marked = new bool[n];
var sorted = new List<(int, int)>();
for (int i = 0; i < n; i++) {
sorted.Add((nums[i], i));
}
sorted.Sort();
foreach (var (value, index) in sorted) {
if (!marked[index]) {
score += value;
if (index > 0) marked[index - 1] = true;
marked[index] = true;
if (index < n - 1) marked[index + 1] = true;
}
}
return score;
}
public static void Main() {
int[] nums = {2, 1, 3, 4, 5, 2};
Solution sol = new Solution();
Console.WriteLine(sol.FindScore(nums));
}
}In this Python solution, we utilize sorting with tuple comparison to maintain indices efficiently. The marking process is handled using a boolean list.
Time Complexity: O(n log n) for sorting.
Space Complexity: O(n) due to space needed for the sorted list.
Approach 2: Approach 2: Priority Queue Based Greedy Selection
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.
import heapq
def find_score(nums):
n = len(nums)
score = 0
marked = [False] * n
heap = [(num, i) for i, num in enumerate(nums)]
heapq.heapify(heap)
while heap:
value, index = heapq.heappop(heap)
if not marked[index]:
score += value
if index > 0:
marked[index - 1] = True
marked[index] = True
if index < n - 1:
marked[index + 1] = True
return score
# Example usage
nums = [2, 1, 3, 4, 5, 2]
print(find_score(nums))import java.util.*;
public class ArrayScore {
static class Element implements Comparable<Element> {
int value;
int index;
Element(int value, int index) {
this.value = value;
this.index = index;
}
@Override
public int compareTo(Element o) {
return Integer.compare(this.value, o.value);
}
}
public static int findScore(int[] nums) {
PriorityQueue<Element> pq = new PriorityQueue<>();
int n = nums.length;
boolean[] marked = new boolean[n];
for (int i = 0; i < n; i++) {
pq.add(new Element(nums[i], i));
}
int score = 0;
while (!pq.isEmpty()) {
Element curr = pq.poll();
if (!marked[curr.index]) {
score += curr.value;
if (curr.index > 0) marked[curr.index - 1] = true;
marked[curr.index] = true;
if (curr.index < n - 1) marked[curr.index + 1] = true;
}
}
return score;
}
public static void main(String[] args) {
int[] nums = {2, 1, 3, 4, 5, 2};
System.out.println(findScore(nums));
}
}#include <iostream>
#include <vector>
#include <queue>
struct Element {
int value;
int index;
bool operator>(const Element& other) const {
return value > other.value;
}
};
int findScore(std::vector<int>& nums) {
std::priority_queue<Element, std::vector<Element>, std::greater<Element>> pq;
int n = nums.size();
std::vector<bool> marked(n, false);
for (int i = 0; i < n; ++i) {
pq.push({nums[i], i});
}
int score = 0;
while (!pq.empty()) {
Element curr = pq.top();
pq.pop();
if (!marked[curr.index]) {
score += curr.value;
if (curr.index > 0) marked[curr.index - 1] = true;
marked[curr.index] = true;
if (curr.index < n - 1) marked[curr.index + 1] = true;
}
}
return score;
}
int main() {
std::vector<int> nums = {2, 1, 3, 4, 5, 2};
std::cout << findScore(nums) << std::endl;
return 0;
}function findScore(nums) {
const n = nums.length;
let score = 0;
const marked = new Array(n).fill(false);
const minHeap = nums.map((num, idx) => [num, idx]);
minHeap.sort((a, b) => a[0] - b[0]);
while (minHeap.length > 0) {
const [value, index] = minHeap.shift();
if (!marked[index]) {
score += value;
if (index > 0) marked[index - 1] = true;
marked[index] = true;
if (index < n - 1) marked[index + 1] = true;
}
}
return score;
}
// Example usage
const nums = [2, 1, 3, 4, 5, 2];
console.log(findScore(nums));#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct {
int value;
int index;
} Element;
int compare(const void *a, const void *b) {
return ((Element*)a)->value - ((Element*)b)->value;
}
int findScore(int* nums, int numsSize) {
Element* elements = (Element*)malloc(numsSize * sizeof(Element));
for (int i = 0; i < numsSize; i++) {
elements[i].value = nums[i];
elements[i].index = i;
}
qsort(elements, numsSize, sizeof(Element), compare);
bool* marked = (bool*)malloc(numsSize * sizeof(bool));
for (int i = 0; i < numsSize; i++) marked[i] = false;
int score = 0;
for (int i = 0; i < numsSize; ++i) {
int value = elements[i].value;
int index = elements[i].index;
if (!marked[index]) {
score += value;
if (index > 0) marked[index - 1] = true;
marked[index] = true;
if (index < numsSize - 1) marked[index + 1] = true;
}
}
free(elements);
free(marked);
return score;
}
int main() {
int nums[] = {2, 1, 3, 4, 5, 2};
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", findScore(nums, size));
return 0;
}using System;
using System.Collections.Generic;
class Solution {
public int FindScore(int[] nums) {
int n = nums.Length;
int score = 0;
bool[] marked = new bool[n];
SortedSet<(int value, int index)> pq = new SortedSet<(int, int)>();
for (int i = 0; i < n; i++) {
pq.Add((nums[i], i));
}
while (pq.Count > 0) {
var curr = pq.Min;
pq.Remove(curr);
if (!marked[curr.index]) {
score += curr.value;
if (curr.index > 0) marked[curr.index - 1] = true;
marked[curr.index] = true;
if (curr.index < n - 1) marked[curr.index + 1] = true;
}
}
return score;
}
public static void Main() {
int[] nums = {2, 1, 3, 4, 5, 2};
Solution sol = new Solution();
Console.WriteLine(sol.FindScore(nums));
}
}The Python approach uses `heapq` to implement a priority queue, efficiently keeping track of the smallest element to choose, giving a streamlined element marking.
Time Complexity: O(n log n) due to heap operations.
Space Complexity: O(n) for heap and marking structures.
Approach 3: Priority Queue (Min Heap)
We use a priority queue to maintain the unmarked elements in the array, and each item in the queue is a tuple (x, i), where x and i represent the element value and index of the array respectively. An array vis is used to record whether the element in the array is marked.
Each time we take out the smallest element (x, i) from the queue, we add x to the answer, and then mark the element at the i position, and the left and right adjacent elements at the i position, that is, the elements at the i-1 and i+1 positions. Then we determine whether the top element of the heap is marked. If it is marked, pop the top element of the heap until the top element is unmarked or the heap is empty.
Finally, return the answer.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the length of the array.
interface pair {
x: number;
i: number;
}
function findScore(nums: number[]): number {
const q = new PriorityQueue({
compare: (a: pair, b: pair) => (a.x === b.x ? a.i - b.i : a.x - b.x),
});
const n = nums.length;
const vis: boolean[] = new Array(n).fill(false);
for (let i = 0; i < n; ++i) {
q.enqueue({ x: nums[i], i });
}
let ans = 0;
while (!q.isEmpty()) {
const { x, i } = q.dequeue()!;
if (vis[i]) {
continue;
}
ans += x;
vis[i] = true;
if (i - 1 >= 0) {
vis[i - 1] = true;
}
if (i + 1 < n) {
vis[i + 1] = true;
}
while (!q.isEmpty() && vis[q.front()!.i]) {
q.dequeue();
}
}
return ans;
}func findScore(nums []int) (ans int64) {
h := hp{}
for i, x := range nums {
heap.Push(&h, pair{x, i})
}
n := len(nums)
vis := make([]bool, n)
for len(h) > 0 {
p := heap.Pop(&h).(pair)
x, i := p.x, p.i
ans += int64(x)
vis[i] = true
for _, j := range []int{i - 1, i + 1} {
if j >= 0 && j < n {
vis[j] = true
}
}
for len(h) > 0 && vis[h[0].i] {
heap.Pop(&h)
}
}
return
}
type pair struct{ x, i int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].x < h[j].x || (h[i].x == h[j].x && h[i].i < h[j].i) }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }Approach 4: Sorting
We can create an index array idx where idx[i]=i, and then we sort the index array idx according to the element values in the array nums. If the element values are the same, then sort them according to the index values.
Next, create an array vis of length n+2 where vis[i]=false, which means whether the element in the array is marked.
We traverse the index array idx, and for each index i in the array, if vis[i+1] is false, that is, the element at position i is not marked, we add nums[i] to the answer, and then mark the element at position i, and the left and right adjacent elements at position i, that is, the elements at positions i-1 and i+1. Continue to traverse the index array idx until the end.
Finally, return the answer.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the length of the array.
function findScore(nums: number[]): number {
const n = nums.length;
const idx: number[] = new Array(n);
for (let i = 0; i < n; ++i) {
idx[i] = i;
}
idx.sort((i, j) => (nums[i] == nums[j] ? i - j : nums[i] - nums[j]));
const vis: boolean[] = new Array(n + 2).fill(false);
let ans = 0;
for (const i of idx) {
if (!vis[i + 1]) {
ans += nums[i];
vis[i] = true;
vis[i + 2] = true;
}
}
return ans;
}func findScore(nums []int) (ans int64) {
n := len(nums)
idx := make([]int, n)
for i := range idx {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool {
i, j = idx[i], idx[j]
return nums[i] < nums[j] || (nums[i] == nums[j] && i < j)
})
vis := make([]bool, n+2)
for _, i := range idx {
if !vis[i+1] {
ans += int64(nums[i])
vis[i], vis[i+2] = true, true
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Greedy with Sorting and Marking | Time Complexity: O(n log n) for sorting. |
| Approach 2: Priority Queue Based Greedy Selection | Time Complexity: O(n log n) due to heap operations. |
| Priority Queue (Min Heap) | – |
| Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting and Marking | O(n log n) | O(n) | Best for clean implementation when sorting elements once and scanning is sufficient. |
| Priority Queue Greedy Selection | O(n log n) | O(n) | Useful when dynamically retrieving the smallest element without sorting the entire array first. |
Frequently asked questions
Is Find Score of an Array After Marking All Elements easy or hard?
The problem is rated Medium because the greedy insight is not immediately obvious. Once you realize the smallest unmarked element must always be selected first, the implementation becomes straightforward using sorting or a priority queue with O(n log n) complexity.
Find Score of an Array After Marking All Elements Python/Java solution
In Python, the solution often uses a list of (value, index) pairs sorted by value or the heapq module for a min heap. Java implementations typically use Arrays.sort for the sorted approach or a PriorityQueue for the heap-based greedy method. Both versions maintain a boolean array to mark visited indices.
How to solve Find Score of an Array After Marking All Elements in O(n)?
A strict O(n) solution generally is not feasible because the algorithm must repeatedly identify the smallest remaining value. That operation requires ordering, which leads to O(n log n) with sorting or a heap. Linear time would only be possible if the value range were small enough to use counting or bucket techniques.
What is the best approach for Find Score of an Array After Marking All Elements?
The most common solution uses a greedy strategy. Sort elements by value while keeping their indices, then iterate from smallest to largest and mark the element and its neighbors if the index is still unmarked. This guarantees the smallest available value is always chosen first and runs in O(n log n) time with O(n) extra space.
Is Find Score of an Array After Marking All Elements asked at Google/Amazon/Meta?
Problems combining greedy selection with heaps and array marking frequently appear in interviews at companies like Amazon, Google, and Meta. Variations that require selecting minimum elements while invalidating neighbors are common in system design and algorithm rounds.
What data structure is used in Find Score of an Array After Marking All Elements?
Typical implementations use arrays for marking visited indices and either sorting or a min heap (priority queue) to retrieve the smallest value efficiently. The heap approach maintains the minimum element dynamically, while sorting precomputes the order once.
What is the time complexity of Find Score of an Array After Marking All Elements?
The optimal solutions run in O(n log n) time. Sorting the array or maintaining a priority queue dominates the runtime, while marking neighbors takes constant time per element. Space complexity is O(n) for tracking which indices have already been marked.