LC-1499 Hard LeetCode

1499. Max Value of Equation

Array Queue Sliding Window Heap (Priority Queue) Monotonic Queue

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 44% Topics: Array, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue

Reading material

Arrays & Hashing 12 min Stacks & Queues 11 min Sliding Window 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

import collections


class Solution(object):
    def findMaxValueOfEquation(self, points, k):
        """
        :type points: List[List[int]]
        :type k: int
        :rtype: int
        """
        result = float("-inf")
        dq = collections.deque()
        for i, (x, y) in enumerate(points):
            while dq and points[dq[0]][0] < x-k:
                dq.popleft()
            if dq:
                result = max(result, (points[dq[0]][1]-points[dq[0]][0])+y+x)
            while dq and points[dq[-1]][1]-points[dq[-1]][0] <= y-x:
                dq.pop()
            dq.append(i)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT