How about using two pointers. The first pointer starts from the beginning of each range and increases by 1 until it finds the first pipe and is less than end of range. The second pointer if (left pointer +1) and increases by 1 until it finds a pipe. We add the difference between both the pointers -1 as the current count of the stars. Then, we make the first pointer to start from the second pointer. And the secondpointer starts from firstpointer +1. We always check if the pointers are less than right.
I got this question for amazon's OA and also a question similar to this for IBM's OA on the coding portion so this is a good question to review. Too bad i didnt know how to do it 😭
this is the best video to understand this problem even if you're using python
loved it, one of the easiest and best explanation. Thank you !
Love you solution (and your voice)
Good solution. I like that you did it with regular arrays makes it easy to transfer the logic to other languages.
Great solution thanks man
That is a great clear explanation. Thanks!
omg, the prefix sum explanation was so good
awesome!
How about using two pointers. The first pointer starts from the beginning of each range and increases by 1 until it finds the first pipe and is less than end of range. The second pointer if (left pointer +1) and increases by 1 until it finds a pipe. We add the difference between both the pointers -1 as the current count of the stars. Then, we make the first pointer to start from the second pointer. And the secondpointer starts from firstpointer +1. We always check if the pointers are less than right.
I got this question for amazon's OA and also a question similar to this for IBM's OA on the coding portion so this is a good question to review. Too bad i didnt know how to do it 😭
Awesome!
Another option would be to construct the running totals, and then use a binary search to find the rising edges.
I do this in javascript but dont get that fast of a result
isn't using treeset better since O(logn) is faster than O(n) ?
You have to iterate over the array anyhow, so it doesn't matter for time complexity, but yeah it probably would be better in practice.
accessing the nearest candle is o(1) with an array, but o(logn) for a treeset. initialising either is o(n)