Leetcode discuss: 1499. Max Value of Equation

 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;
    }
}