Greedy

The intuition is that starting at index 0, we extend our max range to the furthest possible index we can reach so far. Once we are at some index that is beyond our reach, we clearly cannot reach the end so we return false. Otherwise we return true.

This is a very similar question to the first, we just want the number of jumps instead of a boolean feasibility check. It's the same greedy idea, we just need to track updates.

This is an example of using Two Pointers technique in a greedy fashion.

The idea is we want max_{i,j : i < j} (j-i) * (min(height[i], height[j]))

Basically out of all pairs of left,right edges, we want the maximum area rectangle of water that that rectangle can hold. Clearly we can brute force this formula in O(n^2) time, O(1) space.

However, this is wasteful. We can use a greedy, locally optimal algorithm to speed this up.

Since we want maximum area, it makes sense to start with the maximum width rectangle, being i = 0, j = n-1.

Imagine we have two edges, i,j. The lower height edge defines the amount of water the rectangle can hold. Since we can only shrink our window, (width) in order to increase the max area, we must abandon the lower height edge in search of a higher height. (ie. if we shrank the window by moving the higher height edge, all subsequent windows have max water area <= our current area, because the height of water is capped by the lower height edge.)

This is an amazing observation, because it saves a lot of redundant work. For example, if i = 0, j = n-1, and 0 is the lower height edge, we know that any rectangle with left edge i = 0 and j where j < n-1 will have less water area than the current area being (n-1 - 0) * (height[left]), because the first term the width will be strictly smaller, and the second term the minimum height will be less than or equal to height[left]. So basically, you can think of it as, on every iteration we save O(n) time. There will be O(n) iterations because we move each pointer exactly one every iteration, and we terminate once left crosses right, and both are initialized with space n apart.

This outlines a proof of the greedy stays ahead approach. We just showed that at every step, we can safely discard a set of solutions that will clearly be no better than our current. Which essentially means our greedy solution will not discard any optimal solution that exists, ie. is a smart brute force search. This is actually similar to the proof of correctness for the sliding window chapter.

This example outlines a common solution approach: model the problem mathematically, which instantly provides a brute force solution. However, you can leverage some greedy observations to make the solution optimally efficient.

This is a very similar idea to container with most water. We realize that essentially we want to maximize diff = min(max_prefix_height(i), max_suffix_height(i)) - height[i] for each i individually, and sum them for all i.

Note that depending on how we define prefix(i) (either as inclusive of i or exclusive), we will need a max(0, diff). (think about why, if it is exclusive then the diff can be negative, which obviously doesn't make sense.)

We can brute force this in O(n^2) time and O(1) space. We can use prefix max and suffix max dp to do this in O(n) time and space. But the optimal solution of O(n) time and O(1) space requires a greedy two pointers strategy.

If we have two pointers l,r if max_prefix_height[l] < max_suffix_height[r], we know that min(max_prefix_height(l), max_suffix_height(l)) = max_prefix_height[l]. Why? Because max_suffix_height(l) >= max_prefix_height_r(r). Think about that. So we can greedily compute for index l, and increment it. Similar logic for the else case.

This is a fairly simple problem. Just handle it with greedy intuition. Obviously you want to pair the worker with the highest profit task they can do.

The high level idea is if you consider nums1 in sorted order with index j, you know all previous indices j that we need to index into nums2 with. So basically you can use a heap of size k to maintain the sum of the max k. This is a min heap, so when we pop, we pop the smallest value out. This code is very common to maintaining a heap of size k:

heappush(heap, nums2[sl[i][1]])
sum_heap += nums2[sl[i][1]]
if len(heap) == k+1:
    sum_heap -= heappop(heap)

Now given a certain index i, (in nums1 sorted order) we have the greedy optimal max sum of nums2 elements with these corresponding indices j.

What remains is re-assigning back to our original indices i. Sum_max_k indices are relative to the sorted order of nums1.

We need to binary search in the sorted list for (nums1[i], -inf). (see sorted list chapter) -1 to the index, and that gives us the sorted order index which we can index into for sum_max_k.

The first solution is greedy heap. The second is with binary search.

The problem with just using a pure greedy approach, similar to binary search is that we could be using a ladder for a huge gap, but huge gap is at the end, where we would have never reached there anyways. (ie. there is no fixed length) This is why we either need to use a greedy heap solution where we swap ladders with bricks on the fly as we move left to right. OR we can fix the final building length using binary search, and once we fix the length we can use a simple greedy solution.

Binary search solution should be fairly straightforward. Max template.