Problem Link - Stable Quick Sort Practice Problem in Jump from 2* to 3*
Problem Statement:
You are given a collection of n pairs, where each pair contains two integers. The task is to write a function that selects the indices (0-based) of pairs based on the uniqueness of the first element of each pair. The output should be a list of indices such that the first element of each selected pair is unique, maintaining the original order of the pairs.
Approach:
To solve this problem, we need to ensure that for each unique first element in the pairs, we only select the first occurrence of it and store the index. Here’s a step-by-step breakdown of the approach:
Tracking Unique Elements:
- Initialize a
set: Create a set to store the first elements of the pairs as they are encountered. This ensures that only unique elements are tracked. - Create a
candidatescontainer: Initialize a container (e.g., a list or array) to store the indices of the pairs whose first elements are unique. - Iterate through the array of pairs:
- For each pair, check if the first element is not present in the set.
- If the element is unique (i.e., not found in the set):
- Append the current index of the pair to the
candidatescontainer. - Insert the first element into the set to mark it as seen.
- Append the current index of the pair to the
Return the candidates container: After the iteration, return the container holding the indices of the selected pairs.
Complexity:
- Time Complexity:
O(n), wherenis the number of pairs. This is because we are iterating over the array once and performing insert and find operations on a set, which takesO(1)on average due to hash set operations. - Space Complexity:
O(n)in the worst case, due to storing unique elements and indices.