Naive Approach
The first approach that we can think of is to directly simulate the process. Initially, each element is undeleted. Whenever a query of type 1 comes, we can mark the corresponding element as deleted. For a query of type 2, we can iterate over all the elements and pick the first undeleted integer greater than K. This approach will have O(NQ) time complexity.
C++ Code
#include<bits/stdc++.h>
using namespace std;
void solve(int N, int Q, vector<pair<int,int>> &queries){
// Vector to check if an element is deleted or not
vector<int> deleted(N + 1, 0);
// Iterating over queries
for (int i = 0; i < Q; i++){
// Marking the element as deleted for type 1 queries
if (queries[i].first == 1){
deleted[queries[i].second] = 1;
}
else{
int ans = -1;
// Iterating over all numbers from K to N
for(int j=queries[i].second; j<=N; j++){
// If the numbers not deleted, update the answer
if (deleted[j] == 0){
ans = j;
break;
}
}
// Printing the first undeleted integer from K to N.
cout<<ans<<' ';
}
}
cout<<endl;
}
// Driver Code
int main(){
int N = 5;
vector<pair<int,int>> queries{ {1, 3}, {2, 1}, {1, 2}, {2, 2}, {1, 4}, {2, 4} };
int Q = queries.size();
solve(N, Q, queries);
return 0;
}
You can also try this code with Online C++ Compiler
Output
1 4 5
You can also try this code with Online C++ Compiler
Complexity Analysis
Time Complexity
As for each query of type 2, we are iterating over the numbers from K to N. In the worst-case, K can be equal to 1 for every type 2 query, so the time complexity of the approach is O(N * Q).
Space Complexity
We have created an extra array ‘deleted’ of length O(N), so the space complexity of the approach is O(N).
Efficient Approach
Let’s visualize the problem to think of a better approach.
Consider the above example. Initially, we had 5 elements.
Now, after the first query, we have deleted 3. This means that now the answer for ‘K’=3 and ‘K’=4 will be the same, i.e., 4. We can think of it as a graph problem and combine 3 and 4 into a single group.
Similarly, when we delete 2, the answer for ‘K’=2 and ‘K’=3 will be the same, which will also be the same as ‘K’=4 due to the first operation. So we can combine 2, 3, and 4 in a single group.
We can see that in this problem, the answer for each group will be the same. This gives us the intuition to use Disjoint Set Union (Also, see Maximum Disjoint Intervals).
Initially, all elements form distinct disjoint sets. When a query of type {1, ‘K’} comes, we perform the Union operation on ‘K’ and ‘K’+1 such that the parent of ‘K’ is ‘K’+1. For a query of type 2, the answer will be the root of the set containing ‘K’.
Algorithm
- Create a vector ‘parent’ of length ‘N’+2.
- Initialize ‘parent[i]’ = i for every 1<=i<=N+1.
-
Now, iterate over the ‘queries’ array and do the following:
- If ‘queries[i].first’ = 1, perform union of ‘queries[i].second’, ‘queries[i].second’ + 1.
- Else, find the root of the set containing ‘queries[i].second’. If its value is equal to N+1, print -1, else, print the root.
C++ Code
#include<bits/stdc++.h>
using namespace std;
// Function to find root of the disjoint set
int Find(int node, vector<int>& parent) {
if (parent[node] != node){
parent[node] = Find(parent[node], parent);
}
return parent[node];
}
// Function to perform DSU union operation
void Union(int u, int v, vector<int>& parent){
u = Find(u, parent);
v = Find(v, parent);
// Updating parent of u
parent[u] = v;
}
void solve(int N, int Q, vector<pair<int,int>> &queries){
// Vector to store the parent of a node
vector<int> parent(N + 2);
// Initializing vector
for(int i=0; i<=N+1; i++){
parent[i] = i;
}
// Iterating over queries
for (int i = 0; i < Q; i++){
// Performing Union operation for type 1 queries
if (queries[i].first == 1){
Union(queries[i].second, queries[i].second + 1, parent);
}
else{
// Finding root of the given node
int root = Find(queries[i].second, parent);
// Printing the first undeleted integer from K to N.
if (root == N+1){
cout<<-1<<" ";
}
else{
cout<<root<<" ";
}
}
}
cout<<endl;
}
// Driver Code
int main(){
int N = 5;
vector<pair<int,int>> queries{ {1, 3}, {2, 1}, {1, 2}, {2, 2}, {1, 4}, {2, 4} };
int Q = queries.size();
solve(N, Q, queries);
return 0;
}
You can also try this code with Online C++ Compiler
Output
1 4 5
You can also try this code with Online C++ Compiler
Complexity Analysis
Time Complexity
We have implemented the following functions to implement DSU:
find(): This will take O(logN) time in the worst case for a single call.
union(): This function calls find() two times. Other operations take constant time. So overall complexity is O(logN) for a single call.
For type 1 queries, the union function is invoked, and for type 2 queries, the find function is called. So the time taken to find the first undeleted integer for each query is O(logN).
Total Time Complexity - O(Q * logN).
Space Complexity
We have created a new vector ‘parent’ of length O(N) for creating DSU and answering queries.
Total Space Complexity: O(N).
Frequently Asked Questions
What is a Disjoint Set data structure?
A disjoint set data structure allows us to keep track of a set of elements partitioned into disjoint sets. We can add new sets, merge two sets, and find the root of a set using this data structure.
Explain Find operation on Disjoint Set data structure.
The Find operation follows the parent pointers from the given node until we reach the root element.
Explain union operation on DSU?
The union of two nodes ‘x’ and ‘y’ replaces the set containing ‘x’ and the set containing ‘y’ with their union. First, we use two Find operations to get the roots of the sets containing ‘x’ and ‘y’. If both the roots are the same, we have to do nothing else merge both sets by either setting parent of ‘x’ to ‘y’ or by setting the parent of ‘y’ to ‘x.’
Conclusion
This article discussed how to find the first undeleted integer from ‘K’ to ‘N’ for ‘Q’ queries. We also discussed the time and space complexity of our solution. If you want to solve more such problems, you can visit Coding Ninjas Studio.
To practice more, you can check out the top problem lists:
If you think that this blog helped you share it with your friends!. To be more confident in data structures and algorithms, try out our DS and Algo Course. You can also check out some of the Guided Paths on topics such as Competitive Programming along with some of the Interview Experiences, Contests, and Interview Bundles only on Coding Ninjas Studio.
Until then, All the best for your future endeavors, and Keep Coding.
519+ registered 
