HackerRank | Array Manipulation | Solution Explained (Java + Whiteboard)

Running Time: O(N)
Space Complexity: O(1)

[Lotuz]

Coming here after a long time just to thank you Xavier, for the comment in the beginning of the video. About not knowing how could someone come up with this on their own. I've struggled a lot with the idea that some people are just so incredibly much smarter and better at this than I am. And thats ok that they are. But at the same time some people are just more educated, have more study, have more contact with these challenges and patterns, as I have more contact with other stuff, and remembering that is very good.

[sadBoiDev]

"I don't know how you come up with this unless your really smart" Ya thats the vibe every time I cant do a problem in O(n) time =[

[_-]

HI Xavier, I did not understand why we should actually subtract 100 from b+1 index. Could you explain more about this operation?

[ALEINLOSANGELES]

Took me a while to get there, but for whoever didn't understand and not familiar with these problems (like me) here's my attempt to explain. The way this problem is solved is not "brute force" iterating and adding values. It is solved through a "check". For example, first array where we have 100 at position 1, 2, we could read the line as 100(true), 100(true), 100-100(false), 100-100(false), 100-100(false) is
that is going to be 100, 100, 0, 0, 0. Doing this process for all the lines we get the solution that we would get through the addition process. hope this helps.

[peterr]

Thank you! I especially like the whiteboard. Very clear down to earth explanation.

[loam]

In the first cicle you can go without "if(end + 1 < n)", if you create initial array of size (n + 1), which is better in terms of micro-optimizations.

[vijayjangid]

A very good video and Subscribed you also. Thanks bro!

[dethathela]

Great solution! Thanks :)
One thing:
Space Complexity: O(1)
Is it really O(1)? You create an auxiliary array of N elements, so isn't it O(N)?

[RishiRaj-dlmg]

Sir first of all great explanation.Can we do this problem using segment trees ?? Can we just build a segemt tree and updateRange from a to b? and at last traverse the tree array and find max.

[saikumarboda]

why do u taken -1 in queries[][]-1 for start and end values

[lianghe]

"I don't know how to explain it" is definitely not a good explanation :D

[skyjoe]

Gee what kind of person can come up with this idea? I was able to make O(Qn) algorithm with time limit exceeds for some test cases.

[romko-romario]

P.S. In you video, I also highly appreciate good quality and high resolution, which are many other tutorials devoid of, plus, of course, well perceptable logic of explanation. Nice job!

[outofboundsbro]

I dislike this question immensely. The problem description leads you to think you gotta replace all those individual indexes. I personally feel like the problem intentionally misleads you.