Largest Plus Sign | A Detailed Explanation of the Solution
Vložit
- čas přidán 24. 07. 2024
- 764. Largest Plus Sign. I explain the solution in detail, with an observation based approach. Scan based approaches are a good idea to remember for the next time!
Problem: leetcode.com/problems/largest...
My references: leetcode.com/problems/largest...
Follow:
LeetCode: leetcode.com/chaudhary1337/
GitHub: github.com/chaudhary1337
LinkedIn: / tanishq-chaudhary-a203...
My Website: chaudhary1337.github.io/
#LeetCode #LeetCodeDaily #chaudhary1337
Hey one doubt for left count in your example ,
if element at 0th index is 1 then the left count should be zero right because there are no elements at left of 0th index, but in your code for the 0th index is it taking minimum as 1?
Aha! Nice catch :D
That's an implementation detail. Since the mines are 0, we want to avoid setting the count to 0 as well. Think why ;)
This is why we increase the count by 1, always, helping us *dodge* and *distinguish* with the mines. Thus, while mathematically the logic is sound (as shown in OneNote), implementation changes things a bit.
ok got it!! Thanks Man your explanations are too good.
OMG, Such a god-level explanation. You are truly a remarkable teacher. Keep it up.
I love your explanations. Have you thought about doing some problems with interesting solutions from weekly contests?
I haven't looked at it, but an interesting suggestion! I'll try looking into it.
Back on track!
At 6:00 you said that n^3 would work for n
n^3 is going to take 300^3 = 27*10^6. This is well below the approximate range of 10^8. 500^3 however, is 125*10^6 which puts it at the borderline. Especially in Python3, its not a good idea to borderline, since its almost always going to give a TLE.
@@chaudharycodes this is a new thing to me. can you tell what is this range of 10^8. thanks in advance ?
@@ritwik121 Its basically saying that we can do 10^8 operations in 1 second. The 10**8 and the 1 sec numbers will both vary from OJ to OJ and language to language and are only approximate numbers. In our case, Python3 *can* give a TLE. LeetCode is a bit lenient, so it may work.
Refs:
codeforces.com/blog/entry/4825
codeforces.com/blog/entry/21344
blog.codechef.com/2009/04/01/announcing-time-limits-based-on-programming-language/