Mark Elements on Array by Performing Queries

Medium

Samsung

0 views

Topics:

ArraysGreedy Algorithms

You are given a 0-indexed array nums of size n consisting of positive integers.

You are also given a 2D array queries of size m where queries[i] = [index_i, k_i].

Initially all elements of the array are unmarked.

You need to apply m queries on the array in order, where on the i^th query you do the following:

Mark the element at index index_i if it is not already marked.
Then mark k_i unmarked elements in the array with the smallest values. If multiple such elements exist, mark the ones with the smallest indices. And if less than k_i unmarked elements exist, then mark all of them.

Return an array answer of size m where answer[i] is the sum of unmarked elements in the array after the i^th query.

Example 1:

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

Output: [8,3,0]

Explanation:

We do the following queries on the array:

Mark the element at index 1, and 2 of the smallest unmarked elements with the smallest indices if they exist, the marked elements now are nums = [1,2,2,1,2,3,1]. The sum of unmarked elements is 2 + 2 + 3 + 1 = 8.
Mark the element at index 3, since it is already marked we skip it. Then we mark 3 of the smallest unmarked elements with the smallest indices, the marked elements now are nums = [1,2,2,1,2,3,1]. The sum of unmarked elements is 3.
Mark the element at index 4, since it is already marked we skip it. Then we mark 2 of the smallest unmarked elements with the smallest indices if they exist, the marked elements now are nums = [1,2,2,1,2,3,1]. The sum of unmarked elements is 0.

Example 2:

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

Output: [7]

Explanation: We do one query which is mark the element at index 0 and mark the smallest element among unmarked elements. The marked elements will be nums = [1,4,2,3], and the sum of unmarked elements is 4 + 3 = 7.

Constraints:

n == nums.length
m == queries.length
1 <= m <= n <= 10⁵
1 <= nums[i] <= 10⁵
queries[i].length == 2
0 <= index_i, k_i <= n - 1

Mark Elements on Array by Performing Queries

Medium

Samsung

0 views

Topics:

ArraysGreedy Algorithms

You are given a 0-indexed array nums of size n consisting of positive integers.

You are also given a 2D array queries of size m where queries[i] = [index_i, k_i].

Initially all elements of the array are unmarked.

You need to apply m queries on the array in order, where on the i^th query you do the following:

Mark the element at index index_i if it is not already marked.
Then mark k_i unmarked elements in the array with the smallest values. If multiple such elements exist, mark the ones with the smallest indices. And if less than k_i unmarked elements exist, then mark all of them.

Return an array answer of size m where answer[i] is the sum of unmarked elements in the array after the i^th query.

Example 1:

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

Output: [8,3,0]

Explanation:

We do the following queries on the array:

Mark the element at index 1, and 2 of the smallest unmarked elements with the smallest indices if they exist, the marked elements now are nums = [1,2,2,1,2,3,1]. The sum of unmarked elements is 2 + 2 + 3 + 1 = 8.
Mark the element at index 3, since it is already marked we skip it. Then we mark 3 of the smallest unmarked elements with the smallest indices, the marked elements now are nums = [1,2,2,1,2,3,1]. The sum of unmarked elements is 3.
Mark the element at index 4, since it is already marked we skip it. Then we mark 2 of the smallest unmarked elements with the smallest indices if they exist, the marked elements now are nums = [1,2,2,1,2,3,1]. The sum of unmarked elements is 0.

Example 2:

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

Output: [7]

Explanation: We do one query which is mark the element at index 0 and mark the smallest element among unmarked elements. The marked elements will be nums = [1,4,2,3], and the sum of unmarked elements is 4 + 3 = 7.

Constraints:

n == nums.length
m == queries.length
1 <= m <= n <= 10⁵
1 <= nums[i] <= 10⁵
queries[i].length == 2
0 <= index_i, k_i <= n - 1

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `nums` and `queries` arrays, and what is the range of values within those arrays?
Can the `nums` array contain negative numbers, zero, or floating-point numbers?
If the same index appears multiple times in `queries`, should only the first matching query mark the element, or should all matching queries mark the element (effectively making it marked if at least one matches)?
What should I return if the `nums` or `queries` array is null or empty?
Is the index in `queries` guaranteed to be within the bounds of the `nums` array?

Brute Force Solution

Approach

Imagine you have a list of light switches and a set of instructions to flip certain switches on or off multiple times. The brute force method involves directly following each instruction, one at a time, in the order they are given, to see which switches end up on.

Here's how the algorithm would work step-by-step:

Start with all the light switches in the off position.
Take the first instruction from the set of instructions.
Go through the entire list of light switches and if the instruction tells you to flip a specific switch, then flip it (on becomes off and off becomes on).
Once you've applied that instruction to every switch in the list, move on to the next instruction.
Repeat this process, instruction by instruction, until you have followed all instructions.
At the end, the switches that are left in the on position are the ones that get marked.

Code Implementation

