LC-2736 Hard LeetCode

2736. Maximum Sum Queries

Array Binary Search Stack Binary Indexed Tree Segment Tree Sorting Monotonic Stack

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 28% Topics: Array, Binary Search, Stack, Binary Indexed Tree, Segment Tree, Sorting, Monotonic Stack

View full problem on LeetCode

Reading material

Arrays & Hashing 12 min Binary Search 12 min Stacks & Queues 11 min

Reference solution (spoiler · python)

# Time:  O(nlogn + mlogm + mlogn)
# Space: O(n + m)

import itertools
import bisect


# sort, mono stack, binary search
class Solution(object):
    def maximumSumQueries(self, nums1, nums2, queries):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        pairs = sorted(((i, j) for i, j in itertools.izip(nums1, nums2)))
        result = [0]*len(queries)
        stk = []
        for x, y, i in sorted(((x, y, i) for i, (x, y) in enumerate(queries)), reverse=True):
            while pairs and pairs[-1][0] >= x:
                a, b = pairs.pop()
                while stk and stk[-1][1] <= a+b:
                    stk.pop()
                if not stk or stk[-1][0] < b:
                    stk.append((b, a+b))
            j = bisect.bisect_left(stk, (y,))
            result[i] = stk[j][1] if j != len(stk) else -1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT