Largest Submatrix With Rearrangements | Build Intuition | 3 Approaches | Leetcode 1727
209Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 73rd Video of our Array Playlist.
In this video we will try to solve a very good 2D array problem - Largest Submatrix With Rearrangements (Leetcode -1727).
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.
Problem Name : Largest Submatrix With Rearrangements
Company Tags : Google, Directi
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Arrays/2-D%20Array/Largest%20Submatrix%20With%20Rearrangements.cpp
Leetcode Link : https://leetcode.com/problems/largest-submatrix-with-rearrangements
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
With Sorting Approach Summary :
The algorithm iterates through each row of the matrix and updates the values in the matrix based on the number of consecutive 1s above the current cell. After updating the matrix, it sorts each row in non-ascending order and calculates the area of the largest rectangle formed by consecutive 1s in each column. The maximum area encountered across all rows is stored in the variable result, which is then returned as the final output.
Without Sorting Approach Summary :
Here, the algorithm uses two vectors: prevHeights and heights. prevHeights stores pairs of heights and corresponding column indices from the previous row, while heights is updated for the current row based on the values in prevHeights and the current row of the matrix.
For each column in the current row, the code checks the height of consecutive 1s based on the information from the previous row. It updates the heights vector accordingly, keeping track of the heights and corresponding column indices.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
0:00 - Introduction
2:54 - Intuition Building + Thought Process
5:30 - Approach 1 - Story To Code + Code + Complexity
30:22 - Approach 2 - Story Explanation + Code + Complexity
36:40 - Approach 3 - Story Explanation + Code + Complexity
#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