Largest Plus Sign | Leetcode 764 | Live coding session 🔥🔥🔥

Here is the solution to "Largest Plus Sign" leetcode question. Hope you have a great time going through it.
Solution: leetcode.com/problems/largest...
1) 0:00 Explaining the problem out loud
2) 1:10 Algorithm walkthrough
3) 2:00 Solution approach
4) 10:40 Coding
Solutions github.com/Sunchit/Coding-Dec...
For discussion/feedback
Feel free to join discord / discord
Complete September playlist : • Leetcode September 202...
Complete August playlist : • Leetcode August 2021 C...
Complete July playlist : • Leetcode July 2021 Cha...
Complete June playlist : • Leetcode June 2021 Cha...
Complete May playlist : • Leetcode May 2021 Chal...
Complete April playlist : • Leetcode April 2021 Ch...
Complete March playlist : • Playlist
Complete Feb playlist : • Leetcode February 2021...
Complete Jan playlist : • Leetcode January 2021 ...
Complete December Playlist: • Leetcode December 2020...
PS : Please increase the speed to 1.25X

[@abhishekjain7065]

Thank you bhai :) I paused the video exactly when you said “with a little thought, you can try it on your own” and made the ACCEPTED submission…

[@CodeWithSunchitDudeja]

Great 👍 going , impressive

[@shrimpo6416]

Thank you! Your explanation is the best across CZcams!

[@CodeWithSunchitDudeja]

Thanks Shrimpo for your support

[@skystone1000]

Wow, Nice approach and clear explanation, could just come up with brute force on my own.
Thanks 😀

[@jatinthakwani5370]

Nice explaination.
Instead of creating four arrays, you can make one 2d array that would be more optimized.

[@LegitGamer2345]

So the size of the plus is going to be decided by min of all 4 because since it is minimum , a contiguous section of ones of length min will be present in all 4 directions
Wow that was pretty cool ! Nice explanation !!

[@CodeWithSunchitDudeja]

That is correct

[@Ryan-mr9pn]

Oh ohkay so we r standing at a point and seeing how far can we extend our 4 arms of plus sign such that they remain equal and that is our ans.

[@wintersol9921]

Where can I find the code which uses the same matrix for every direction? (The one that you mentioned at the end of the video.

[@CodeWithSunchitDudeja]

I am waiting for someone to write it up and raise a pull request here github.com/Sunchit/Coding-Decoded

[@MGtvMusic]

class Solution {
public int orderOfLargestPlusSign(int N, int[][] mines) {
Set banned = new HashSet();
int[][] dp = new int[N][N];

for (int[] mine: mines)
banned.add(mine[0] * N + mine[1]);
int ans = 0, count;

for (int r = 0; r < N; ++r) {
count = 0;
for (int c = 0; c < N; ++c) {
count = banned.contains(r*N + c) ? 0 : count + 1;
dp[r][c] = count;
}

count = 0;
for (int c = N-1; c >= 0; --c) {
count = banned.contains(r*N + c) ? 0 : count + 1;
dp[r][c] = Math.min(dp[r][c], count);
}
}

for (int c = 0; c < N; ++c) {
count = 0;
for (int r = 0; r < N; ++r) {
count = banned.contains(r*N + c) ? 0 : count + 1;
dp[r][c] = Math.min(dp[r][c], count);
}

count = 0;
for (int r = N-1; r >= 0; --r) {
count = banned.contains(r*N + c) ? 0 : count + 1;
dp[r][c] = Math.min(dp[r][c], count);
ans = Math.max(ans, dp[r][c]);
}
}

return ans;
}
}

[@satyampatidar8600]

what is intuition behind these logic?

[@CodeWithSunchitDudeja]

Analyse the plus sign. It has 4 branches you need the mini of longest running branch in each direction.

[@yoyo8293]

size of 1 2D array here would be = 5000*500 = 2500000 which is 2.5 * 10^6 . you have made 4 2D arrays = 4 * 2.5 * 10^6 = 10^7 . Shouldn't that give MLE ?

[@amazinglife5400]

Sunchit, can't we do one thing here. If we directly visit the mines points and then get all directions : left, right, top & bottom because at the mines point our row number & column number will remain constant only so would'nt T.C in that case would be O(mines.length * grid.length) -> O(k * n). What's your view on it Sunchit ?

[@CodeWithSunchitDudeja]

Frankly it appears like a possible solution too. Try and reduce it to 1D first, if it works then we can extended to 2D. For iterating in all 4 directions you need to perform sorting on mines array column wise and row wise both. Also, please share if you succeed with it.