Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Problem
2.
Naive Approach
2.1.
C++ Code
2.2.
Output
2.3.
Time Complexity = O(N * Q)
2.4.
Space Complexity = O(N + M)
3.
Efficient Approach
3.1.
Algorithm
3.2.
C++ Code
3.3.
Output:
3.4.
Time Complexity:
3.5.
Space Complexity: 
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Maximum element in the connected component of the given node for Q queries

Author Jaglike Makkar
3 upvotes
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Problem

Given an integer ‘N’ denoting the number of nodes in the graph, an array of pairs ‘arr’ of length ‘M’, denoting an edge and another array ‘queries’ of length ‘Q’, find the maximum element in the connected component of the node having a value equal to ‘queries[i]’ for every 1<=i<=Q.

In other words, we are given edges of a graph, and we are required to find the maximum element in the connected component of the given node. 

Example -

Input: ‘arr’ = [ {1, 2}, {2, 4}, {3, 5} ] and ‘queries’ = [3, 2, 4]. 

Output: 5 4 4
 

For the first query - ‘queries[0]’, the given node is 3. We can see that the connected component of 3 consists of only two nodes - 3 and 5. Since we need the maximum element in the connected component, so the answer for the first query is 5.

For the second query - ‘queries[1]’, the given node is 2. The connected component of 2 has three nodes - 1,2,4. So, the maximum element in the connected component of 2, and the answer for the second query is 4.

Similarly, for the third query - ‘queries[2]’, the given node is 4. The maximum element in the connected component of 4 is 4 itself.

Naive Approach

One simple approach to solving this problem is to do dfs/bfs for each query and keep track of the maximum element. To implement this, we can first create an adjacency list from the given edges. For every query, initialize ‘ans’ = 0. Then we can perform DFS Algorithm and update ‘ans’ as ‘ans’ = max(‘ans’, ‘node’) for every node we visit. After this, ‘ans’ will have a value equal to the maximum element in the connected component.

C++ Code

#include<bits/stdc++.h>
using namespace std;

