Two Pointers
19 / 170Two PointersLesson 4 of 6About 40 min
When the two ends are not symmetric, one side is provably useless. Finding which one is the whole problem.
In the sorted-sum search, the comparison told you which pointer to move because the sum moved predictably. Some problems have no target to compare against. Instead the quantity you care about depends on both ends at once, and you have to reason about which end is holding you back.
Here is a toy version. Two vertical posts of given heights stand at given positions. The rectangle they enclose has width equal to the distance between them and height equal to the shorter post, since anything taller spills over. Find the largest such rectangle.
def largest_rectangle_slow(heights): best = 0 for i in range(len(heights)): for j in range(i + 1, len(heights)): width = j - i height = min(heights[i], heights[j]) best = max(best, width * height) return best print(largest_rectangle_slow([1, 8, 6, 2, 5, 4, 8, 3, 7]))The next problem uses a discard argument too, and the quantity being tracked is less obvious. Before you write anything, work out what each position contributes to the answer, and what you would need to know about both sides in order to compute that contribution.
Pointers sit at heights 8 on the left and 3 on the right. Which move is provably safe, and why?
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.