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.
Output
4.2.
Time Complexity 
4.3.
Space Complexity 
5.
Frequently Asked Questions
6.
Key Takeaways
Last Updated: Mar 27, 2024

Determine whether we can travel to every node under the given conditions

Author Gaurish Anand
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Before beginning with this question, let’s recap what a graph means. 

Source

A graph is a data structure that is not linear and contains edges that connect vertices.  

Graphs can be either directed or undirected. A directed graph is a collection of vertices/nodes connected by edges where each edge has a direction. The edges of the graph are indicated by arrows pointing in the direction of traversal. If an arrow is pointing towards 2 on edge between vertex 1 and 2, the graph can be traversed from 1 to 2 rather than 2 to 1. On the other hand, an undirected graph can be traversed in either direction, i.e., we can travel in the graph from 1 to 2 and 2 to 1 if the graph is undirected.

Problem Statement

We are given a graph with (N+1) nodes and a boolean array of size N. There will be in total (2*N-1) edges where:

  1. (N-1) edges will be from ith node to (i+1)th node and 
  2. The rest of N edges will be from ith node to (N+1)th node if booleanArray[i] = 0; otherwise, edge will be from (n+1)th to ith node.


You have to find whether a path that can visit all the nodes will exist or not, and if the path exists, print the path.

Example 1: 

Input: N = 3     booleanArray[] = {0, 1, 0}

The Tree for the above input will be: 

Output: [1,2,3,4]
 

Example 2: 

Input: N = 4     booleanArray[] = {0, 1, 1, 1}

The Tree for the above input will be: 

Output: [1,5,2,3,4]  

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

We will solve the above problem greedily by the following operations: 

  1. If booleanArray[0] = 1, we have an edge from the node (N+1) to the 1st node. So one of the possible paths can be 
    (N+1) → 1 → 2 → 3 → 4 … → N
  2. If booleanArray[N-1] = 0, then it means we have an edge from the node Nth node to the (N+1)st node. So one of the possible paths can be 
    1 → 2 → 3 → 4 … → N → N+1

     
  3. If the above situations are not true, then it means we have booleanArray[0] = 0 and booleanArray[N-1] = 1. 
    So in that case find an ith node where booleanArray[i] = 0 and booleanArray[i+1] = 1 for (1 < i < N). Since such a node will always exist, therefore path will always exist, and path, in this case, will be from 
    1 → 2 → 3 … → i → N+1 → i+1 → i+2 → … → N

Code in C++

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

void printPath(int N,vector<bool>& booleanArray){
	if(booleanArray[1]==1){
		// There is an edge from (n+1)th node to 1st node
		// so path can be (N+1)th --> 1th --> 2nd --> ... --> Nth

		cout<<(N+1)<<" ";
		for(int i=1;i<=N;i++){
			cout<<i<<" ";
		}
	}else if(booleanArray[N]==0){
		// There is an edge from (n)th node to (n+1)th node
		// so path can be 1th --> 2nd --> ... --> Nth --> (N+1)th

		for(int i=1;i<=(N+1);i++){
			cout<<i<<" ";
		}
	}else{
		// We need to find a ith node where booleanArray[i]==0 and booleanArray[i+1] = 1
		vector<int> path;
		for(int i=1;i<N;i++){
			if(booleanArray[i]==0 && booleanArray[i+1]==1){
				cout<<i<<" "<<(N+1)<<" "<<(i+1)<<" ";
				for(int j=i+2;j<=N;j++){
					cout<<j<<" ";
				}
				break;
			}else{
				cout<<i<<" ";
			}
		}
	}
}

int main(){
	int N = 4;
	vector<bool> booleanArray{NULL ,0,1,1,1};
	printPath(N,booleanArray);
}

Output

1 5 2 3 4 

Time Complexity 

Since we visit N nodes only once, therefore time complexity is O(N);

Space Complexity 

Since we are not using any extra space, therefore space complexity is O(1) 

Frequently Asked Questions

  1. What is the difference between a tree and a graph?
    Trees and graphs are different since there can never be loops in a tree, but we can have loops in a graph. Also, all the nodes in a tree are always connected, but that is not true for a graph.
     
  2. What is the difference between a DFS Traversal and a BFS Traversal?
    In a DFS traversal of a graph, we begin from any random node and travel down each branch as feasible before returning to the current node. In contrast, in a BFS traversal, we visit each node at the current level before visiting their children nodes. 
    DFS Traversal is performed using a stack, whereas a BFS Traversal is performed using a queue.
     
  3. Are there more Data Structures and Algorithms problems in Coding Ninjas Studio?
    Yes, Coding Ninjas Studio offers both coding practice and frequently asked interview questions. The more we practice, the greater our chances of landing a job at our ideal organization.

Key Takeaways

This article taught us how to travel to every node in a graph depending on the specific conditions.

Since graphs are frequently asked in interviews, we recommend you practice more problems based on graphs on Coding Ninjas Studio. 

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Previous article
Maximum Bitwise XOR of values of nodes of an Acyclic Graph made up of N given vertices using M edges
Next article
Pair of positions in matrix which are not accessible
Live masterclass