Minimum Cost to Make at Least One Valid Path in a Grid | 2 Detailed Approaches | Leetcode 1368 | MIK
515Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
Hi Everyone, this is the 62nd video of our Playlist "Graphs : Popular Interview Problems".
Dijkstra's Algorithm (Part-1) - • Dijkstra's Algorithm | PART-1 | Graph...
Dijkstra's Algorithm (Part-2) - • Dijkstra's Algorithm | PART-2 | (Micr...
Dijkstra's Algorithm (Part-3) - • Dijkstra's Algorithm | PART-3 | Why n...
We will solve a very good problem based 2D Grid traversal based on Backtracking and Dijkstra - Minimum Cost to Make at Least One Valid Path in a Grid | 2 Detailed Approaches | Leetcode 1368 | codestorywithMIK
We will deep dive in minute details. The explanation will be detailed so that even beginners can understand it well.
Problem Name : Minimum Cost to Make at Least One Valid Path in a Grid | 2 Detailed Approaches | Leetcode 1368 | codestorywithMIK
Company Tags : will update later
Github Solutions Link (C++/Java) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Dijkstra'a Based Problems/Minimum Cost to Make at Least One Valid Path in a Grid.cpp
Leetcode Link : https://leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid
My DP Concepts Playlist : • Roadmap for DP | How to Start DP ? | ...
My Graph Concepts Playlist : • Graph Concepts & Qns - 1 : Graph will...
My Segment Tree Concepts Playlist : • Segment Tree | Introduction | Basics ...
My Recursion Concepts Playlist : • Introduction | Recursion Concepts And...
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Video Summary :
Approach-1: Backtracking DFS
The idea behind this approach is to explore all possible paths from the starting point (top-left) to the destination (bottom-right) by recursively trying all four directions (up, down, left, right). At each step, we calculate the cost of moving to the next cell and backtrack when we reach a dead end or a previously visited cell. The key challenge is that this approach does not prioritize low-cost paths, which results in inefficient exploration and causes time limit exceeded (TLE) errors for large grids.
Approach-2: Dijkstra's Algorithm
This approach leverages Dijkstra’s algorithm, which uses a priority queue to always process the cell with the current lowest cost. It iteratively explores neighboring cells and calculates the cost to reach them, adding the new cost to the priority queue. If a cheaper path to a cell is found, it updates the cost and reprocesses that cell. The algorithm ensures that we always process cells in the order of their minimum cost, leading to an optimal solution with much better efficiency compared to backtracking.
✨ Timelines✨
00:00 - Introduction
00:46 - Motivation
02:08 - Problem Explanation
08:19 - Intuition - Backtracking
17:03 - Important Note
27:29 - Coding Backtracking - TLE
34:50 - Why Dijkstra's Algorithm
47:11 - Coding Dijkstra's
#MIK #mik #Mik
#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 #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik