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.
Approach
4.
Code in C++
4.1.
Time Complexity
4.2.
Space Complexity
5.
Frequently Asked Questions
6.
Key Takeaways
Last Updated: Mar 27, 2024

Count the number of nodes in a Graph whose sum of neighbors is at most K

Author SHIKHAR SONI
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

This article aims to help you apply graph traversal (learn about the essential graph traversal algorithms here) and use it to solve problems that you may commonly encounter in interviews or coding tests. We also cover the approach and C++ implementation and discuss improvements and references to sources that can help you learn more about related topics.

Problem Statement

The problem is to count the number of nodes whose neighbours have a sum of at most K in a graph. Refer to the below example to see the input and understand how the answer varies depending on it.

As an example, refer to the below graph.

Input:

K = 5

Output:

3

Explanation:

Neighbours of node having value 1 are 2,4 and 5. The sum is 9 (9 > 5, so not added to the answer count).

Neighbours of node having value 2 is 1. The sum is 1 (1 <= 5, so added to the answer count).

Neighbours of node having value 3 are 4 and 5.

Neighbours of node values 4 and 5 are 1 and 3. The sum is 4 (4 <= 5).

There are only three nodes: {4,5,2} with a neighbour sum of less than or equal to 4, the count is 3, and that's the answer.

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

Approach

Our idea for solving the problem is to traverse the graph using DFS Algorithm and count the sum of the neighbours' values. We compare and ensure that the sum doesn't exceed K and increase the answer count depending on it being less than or equal to K.

Our algorithm below follows the following steps:

  1. Initialize and build the input graph.
  2. Use DFS to visit every node and record the visited nodes in the unordered_set.
  3. Return if the node was previously visited.
  4. Calculate the sum of values of the neighbouring nodes and recurse through the whole graph, as in DFS.
  5. If the sum is less than equal to K, increment the answer by one and return it.

Code in C++

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;


/*
    uncomment if you need to use long long for testing instead of int
*/
// #define int long long


class Node{
    public:
    vector<Node *> neigh;
    int val;
    Node(int x){
        val = x;
    }
    void insert(Node *x){
        neigh.push_back(x);
    }
};


int countNodesWithNeighborSumNotMoreThanK(Node* start, unordered_set<Node *>& vis, int K){
    
    // if node already visited, return back
    if(vis.find(start) != vis.end()) return 0;
    
    vis.insert(start);
    
    int sum = 0, ans = 0;
    
    for(int i = 0; i < start->neigh.size(); i++){
        ans += countNodesWithNeighborSumNotMoreThanK(start->neigh[i], vis, K);
        sum += start->neigh[i]->val;
    }


    if(sum <= K) ans += 1;
    
    return ans;
}


int32_t main(){
    // edit the data and check the output for various graphs
    // list of node values
    vector<int> a = {1, 2, 3, 4, 5};
    vector<Node *> v;
    for(int x: a){
        v.push_back(new Node(x));
    }
    // adjacency list for neighbors
    vector<vector<int>> neighbors = {
        {1, 3, 4},
        {0},
        {3, 4},
        {0, 2},
        {0, 2}
    };
    // K value for the problem
    int K = 4;
    for(int i = 0; i < neighbors.size(); i++){
        for(int j: neighbors[i]){
            v[i]->insert(v[j]);
        }
    }
    unordered_set<Node *> vis;
    cout << countNodesWithNeighborSumNotMoreThanK(v[0], vis, K);
}

Output

3

Time Complexity

Time Complexity for the given algorithm is O(V + E), here V are the number of nodes, and E are the edges in the graph. This time complexity is identical to DFS as that's essentially all that's happening in the code.

Space Complexity

Extra space O(V + h) other than the input is required by the algorithm, O(V) space is required by unordered_set for storing the visited positions, here h is the stack depth at max. h can at maximum be V (number of nodes), so the worst-case space complexity of the algorithm is O(V). This happens when we have a chain-like graph, as shown below. If 1 is the start node, then the stack depth at max will be V.

Check out this problem - Pair Sum In Array.

Frequently Asked Questions

1. Why did we prefer to use DFS, and can we use BFS instead?

One can easily do the same problem using BFS, and I recommend you to try the problem using BFS and observe the difference. Observe the difference in memory consumed for different graphs with the same algorithms. This observation will give you a better idea of which algorithm performs better in which type of graph.

2. Difference between unordered_set and set in C++ STL?

The set data structure is usually implemented using a red-black tree (read more about it here). The unordered_set, however, is implemented using a hash table and hence offers an average O(1) retrieval and insertion. In contrast, set data structure takes O(log(n)) for retrieving and inserting an element.

3. Is unordered_set always better than set?

No, the unordered_set will usually work well with random data and give O(1) retrieval and insertion on average. Still, in case of excessive collisions (which can be the case for some specific inputs, depending on the hash function), our retrieval and insertion may become O(N).

Key Takeaways

The article helps us understand applications of graph traversals algorithms such as DFS, understanding and approaching related problems and implementing them. Go through the basics of graph theory here to better understand and follow the blog and read a bit about Graph Traversal Algorithms here and recursion here.

Learn more about the C++ STL library from here if you have trouble understanding some part of the code. Visit the link here for carefully crafted courses on campus placement and interview preparation on coding ninjas.

Happy learning!

Previous article
Find the minimum number of edges to be removed such that no path exists between the given pair of vertices
Next article
Find Eventual Safe States
Live masterclass