Tag: DFS

Find length of longest path in the matrix with consecutive characters

Given a M x N matrix of characters, find the length of longest path in the matrix starting from a given character. All characters in the longest path should be increasing and consecutive to each other in alphabetical order.

Replace all occurrences of 0 that are completely surrounded by 1 in a binary matrix

Give a M x N binary matrix, replace all occurrences of 0 by 1 which are completely surrounded by 1.

Traverse the given directory using BFS and DFS in Java

In this post, we will see how to traverse the given directory and list out all files present in it and all its sub-directories.

Find Cost of Shortest Path in DAG using one pass of Bellman-Ford

Given a directed acyclic graph (DAG) and a source vertex, find the cost of shortest path from source vertex to all other vertices present in the graph. If vertex can’t be reached from given source vertex, printĀ its distance as infinity.

Determine if a graph is Bipartite Graph using DFS

Given a graph, determine if given graph is bipartite graph using DFS. A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.

Check if Graph is Strongly Connected or not using one DFS Traversal

Given a directed graph, check if it is strongly connected or not. A directed graphs is said to be strongly connected if every vertex is reachable from every other vertex.

Inorder Tree Traversal | Iterative & Recursive

Given a binary tree, write iterative and recursive solution to traverse the tree using in-order traversal in C++ and Java.   Unlike linked lists, one-dimensional arrays and other linear data structures, which are traversed in linear order, trees may be traversed in multiple ways in depth-first order (pre-order, in-order, and post-order) or breadth-first order (level …

Preorder Tree Traversal | Iterative & Recursive

Given a binary tree, write iterative and recursive solution to traverse the tree using pre-order traversal in C++ and Java.     Unlike linked lists, one-dimensional arrays and other linear data structures, which are traversed in linear order, trees may be traversed in multiple ways in depth-first order (pre-order, in-order, and post-order) or breadth-first order …

Postorder Tree Traversal | Iterative & Recursive

Given a binary tree, write iterative and recursive solution to traverse the tree using post-order traversal in C++ and Java.     Unlike linked lists, one-dimensional arrays and other linear data structures, which are traversed in linear order, trees may be traversed in multiple ways in depth-first order (pre-order, in-order, and post-order) or breadth-first order …

Replace all occurrences of 0 that are not surrounded by 1 in a binary matrix

Give a M x N binary matrix, replace all occurrences of 0 by 1 which are not completely surrounded by 1.

Flood Fill Algorithm

Flood fill (also known asĀ seed fill) is an algorithm that determines the area connected to a given node in a multi-dimensional array.

Find all occurrences of given string in a character matrix

Given a M x N matrix of characters, find all occurrences of a given string in the matrix. We are allowed to search the string in all eight possible directions i.e. North, West, South, East, North-East, North-West, South-East, South-West. Note that there should not be any cycles in the output path.