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 and j, maintain the sum of the range (i, j). House j marks the furthest house one could deliver presents to starting from house i, where the sum of the range does not exceed M. For every 1 \le i \le N, increase j from the previous iteration; as no house has negative children, pointer j can only increase.

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


Comments

There are no comments at the moment.