Day 9 of LeetCode

Documenting LeetCode solving.

Q1

853. Car Fleet

Medium. Stack

From Neetcode, youtube.com/watch?v=Pr6T-3yB9RM

class Solution:
    def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
        stack = []
        pair = [[p, s] for p, s in zip(position, speed)]

        for p, s in sorted(pair)[::-1]: # Sort first, 
                                        # then iterate in reversed order
            stack.append((target - p) / s) # Decimal
            if len(stack) >= 2 and stack[-1] <= stack[-2]:
                stack.pop()

        return len(stack)

Q2

84. Largest Rectangle in Histogram

Hard. Stack

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = [] # pair: (index, height)
        maxArea = 0

        for i, h in enumerate(heights):
            start = i
            # If the coming height is smaller, 
            # that means we can't extend further
            while stack and h < stack[-1][1]:
                index, height = stack.pop()
                maxArea = max(maxArea, height * (i - index))
                # Extend the start backwards to the one just popped
                start = index
            stack.append((start, h))

        # Iterate the remaining pairs in stack
        for i, h in stack:
            maxArea = max(maxArea, h * (len(heights) - i))

        return maxArea

Q3

704. Binary Search

Easy. Binary search

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        # Left and right pointer should meet each other, they can't cross
        while l <= r:
            # // is to get the integer
            mid = l + ((r - l) // 2) # Avoid overflow
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1

        return -1