Count Square Submatrices with All Ones | Recursion | Bottom Up | Leetcode 1277 | codestorywithMIK
411Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 102nd Video of our Playlist "Dynamic Programming : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a good DP on Grids problem : Count Square Submatrices with All Ones | Recursion | Bottom Up | Detailed | Leetcode 1277 | codestorywithMIK
This is same as Leetode - 221 "Maximal Square" Problem - https://leetcode.com/problems/maximal-square/description/
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 : Count Square Submatrices with All Ones | Recursion | Bottom Up | Detailed | Leetcode 1277 | codestorywithMIK
Company Tags : Flipkart
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/DP/DP on Grids/Count Square Submatrices with All Ones.cpp
Leetcode Link : https://leetcode.com/problems/count-square-submatrices-with-all-ones/description/
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/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
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
The approaches provided in both the C++ and Java solutions use dynamic programming to solve the problem of counting squares of 1s in a binary matrix.
Key Ideas:
Memoization for Recursive Approach:
The first approach uses a recursive function with memoization to explore each cell in the matrix.
For each cell, it recursively checks possible square formations by examining cells to the right, below, and diagonally down-right.
It builds up the size of the largest square that can be formed at each cell and adds it to a cumulative count.
Iterative DP Table Approach:
The second approach constructs a DP table (dp), where each cell in dp represents the size of the largest square with the bottom-right corner at that cell.
For each 1 in the matrix, the square size is calculated as 1 plus the minimum of adjacent squares (top, left, and top-left).
The size at each cell is added to a running count, capturing the total number of squares formed in the matrix.
✨ Timelines✨
00:00 - Introduction
#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