Per48edjes

from typing import Optional


"""
LeetCode 206. Reverse Linked List
"""


class ListNode:
    def __init__(self, val, next=None):

Per48edjes

from typing import Optional


class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


def hasCycle(head: Optional[ListNode]) -> bool:

Per48edjes

main :: IO ()
main = undefined


toDigitsRev :: Integer -> [Integer]
toDigitsRev n
  | n <= 0 = []
  | otherwise = (n `mod` 10) : toDigitsRev (n `div` 10)

Per48edjes

# Let's implement Randomized QuickSort!
import random

class Solution:

    # O(n)
    def partition(self, nums: List[int], l: int, r: int) -> int:
        # Choose random pivot, put it first in the array 
        random_idx = random.choice(range(l, r + 1))
        nums[l], nums[random_idx] = nums[random_idx], nums[l]

Per48edjes

# This is the same thing as finding the (len(nums) - (k-1))th order statistic.
#   - Note: We need to transform "Kth Largest, 1-indexed" into "Kth Smallest, 0-indexed"
# Idea: Use randomized quickselect! It has O(n) expected time

import random


class Solution:

    # O(n) time, O(1) space

Per48edjes

from typing import Optional


class MinHeap:

    """
    A MinHeap is a complete binary tree where the value of each node is less than or equal
    to the value of its children. (The root node is the minimum element in the heap.)

    This implementation supports the following operations:

Per48edjes

-- Minimal nvim config with lazy
-- Assumes a directory in $NVIM_DATA_MINIMAL
-- Start with
--
-- export NVIM_DATA_MINIMAL=$(mktemp -d)
-- export NVIM_APP_NAME="nvim-ht-minimal"
-- nvim -u minimal.lua
--
-- Then exit out of neovim and start again.

Per48edjes

Per48edjes

class Solution:

    def minOperations(self, nums: List[int]) -> int:

        def opMin(freq: int) -> int:
            assert freq > 1, f"{opMin.__name__} only takes freq > 1"
            call_stack = [(freq, 0)]
            while call_stack:
 k, ops = call_stack.pop()

Per48edjes

import math


class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        n = len(arr)
        spanned_indices = [[1,1] for _ in range(n + 1)]
        mono_i_stack = []
 for i, num in enumerate(arr + [-math.inf]):