Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Naive Approach
3.1.
C++ Code
3.2.
Complexity Analysis
4.
Efficient Approach
4.1.
Algorithm
4.2.
C++ Code
4.3.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is a Disjoint Set data structure?
5.2.
Explain Find operation on Disjoint Set data structure.
5.3.
Explain union operation on DSU?
6.
Conclusion
Last Updated: Mar 27, 2024
Hard

Find First Undeleted Integer From K to N in Given Unconnected Graph After Performing Q Queries.

Author Jaglike Makkar
3 upvotes
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Graphs are one of the most popular Data Structures along with one of the most complicated ones. However, it isn't all that tough once you get used to how things work as long as you are clear on the basics the rest of it is just a piece of cake. In this article, we are going to discuss one of the popular graph problems and how to approach its solution.

Problem Statement

Initially, we will be given ‘N’ integers from 1 to ‘N’. Now we have to perform ‘Q’ queries. Each query is one of the following two types:

  • {1, ‘K’} = Delete ‘K’ from the given set of integers.
  • {2, ‘K’} = Find the first undeleted integer from ‘K’ to ‘N’ from the given set of integers.

Note: If there is no undeleted integer from ‘K’ to ‘N’, print -1.

Now let’s understand the problem with an example 

Given: N = 5 and Q = [ {1, 3}, {2, 1}, {1, 2}, {2, 2}, {1, 4}, {2, 4} ].

Output: 1 4 5

Explanation:

  • Initially we have 5 integers - 1,2,3,4,5.
  • After the first query, 3 is deleted. So we are left with 4 integers - 1,2,4,5.
  • For the second query, we need to find the first undeleted integer from 1 to 5. So, the answer to this query is 1 itself, as it is not deleted.
  • After the third query, 2 is deleted. Now we are left with 3 integers - 1,4,5.
  • For the fourth query, we have to find the first undeleted integer from 2 to 5. 2 and 3 have already been deleted. So the answer to this query is 4.
  • After the fifth query, 4 is deleted. Now we are left with 2 integers - 1,5.
  • For the last query, the first undeleted integer from 4 to 5 is 5.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

Output

1 4 5

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.

example illustration

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.

example illustration

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.

example illustration

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

  1. Create a vector ‘parent’ of length ‘N’+2.
  2. Initialize ‘parent[i]’ = i for every 1<=i<=N+1.
  3. Now, iterate over the ‘queries’ array and do the following:
    1. If ‘queries[i].first’ = 1, perform union of ‘queries[i].second’, ‘queries[i].second’ + 1.
    2. 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;
}

Output

1 4 5

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.

Live masterclass