Build a Matrix With Conditions | BFS | DFS | Detailed Explanation | Leetcode 2392 | codestorywithMIK
333Whatsapp Community Link : https://www.whatsapp.com/channel/0029...
This is the 52th Video of our Playlist "Graphs : Popular Interview Problems" by codestorywithMIK
Cycle Detection using DFS - • Graph Concepts & Qns - 4 (Miscoroft, ...
Topological Sorting DFS - • Graph Concepts & Qns - 7 (Microsoft, ...
Topological Sorting BFS - • Graph Concepts & Qns - 7 (Microsoft, ...
In this video we will try to solve a very good Graph Problem : Build a Matrix With Conditions | BFS | DFS | Detailed Explanation | Leetcode 2392 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Build a Matrix With Conditions | BFS | DFS | Detailed Explanation | Leetcode 2392 | codestorywithMIK
Company Tags : APPLE
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Intervie...
Leetcode Link : https://leetcode.com/problems/build-a...
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
Approach 1: Topological Sorting using DFS
Time Complexity (T.C.): O(k2+n)
Space Complexity (S.C.): O(k2+n)
This approach uses Depth-First Search (DFS) to perform topological sorting. Here’s a breakdown:
Graph Representation: The graph is represented using an adjacency list stored in an unordered map.
DFS for Topological Sort:
Nodes are marked as not visited, visiting, or visited using a visited vector.
A DFS is performed, pushing nodes onto a stack when their entire subtree has been processed.
During DFS, if a node that is currently being visited is encountered again, a cycle is detected.
Cycle Detection: If a cycle is detected during the DFS, an empty order is returned, indicating no valid topological ordering is possible.
Order Construction: Nodes are popped from the stack to form the topological order.
Approach 2: Topological Sorting using BFS
Time Complexity (T.C.): O(k2+n)
Space Complexity (S.C.): O(k2+n)
This approach uses Breadth-First Search (BFS) and Kahn's algorithm to perform topological sorting. Here’s a breakdown:
Graph Representation: The graph is represented using an adjacency list stored in a vector of vectors. An in-degree vector is also maintained.
Queue for BFS:
Nodes with an in-degree of zero are added to a queue.
Nodes are processed from the queue, and their neighbors’ in-degrees are decremented. If a neighbor’s in-degree becomes zero, it is added to the queue.
Cycle Detection: If the total number of nodes processed does not match the number of nodes in the graph, a cycle is detected.
Order Construction: Nodes are added to the order list in the sequence they are processed from the queue.
Building the Matrix:
Row and Column Orders: Both approaches first compute topological orders for row and column conditions.
Matrix Construction: If either topological order is empty (indicating a cycle), an empty matrix is returned. Otherwise, a matrix is constructed where elements are placed according to the computed row and column orders.
✨ Timelines✨
00:00 - Introduction
0:39 - Problem Explanation
6:35 - Thought Process
9:58 - Topological Sorting Recap
15:15 - Building Matrix
22:15 - Coding it up - DFS
36:44 - Coding it up - BFS
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024