Editorial for Door(Dasher)

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: pingu

This is a problem based on the 2 Pointer and Sliding Window Lesson.

Using the Two-Pointer technique, say with pointers $i$ ~i~ and $j$ ~j~, maintain the sum of the range $(i, j)$ ~(i, j)~. House $j$ ~j~ marks the furthest house one could deliver presents to starting from house $i$ ~i~, where the sum of the range does not exceed $M$ ~M~. For every $1 \le i \le N$ ~1 \le i \le N~, increase $j$ ~j~ from the previous iteration; as no house has negative children, pointer $j$ ~j~ can only increase.

Both pointers $i$ ~i~ and $j$ ~j~ will start at $1$ ~1~ and increase until $N$ ~N~ (as both pointers never decrease), giving us a time complexity of $O(N)$ ~O(N)~.

Comments

There are no comments at the moment.