LeetCode 3080: Mark Elements on Array by Performing Queries Solution

Master LeetCode problem 3080 (Mark Elements on Array by Performing Queries), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3080. Mark Elements on Array by Performing Queries

Medium

Array Hash Table Sorting Heap (Priority Queue)Simulation

Problem Explanation

Explanation

To solve this problem, we can use a combination of a priority queue and a set. We will iterate through the queries and for each query, we will mark the element at the specified index and mark the smallest unmarked elements. We will keep track of the unmarked elements using a set and the smallest unmarked elements using a priority queue.

Algorithm:

Initialize a set to keep track of unmarked elements and a priority queue to store the smallest unmarked elements.
Iterate through the queries:
- Mark the element at the specified index if it is not already marked.
- Add the smallest unmarked elements to the priority queue.
- If the priority queue has more elements than required, remove the excess elements.
- Update the sum of unmarked elements.
- Add the marked element to the set.
Return the array containing the sum of unmarked elements after each query.

Time Complexity:

Each query operation involves adding and removing elements from the priority queue, which has a time complexity of O(log n) where n is the number of elements in the priority queue.
Overall time complexity is O(m * log n) where m is the number of queries.

Space Complexity:

The space complexity is O(n) to store the set and priority queue.

Solution Code

class Solution {
    public int[] markElements(int[] nums, int[][] queries) {
        int n = nums.length;
        Set<Integer> unmarked = new HashSet<>();
        PriorityQueue<Integer> smallestUnmarked = new PriorityQueue<>(Comparator.comparingInt(i -> nums[i]));

        for (int i = 0; i < n; i++) {
            unmarked.add(i);
        }

        int[] result = new int[queries.length];
        for (int j = 0; j < queries.length; j++) {
            int index = queries[j][0];
            int k = queries[j][1];

            if (unmarked.contains(index)) {
                unmarked.remove(index);
                smallestUnmarked.add(index);
            }

            while (smallestUnmarked.size() > k) {
                unmarked.add(smallestUnmarked.poll());
            }

            int sum = 0;
            for (int i : unmarked) {
                sum += nums[i];
            }
            result[j] = sum;
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3080 (Mark Elements on Array by Performing Queries)?

This page provides optimized solutions for LeetCode problem 3080 (Mark Elements on Array by Performing Queries) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3080 (Mark Elements on Array by Performing Queries)?

The time complexity for LeetCode 3080 (Mark Elements on Array by Performing Queries) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3080 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3080 in Java, C++, or Python.

Back to LeetCode Solutions