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

# 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

main :: IO ()
main = undefined


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

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

from typing import Optional


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


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

Per48edjes

def num_rotations(nums: list) -> int:
    """
    Returns the number of times a sorted array has been rotated to the right
    with the numbers wrapping to the beginning when they are rotated at the end
    of the list

    >>> nums  = [3, 4, 5, 1, 2]
    >>> num_rotations(nums)
    3
    >>> nums2  = [1, 2, 3, 4, 5]

Per48edjes

def isHappy(n: int) -> bool:
    """
    Leetcode 202. Happy number

    >>> isHappy(7)
    True
    >>> isHappy(19)
    True
    >>> isHappy(2)
    False

Per48edjes

#!/usr/bin/env python3


def merge_count_split_inversions(left_sorted: list, right_sorted: list, lst_len: int) -> tuple:
    """
    Perform merge of two sorted lists and count inversions while merging

    >>> merge_count_split_inversions([2], [1], 2)
    ([1, 2], 1)
    >>> merge_count_split_inversions([1, 3, 5], [2, 4, 6], 6)

Per48edjes

#!/usr/bin/env python3


def karatsuba_mul(m: int, n: int) -> int:
    """
    Implementation of recursive Karatsuba multiplication

    >>> karatsuba_mul(56, 12)
    672
    >>> karatsuba_mul(78, 34)

Per48edjes

"""
Inspired by Problem 3, Lab 09 from Berkeley's CS 61A course to investigate and 
implement the closed form solution via `catalan_nums` function
"""

from math import comb


def num_trees(n):
    """Returns the number of unique full binary trees with exactly n leaves. E.g.,