void solve(int N, int M, int Q, vector<pair<int,int>>& arr, vector<int> &queries){

    // Creating Adjacency List
    vector<vector<int>> adj(N+1);
    for(int i=0; i<M; i++){
        int u = arr[i].first;
        int v = arr[i].second;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Iterating over all queries
    for(int i=0; i<Q; i++){
        int node = queries[i];

        // Doing DFS for each query
        vector<int>stack;
        vector<int>vis(N+1,0);
        vis[node]=1;
        stack.push_back(node);
        int ans = 0;
        while (stack.size()){
            int u = stack.back();
          
            // Updating answer as max(answer, current node)
            ans = max(ans,u);
            stack.pop_back();
            for (int v: adj[u]){
                if (vis[v]==0){
                    vis[v]=1;
                    stack.push_back(v);
                }
            }
        }

        // Printing the maximum element of the connected component
        cout<<ans<<' ';
    }
    cout<<endl;
}

// Driver Code
int main(){
    int N = 5;
    vector<pair<int,int>>arr { {1,2}, {2,4}, {3,5} };
    vector<int> queries{ 3, 2, 4 };
    int M = arr.size();
    int Q = queries.size();

    solve(N, M, Q, arr, queries);
    return 0;
}

 

Output

5 4 4

Time Complexity = O(N * Q)

For every query, we are performing DFS to get the maximum element of the connected component. In the worst case, the entire graph can be connected, so, a single DFS will have O(N) complexity. Therefore the total time complexity for Q queries is O(N * Q).

Space Complexity = O(N + M)

First, we are creating an adjacency list from the given edges. For M edges and N nodes, the adjacency list will have O(N + M) space complexity. 

For every query, we are creating stack and visited array of length O(N). So the total space complexity of the approach is O(N + M).

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

Efficient Approach

Now let’s see if we can figure out any better approach. One thing to notice in this question is that the answer will be the same for every element of a connected component (equal to the maximum element in the connected component). Therefore, we can combine the nodes of a component into a single group. This can be done using Disjoint Set Union

Initially, all the elements form different disjoint sets. Now we iterate over ‘arr’ and perform the DSU union operation on the elements of the given edge and simultaneously maintain the ‘maxElement’ for each set. After creating the data structure, for each query, perform a find operation to get the parent ‘currentParent’ of that set, and ‘maxElement[currentParent]’ will be the required answer.

Algorithm

  • Create 3 vectors - ‘parent’, ‘rank’, ‘maxElement’.
  • Initialize ‘parent[i]’=i and ‘maxElement[i]’=i for 1<=i<=N.
  • Iterate over the array and perform union operation of ‘arr[i].first’, ‘arr[i].second’.
  • Now for every query:
    • Find parent of the node ‘queries[i]’.
    • Output the value of ‘maxElement[currentParent]’.

C++ Code

#include<bits/stdc++.h>
using namespace std;

// Function to find root of the disjoint set
int Find(vector<int>& parent, int node) {
    if (parent[node] == node){
        return parent[node];
    }
    else{
        parent[node] = Find(parent, parent[node]);
        return parent[node];
    }
}

// Function to perform DSU union operation
void Union(int u, int v, vector<int>& parent, vector<int>& rank, vector<int>& maxElement){
 
    u = Find(parent, u);
    v = Find(parent, v);
 
    // if both elements are already in the same set
    if (u == v)
        return;
 
    // If the ranks are the same
    if (rank[u] == rank[v]) {
        rank[u]++;
    }

    // if the rank of u is less, swap u and v
    if (rank[u] < rank[v]) {
        swap(u,v);
    }
  
    // Updating parent of v
    parent[v] = u;
  
    // Updating maxElement
    maxElement[u] = max(maxElement[u],
                      maxElement[v]);
}

void solve(int N, int M, int Q, vector<pair<int,int>>& arr, vector<int> &queries){

    // Vector to store the parent of a node
    vector<int> parent(N + 1);
 
    // Vector to store rank of a node for DSU
    vector<int> rank(N + 1, 0);
 
    // Vector to store maximum element of a set
    vector<int> maxElement(N + 1);

    // Initializing vectors
    for(int i=0; i<=N; i++){
        parent[i] = i;
        maxElement[i] = i;
    }

    // Iterating over arr and performing union operation
    for (int i = 0; i < M; i++) {
        Union(arr[i].first, arr[i].second, parent, rank, maxElement);
    }

    // Iterating over queries
    for (int i = 0; i < Q; i++){
      
        // Finding parent of the given node
        int currentParent = Find(parent, queries[i]);

        // Printing max element of the set
        cout<<maxElement[currentParent]<<" ";
    }
    cout<<endl;
}

// Driver Code
int main(){
    int N = 5;
    vector<pair<int,int>>arr { {1,2}, {2,4}, {3,5} };
    vector<int> queries{ 3, 2, 4 };
    int M = arr.size();
    int Q = queries.size();

    solve(N, M, Q, arr, queries);
    return 0;
}

 

Output:

5 4 4

 

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.

Union operation is performed once for each edge, so the total time complexity of creating DSU is O(MlogN). Further, there are Q queries and for each query, the find operation is performed once. Therefore the time complexity for answering the queries in O(QlogN).

Total Time Complexity: max(MlogN, QlogN).

Space Complexity

We have created 3 new vectors of length O(N) for creating DSU and answering queries. 

Total Space Complexity: O(N).

FAQs

  1. 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 parent of a set using this data structure.
     
  2. Explain Find operation on Disjoint Set data structure.
    The Find operation is performed by following the parent pointers from the given node until we reach the root element.
     
  3. Explain union operation on DSU?
    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 parent of ‘y’ to ‘x’.

Key Takeaways

In this article, we discussed how to find the maximum element in the connected component of a node 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.

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.

Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Find k-cores of an Undirected Graph
Next article
Find the number of connected grids of a given size in a 2D-Matrix
Live masterclass