def mark_elements_brute_force(array_length, queries):
    # Initialize all elements to 'off' (False).
    element_marks = [False] * array_length

    # Iterate through each query.
    for query in queries:
        # Iterate through each element in the array.
        for index in range(array_length):
            # If the index is within the query range, flip the state.
            if query[0] <= index <= query[1]:

                element_marks[index] = not element_marks[index]

    # Collect indices with elements marked 'on' (True)
    marked_indices = [index for index, marked in enumerate(element_marks) if marked]

    return marked_indices

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through an array of n elements for each of m queries. Applying the first query requires examining each of the n elements in the array and potentially flipping its state. This process is repeated for each of the m queries. Therefore, the total number of operations is proportional to the product of n and m, resulting in a time complexity of O(n*m).

Space Complexity

O(1) – The provided solution operates directly on the input array of light switches and instructions. It doesn't create any auxiliary data structures like temporary arrays, hash maps, or recursion call stacks. The only extra memory used is for a few counter variables to iterate through the light switches and instructions, which takes up constant space regardless of the number of light switches or instructions. Thus, the space complexity is O(1).

Optimal Solution

Approach

The best way to solve this problem is to keep track of which parts of the collection have been marked. We'll use a special technique that allows us to efficiently update large sections at once, instead of checking each spot individually. This speeds up the entire process considerably.

Here's how the algorithm would work step-by-step:

First, imagine a separate, much smaller structure that helps us keep track of changes to large segments of our collection.
When we get a request to mark some elements, we check if we can directly update the corresponding segment in our structure.
If the segment is completely unmarked or completely marked already, we just update the entire segment at once.
However, if the segment is partially marked, we break it down into smaller pieces and update only the parts that need changing. This is lazy propagation.
This way, we only do actual marking on the smallest sections necessary and postpone doing work until we absolutely have to. This strategy reduces the total number of operations needed.
As we process more requests, the segments become more refined, giving us greater efficiency.
Finally, we can read the marked status of any element in our collection by traversing the segments from our smaller structure that overlap with the element's position. This will give us the final answer.

Code Implementation

class Segment:
    def __init__(self, start_index, end_index, marked_status):
        self.start_index = start_index
        self.end_index = end_index
        self.marked_status = marked_status

def mark_elements(array_length, queries):
    segments = [Segment(0, array_length - 1, False)]
    
    for start_index, end_index in queries:
        new_segments = []
        for segment in segments:
            # If the segment is outside the query range, keep it as is.
            if segment.end_index < start_index or segment.start_index > end_index:
                new_segments.append(segment)
                continue
            
            # If the segment is fully contained, update the marked status.
            if start_index <= segment.start_index and segment.end_index <= end_index:
                new_segments.append(Segment(segment.start_index, segment.end_index, True))
                continue

            # This handles partial overlaps.  We need to split the segment.
            if segment.start_index < start_index:
                new_segments.append(Segment(segment.start_index, start_index - 1, segment.marked_status))

            if end_index < segment.end_index:
                new_segments.append(Segment(end_index + 1, segment.end_index, segment.marked_status))

            # Mark the overlapping portion as true.
            new_start = max(segment.start_index, start_index)
            new_end = min(segment.end_index, end_index)
            new_segments.append(Segment(new_start, new_end, True))
        
        segments = new_segments
    
    marked_array = [False] * array_length
    
    # Build the final marked array by querying the segments.
    for i in range(array_length):
        for segment in segments:
            if segment.start_index <= i <= segment.end_index:
                marked_array[i] = segment.marked_status
                break
                
    return marked_array

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(q log n) – The solution employs a segment tree (or similar structure) to efficiently perform range updates. Each query to mark elements involves traversing the tree, which takes logarithmic time, O(log n), where n is the size of the array. Because we perform this traversal for each of the 'q' queries, the overall time complexity becomes O(q log n). Lazy propagation optimizes updates by postponing operations, but does not change the fundamental logarithmic nature of segment tree operations.

Space Complexity

O(N) – The space complexity is dominated by the "smaller structure" that tracks changes to segments of the collection, and represents the marked status of sections of the original array. In the worst-case scenario, this structure, which implements lazy propagation, might require storing information for each element if updates are highly fragmented. Thus, the auxiliary space needed scales linearly with the size of the input collection, which we denote as N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
nums is null or empty	Return 0, as there are no elements to mark.
queries is null or empty	Return 0, as no queries can mark elements.
nums array contains duplicate values but only one query matches a duplicate value's index.	The solution should correctly mark only the element at the specified index when the query matches.
Queries contain duplicate index-value pairs.	The solution should process each query, but subsequent identical queries should not affect the marked status if the element at that index is already marked.
Queries contain the same index but different values; only the last matching query should matter.	The solution should ensure that the last query that matches index and value determines whether the element is marked.
nums array contains negative numbers and queries use negative values	The solution should handle negative numbers without issues.
Index in queries array is out of bounds (less than 0 or greater than or equal to nums.length)	The solution should skip queries with out-of-bounds indexes, or treat them as invalid without crashing.
Large input array and large number of queries to test efficiency.	The solution should iterate through the queries in O(m) time (where m is the number of queries), and marking the array elements should be O(1) lookup which achieves reasonable performance.