LeetCode 3080 - Mark Elements on Array by Performing Queries

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sorting, Heap (Priority Queue), Simulation

Solution

Here’s a fully detailed technical solution guide for LeetCode 3080 following your requested format.

Problem Understanding

The problem gives a zero-indexed array nums of size n consisting of positive integers and a 2D array queries of size m where each query is [indexi, ki]. All elements of nums are initially unmarked. Each query requires two operations in order: first, mark the element at indexi if it is not already marked, and second, mark ki unmarked elements that have the smallest values, breaking ties by the smallest index. After performing a query, we compute the sum of the unmarked elements and store it in an output array answer.

The expected output is an array of size m where answer[i] represents the sum of unmarked elements after the i-th query.

The constraints indicate that n and m can each be up to 100,000, and each element in nums is a positive integer up to 100,000. This tells us that a naive solution that repeatedly scans the entire array to find the smallest unmarked elements per query would be too slow, as it could result in O(n * m) operations, which is potentially 10^10 and exceeds practical limits.

Important edge cases include scenarios where ki is larger than the number of remaining unmarked elements, or where multiple elements share the same value and the tie-breaking rule of smallest index must be respected.

Approaches

The brute-force approach is straightforward: for each query, mark the element at indexi and then iterate over the remaining unmarked elements to find the ki smallest values, marking them and recomputing the sum of unmarked elements after each query. While this approach is correct, it is inefficient because locating the smallest unmarked elements repeatedly requires scanning the array, which is O(n) per query. With up to 10^5 queries, this results in an O(n * m) runtime, which is too slow.

A more efficient solution leverages sorting and prefix sums. First, we sort the elements of nums along with their indices. By maintaining a priority queue or a sorted list of unmarked elements, we can quickly select the smallest unmarked elements for each query. Marking and updating sums can be performed in O(log n) per element if a heap or a balanced tree is used. The main insight is that marking the ki smallest unmarked elements can be efficiently tracked using sorting or a min-heap, rather than rescanning the entire array each time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n)	O(n)	Scan the array for `ki` smallest unmarked elements per query
Optimal	O(n log n + m log n)	O(n)	Use sorting and a min-heap or ordered set to efficiently mark smallest elements

Algorithm Walkthrough

Initialization: Start by storing each element with its index in a list of tuples (value, index). Sort this list by value first, then by index to satisfy the tie-breaking rule.
Tracking Marks: Initialize a boolean array marked of size n to keep track of which elements are marked.
Sum Calculation: Maintain a variable total_sum representing the sum of unmarked elements, initially the sum of all elements in nums.
Pointer for Smallest Unmarked Elements: Use a pointer or index ptr to traverse the sorted list of (value, index). This pointer keeps track of the next smallest unmarked element.
Processing Queries: For each query [indexi, ki]:
If nums[indexi] is unmarked, mark it and subtract its value from total_sum.
Starting from ptr, mark the next ki unmarked elements by moving the pointer forward until ki elements are marked or the end of the list is reached. For each marked element, update total_sum.
Append the updated total_sum to the answer array.
Return the Result: After all queries are processed, return the answer array.

Why it works: The sorted list ensures that we always consider the smallest unmarked elements in order, and the pointer ensures we do not revisit elements that are already marked. Maintaining the sum incrementally avoids recomputing sums repeatedly, keeping the algorithm efficient.

Python Solution

from typing import List

class Solution:
    def unmarkedSumArray(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n = len(nums)
        # Pair each element with its index and sort by value, then by index
        sorted_nums = sorted((num, i) for i, num in enumerate(nums))
        
        marked = [False] * n
        total_sum = sum(nums)
        answer = []
        ptr = 0  # Pointer for smallest unmarked elements in sorted_nums
        
        for indexi, ki in queries:
            # Mark the indexi element if not already marked
            if not marked[indexi]:
                marked[indexi] = True
                total_sum -= nums[indexi]
            
            # Mark the next ki smallest unmarked elements
            count = 0
            while ptr < n and count < ki:
                val, idx = sorted_nums[ptr]
                if not marked[idx]:
                    marked[idx] = True
                    total_sum -= val
                    count += 1
                ptr += 1
            
            answer.append(total_sum)
        
        return answer

This implementation directly follows the algorithm walkthrough. The sorted list ensures we always select the smallest unmarked elements efficiently. The pointer ptr prevents scanning previously processed elements. Using total_sum allows O(1) updates for the sum of unmarked elements.

Go Solution

package main

func unmarkedSumArray(nums []int, queries [][]int) []int64 {
    n := len(nums)
    type pair struct {
        val int
        idx int
    }
    
    sortedNums := make([]pair, n)
    totalSum := int64(0)
    for i, v := range nums {
        sortedNums[i] = pair{v, i}
        totalSum += int64(v)
    }
    
    // Sort by value, then by index
    sort.Slice(sortedNums, func(i, j int) bool {
        if sortedNums[i].val == sortedNums[j].val {
            return sortedNums[i].idx < sortedNums[j].idx
        }
        return sortedNums[i].val < sortedNums[j].val
    })
    
    marked := make([]bool, n)
    answer := make([]int64, 0, len(queries))
    ptr := 0
    
    for _, q := range queries {
        indexi, ki := q[0], q[1]
        if !marked[indexi] {
            marked[indexi] = true
            totalSum -= int64(nums[indexi])
        }
        
        count := 0
        for ptr < n && count < ki {
            val, idx := sortedNums[ptr].val, sortedNums[ptr].idx
            if !marked[idx] {
                marked[idx] = true
                totalSum -= int64(val)
                count++
            }
            ptr++
        }
        
        answer = append(answer, totalSum)
    }
    
    return answer
}

Go-specific notes: int64 is used for sums to avoid integer overflow. sort.Slice is used for sorting with a custom comparator. The slice marked tracks element marking, and the pointer logic mirrors the Python version.

Worked Examples

Example 1: nums = [1,2,2,1,2,3,1], queries = [[1,2],[3,3],[4,2]]

Step by step:

Query	Mark indexi	Mark smallest ki	Total sum
[1,2]	Mark index 1 (value 2)	Mark 2 smallest unmarked: indices 0 (1) and 3 (1)	8
[3,3]	Already marked	Mark next 3 smallest unmarked: indices 6 (1), 2 (2), 4 (2)	3
[4,2]	Already marked	Mark next 2 smallest unmarked: index 5 (3)	0

Example 2: nums = [1,4,2,3], queries = [[0,1]]

Query	Mark indexi	Mark smallest ki	Total sum
[0,1]	Mark index 0 (value 1)	Mark next smallest unmarked: index 2 (2)	7

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n + m log n)	Sorting takes O(n log n), each query may mark up to ki elements using pointer traversal, overall pointer advances at most n times
Space	O(n)	Array for marks, sorted list, and answer array

Sorting dominates initial cost; the pointer ensures each element is only considered once, leading to an efficient traversal during queries.

Test Cases

# Provided examples
assert Solution().unmarkedSumArray([1,2,2,1,2,3,1], [[1,2],[3,