. .
For better reading experience, you may go to this page.
Link to the problem: https://leetcode.com/problems/maximum-number-of-points-with-cost/
Unfortunately, the above solution times out. It has O(m*n*n) time complexity and a quick glance in the discussion channel tells us there is faster solution with O(m*n) time complexity.
The problem is the for loop starting at line 25. The expression at line 26 is a general formula in the sense that it does not leverage anything in the special form of the cost term abs(k−j)
.
To get some intuition, let’s reduce the size of the problem and only look at two adjacent rows. Let a[] denote the first row and b[] denote the second row. The problem is for each element in the first row, we need to select an element from the second row so that we have the best points.
We can further reduce the problem: we each element in array a, we can only select an element from array b which is on its left side. For example, we can only select cells from the green area in the second row for the blue element in array a.
Now let’s look at the values in the second row. Imagine v1 is a very large number. For example, if v1 = 1000 and other elements in the second row is 1, then for most of the elements in the first row, select v1 will give the best points. (why v1 is not preferred by all elements in the first row? It depends on the length of the row. For the right-most element in the first row, selecting v1 has the cost equals to the length of the row minus one.)
Why is that? v1 is always prefered over v2 because v2 is only 1 unit closer to elements in the first row (remember the elements in the first row needs to be on the right side of the elements in the second row) but the v1 has a much larger value which is enough to compensate the cost.
Now suppose we have v1–3 < v4. In this case, v4 should be preferred over v1 by the red elements in the first row.
This indicates that a linear scan of the array should give us the results. More specifically, we scan the two arrays from left to right, for each elements in array b, we want to know the groups of elements in array a whose preference is that element. This will give us something like the following:
