Here is the link.
First practice - C# - Deque - TLE 64/65
Dec. 7, 2020
I studied the code shared by votrubac. I came cross TLE error on test case 64/65.
First practice
It is the simple algebra. I do have to refresh my memory and then find what to look for. I like to borrow analysis from Lee215 in the following:
Explanation
Because xi < xj,
yi + yj + |xi - xj| = (yi - xi) + (yj + xj)
So for each pair of (xj, yj),
we have xj + yj, and we only need to find out the maximum yi - xi.
To find out the maximum element in a sliding window,
we can use priority queue or stack.
Analysis
The maximum yi - xi from index = 0 to i. For next point j > i,
get the maximum yi - xi within reach (xj - xi <= k).
Check if yi - xi + yj + xj produces the biggest result so far.
Adjust maximum using the new point: yj - xj.
Solution
One of ideas is to use the sliding window technique and monotonically decreasing deque. The maximum yi - xi therefore will be in the front. For the deque, the index j is stored.
Items that got out of the xj - xi window from the front of the queue should be removed. Afterwards, do some calculation. Finally, i is added to the deque, making sure we keep monotonicity of y - x. More detail, all elements with smaller y - x from the back of the deque are removed.
public class Solution {
public int FindMaxValueOfEquation(int[][] points, int k) {
var deque = new LinkedList<int>();
var result = Int32.MinValue;
var rows = points.Length;
var columns = points[0].Length;
for (int j = 0; j < rows; ++j)
{
while (deque.Count > 0 && (points[j][0] - points[deque.First()][0]) > k)
{
deque.RemoveFirst();
}
if (deque.Count > 0)
{
var first = deque.First();
result = Math.Max(result, points[first][1] - points[first][0] + points[j][1] + points[j][0]);
}
while (deque.Count > 0 && points[deque.Last()][1] - points[deque.Last()][0] < points[j][1] - points[j][0])
{
deque.RemoveLast();
}
deque.AddLast(j);
}
return result;
}
}