LC-2398 Hard LeetCode

2398. Maximum Number of Robots Within Budget

Array Binary Search Queue Sliding Window Heap (Priority Queue) Prefix Sum Monotonic Queue

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 37% Topics: Array, Binary Search, Queue, Sliding Window, Heap (Priority Queue), Prefix Sum, Monotonic Queue

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(n)
# Space: O(n)

import collections


# sliding window, two pointers, mono deque
class Solution(object):
    def maximumRobots(self, chargeTimes, runningCosts, budget):
        """
        :type chargeTimes: List[int]
        :type runningCosts: List[int]
        :type budget: int
        :rtype: int
        """
        result = left = curr = 0
        dq = collections.deque()
        for right in xrange(len(chargeTimes)):
            while dq and chargeTimes[dq[-1]] <= chargeTimes[right]:
                dq.pop()
            dq.append(right)
            curr += runningCosts[right]
            if chargeTimes[dq[0]]+(right-left+1)*curr > budget:
                if dq[0] == left:
                    dq.popleft()
                curr -= runningCosts[left]
                left += 1
        return right-left+1


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


# sliding window, two pointers, mono deque
class Solution2(object):
    def maximumRobots(self, chargeTimes, runningCosts, budget):
        """
        :type chargeTimes: List[int]
        :type runningCosts: List[int]
        :type budget: int
        :rtype: int
        """
        result = left = curr = 0
        dq = collections.deque()
        for right in xrange(len(chargeTimes)):
            while dq and chargeTimes[dq[-1]] <= chargeTimes[right]:
                dq.pop()
            dq.append(right)
            curr += runningCosts[right]
            while dq and chargeTimes[dq[0]]+(right-left+1)*curr > budget:
                if dq[0] == left:
                    dq.popleft()
                curr -= runningCosts[left]
                left += 1
            result = max(result, right-left+1)            
        return result

Solution from kamyu104/LeetCode-Solutions · MIT