Find Score of an Array After Marking All Elements

Find Score of an Array After Marking All Elements - 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,1,3,4,5,2]

› Output: 7

💡 Note: Choose 1 (smallest), mark indices 0,1,2 → score=1. Choose 2 (at index 5), mark indices 4,5 → score=3. Choose 4 (at index 3), mark index 3 → score=7. All elements marked.

Example 2 — All Same Values

$ Input: nums = [2,2,2,2]

› Output: 4

💡 Note: Choose first 2 (index 0), mark indices 0,1 → score=2. Choose 2 (index 2), mark indices 1,2,3 → score=4. All marked.

Example 3 — Single Element

$ Input: nums = [5]

› Output: 5

💡 Note: Only one element, choose it → score=5.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array of positive integers

Process

Repeatedly choose smallest unmarked, mark neighbors

Output

Sum of all chosen elements

Key Takeaway

🎯 Key Insight: Always choose the globally smallest unmarked element to maximize score

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to always choose the globally smallest unmarked element, not just locally optimal choices. The best approach is sorting first with O(n log n) time and O(n) space, which cleanly separates the sorting logic from the marking simulation.

Common Approaches

Approach	Time	Space	Notes
✓ Priority Queue with Index Tracking	O(n log n)	O(n)	Use a min-heap to efficiently get the smallest unmarked element
Brute Force Simulation	O(n²)	O(n)	Simulate the algorithm by repeatedly finding the smallest unmarked element
Sort with Index Tracking	O(n log n)	O(n)	Sort elements by value while keeping track of original indices

Priority Queue with Index Tracking — Algorithm Steps

Step 1: Create min-heap with (value, index) pairs
Step 2: Pop from heap until finding unmarked element
Step 3: Add to score and mark element with neighbors
Step 4: Continue until heap is empty and all marked

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Heap

Create min-heap with all (value, index) pairs

Pop Min

Extract minimum that's not marked

Mark & Continue

Mark neighbors and repeat

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int value;
    int index;
} Item;

typedef struct {
    Item* items;
    int size;
    int capacity;
} MinHeap;

MinHeap* createHeap(int capacity) {
    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));
    heap->items = (Item*)malloc(capacity * sizeof(Item));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void heapifyUp(MinHeap* heap, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap->items[parent].value <= heap->items[index].value) break;
        
        Item temp = heap->items[parent];
        heap->items[parent] = heap->items[index];
        heap->items[index] = temp;
        index = parent;
    }
}

void heapifyDown(MinHeap* heap, int index) {
    while (2 * index + 1 < heap->size) {
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;
        int smallest = index;
        
        if (heap->items[leftChild].value < heap->items[smallest].value) smallest = leftChild;
        if (rightChild < heap->size && heap->items[rightChild].value < heap->items[smallest].value) smallest = rightChild;
        
        if (smallest == index) break;
        
        Item temp = heap->items[index];
        heap->items[index] = heap->items[smallest];
        heap->items[smallest] = temp;
        index = smallest;
    }
}

void push(MinHeap* heap, int value, int index) {
    heap->items[heap->size].value = value;
    heap->items[heap->size].index = index;
    heapifyUp(heap, heap->size);
    heap->size++;
}

Item pop(MinHeap* heap) {
    Item root = heap->items[0];
    heap->size--;
    heap->items[0] = heap->items[heap->size];
    heapifyDown(heap, 0);
    return root;
}

int solution(int* nums, int n) {
    bool* marked = (bool*)calloc(n, sizeof(bool));
    int score = 0;
    
    // Create min-heap
    MinHeap* heap = createHeap(n);
    for (int i = 0; i < n; i++) {
        push(heap, nums[i], i);
    }
    
    while (heap->size > 0) {
        // Pop until we find an unmarked element
        Item item;
        bool found = false;
        while (heap->size > 0) {
            item = pop(heap);
            if (!marked[item.index]) {
                found = true;
                break;
            }
        }
        
        if (!found) break;
        
        // Add to score
        score += item.value;
        
        // Mark the element and its neighbors
        int start = (item.index - 1 < 0) ? 0 : item.index - 1;
        int end = (item.index + 2 > n) ? n : item.index + 2;
        for (int j = start; j < end; j++) {
            marked[j] = true;
        }
    }
    
    free(marked);
    free(heap->items);
    free(heap);
    return score;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Heap operations take O(log n) and we process each element once

⚡ Linearithmic

Space Complexity

O(n)

Heap stores all elements plus marked array

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

450 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Priority Queue with Index Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler