L33tcode_problems.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "#SumofTwo problem\n",
    "\n",
    "from typing import List #To be able to annotate what types list \n",
    "#should accept, need to use typing.List\n",
    "\n",
    "class Solution1:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        for i in range(0,len(nums)):\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[i]+nums[j] == target:\n",
    "                    return [i,j]\n",
    "class Solution2:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        #nums.sort() #changes the list directly (returns nothing)\n",
    "        complement_dict = {}\n",
    "        for i in range(0,len(nums)):\n",
    "            complement = target - nums[i]\n",
    "            if nums[i] in complement_dict:\n",
    "                return [complement_dict[nums[i]]]+[i]\n",
    "            else:\n",
    "                complement_dict[complement] = i\n",
    "\n",
    "x=Solution1()\n",
    "y=Solution2()\n",
    "print(x.twoSum([4,6,1,1,1,1,1,1,1,1,1],10),'\\n')\n",
    "y.twoSum([1,2,3,4,5,5],10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Reverse Integer problem\n",
    "\n",
    "class Solution1:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        if -2** 31 >= x >= 2** 31 -1:\n",
    "            return 0\n",
    "        if str(x).startswith(\"-\"):\n",
    "            result = int(str(x)[len(str(x)):0:-1])*(-1)\n",
    "        else:\n",
    "            result = int(str(x)[::-1])\n",
    "        if result >= 2**31-1 or result <= -2**31:\n",
    "            return 0\n",
    "        else:\n",
    "            return result\n",
    "        \n",
    "class Solution2:\n",
    "    def reverse(self, x: int) -> int:\n",
    "        if -2** 31 >= x >= 2** 31 -1:\n",
    "            return 0\n",
    "        if x >= 0 :\n",
    "            signal = 1 \n",
    "        else:\n",
    "            signal = -1\n",
    "        result = 0 # initialiiizes result to 0 so we can be sure \n",
    "        while(abs(x) > 0):\n",
    "            remainder = abs(x) % 10 # this returns the last digit from x\n",
    "            result = result * 10 + remainder #adds zero to the right of result\n",
    "            x = abs(x) // 10 # takes away the last digit from x\n",
    "        if signal*result >= 2**31-1 or signal*result <= -2**31:\n",
    "            return 0\n",
    "        else:\n",
    "            return signal*result\n",
    "        \n",
    "\n",
    "x = Solution1()\n",
    "y = Solution2()\n",
    "print(x.reverse(-1232))\n",
    "print(y.reverse(-1232))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Palindrome problem\n",
    "\n",
    "class Solution1:\n",
    "    def isPalindrome(self, x: int) -> bool:\n",
    "        if x < 0:\n",
    "            return False\n",
    "        reverse = 0\n",
    "        num = x\n",
    "        while num > 0:\n",
    "            remainder = num % 10 #returns last digit\n",
    "            reverse = reverse * 10 + remainder #moves to the left and adds last digit\n",
    "            num = num // 10 #takes away the last element       \n",
    "        \n",
    "        return x == reverse\n",
    "\n",
    "x = Solution1()\n",
    "x.isPalindrome(222)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Roman to Integer\n",
    "\n",
    "import re\n",
    "\n",
    "class Solution1:\n",
    "    def romanToInt(self, s: str) -> int:\n",
    "        result = 0\n",
    "        dic = {'IV':4,'IX':9,'XL':40,'XC':90,'CD':400,'CM':900,\n",
    "               'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}\n",
    "        iterator = re.finditer('|'.join(dic.keys()),s)\n",
    "        result = 0\n",
    "        for i in iterator:\n",
    "            result += dic[i.group(0)]\n",
    "        return(result)\n",
    "\n",
    "x = Solution1()\n",
    "x.romanToInt('MMMCMXCIX')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dic = {'IV':4,'IX':9,'XL':40,'XC':90,'CD':400,'CM':900,\n",
    "       'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "list(dic.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "s='MCMXCIV'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'|'.join(dic.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# approach sum problem\n",
    "# a1 and a2 are the given lists, and target is the target sum.\n",
    "# The output should be a tuple of two integers, one from each array.\n",
    "def closest_sum_pair(a1, a2, target):\n",
    "    a1_sorted = sorted(a1)\n",
    "    a2_sorted = sorted(a2)\n",
    "    i = 0\n",
    "    j = len(a2_sorted) - 1\n",
    "    smallest_diff = abs(a1_sorted[0] + a2_sorted[0] - target)\n",
    "    closest_pair = (a1_sorted[0], a2_sorted[0])\n",
    "    while i < len(a1_sorted) and j >= 0:\n",
    "        v1 = a1_sorted[i]\n",
    "        v2 = a2_sorted[j]\n",
    "        current_diff = v1 + v2 - target\n",
    "        if abs(current_diff) < smallest_diff:\n",
    "            smallest_diff = abs(current_diff)\n",
    "            closest_pair = (v1, v2)\n",
    "\n",
    "        if current_diff == 0:\n",
    "            return closest_pair\n",
    "        elif current_diff < 0:\n",
    "            i += 1\n",
    "        else:\n",
    "            j -= 1\n",
    "    return closest_pair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# NOTE: You can use the following values to test this function.\n",
    "a1 = [-1, 3, 8, 2, 9, 5]\n",
    "a2 = [4, 1, 2, 10, 5, 20]\n",
    "a_target = 24\n",
    "# closest_sum_pair(a1, a2, a_target) should return (5, 20) or (3, 20).\n",
    "b1 = [7, 4, 1, 10]\n",
    "b2 = [4, 5, 8, 7]\n",
    "b_target = 13\n",
    "# closest_sum_pair(b1, b2, b_target) should return (4,8), (7, 7), (7, 5), or (10, 4).\n",
    "c1 = [6, 8, -1, -8, -3]\n",
    "c2 = [4, -6, 2, 9, -3]\n",
    "c_target = 3\n",
    "# closest_sum_pair(c1, c2, c_target) should return (-1, 4) or (6, -3).\n",
    "d1 = [19, 14, 6, 11, -16, 14, -16, -9, 16, 13]\n",
    "d2 = [13, 9, -15, -2, -18, 16, 17, 2, -11, -7]\n",
    "d_target = -15\n",
    "# closest_sum_pair(d1, d2, d_target) should return (-16, 2) or (-9, -7)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Next Permutation\n",
    "\n",
    "# nums = [1,5,8,4,7,6,5,3,1]\n",
    "nums = [1,3,2]\n",
    "# nums = [1,2,3]\n",
    "def next_perm(nums: list[int]) -> list[int]:\n",
    "    for i in range(len(nums)-1,0,-1):\n",
    "        if nums[i] > nums[i-1]:\n",
    "            j, val = min((x for x in enumerate(nums[i:], start=i) if x[1] > nums[i-1]), key = lambda t: t[1])\n",
    "            nums[i-1], nums[j] = nums[j], nums[i-1]\n",
    "            nums[i:]=sorted(nums[i:])\n",
    "            return nums\n",
    "    nums.sort()\n",
    "    return nums\n",
    "            \n",
    "\n",
    "print(next_perm(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n",
      "0\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "# Add Two Numbers\n",
    "\n",
    "# Definitions for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "    \n",
    "    def insert_at_begining(self, val):\n",
    "        node = ListNode(val, self.head)\n",
    "        self.head = node\n",
    "        \n",
    "    def print_list(self):\n",
    "        if self.head is None:\n",
    "            print(\"Linked list is empty\")\n",
    "            return\n",
    "        llstr = ''\n",
    "        itr = self.head\n",
    "        while itr:\n",
    "            llstr = ' '.join([llstr, str(itr.val), '-->'])\n",
    "            itr = itr.next\n",
    "        print(llstr)\n",
    "                \n",
    "    def insert_at_end(self, val):\n",
    "        if self.head is None:\n",
    "            self.head = ListNode(val, None)\n",
    "        itr = self.head\n",
    "        while itr.next:\n",
    "            itr = itr.next \n",
    "        itr.next = ListNode(val, None)\n",
    "    \n",
    "    def insert_values(self, val_list):\n",
    "        self.head = None\n",
    "        for val in val_list:\n",
    "            self.insert_at_end(val)\n",
    "            \n",
    "    def get_length(self):\n",
    "        count = 0\n",
    "        itr = self.head\n",
    "        while itr:\n",
    "            count += 1\n",
    "            itr = itr.next\n",
    "        return count\n",
    "\n",
    "    def remove_at(self, index):\n",
    "        if index<0 or index>self.get_length():\n",
    "            raise Exception(\"Invalid index\")\n",
    "        if index==0:\n",
    "            self.head = self.head.next\n",
    "            return\n",
    "        count = 0\n",
    "        itr = self.head\n",
    "        while itr:\n",
    "            if count==index-1:\n",
    "                itr.next = itr.next.next\n",
    "                break\n",
    "            itr = itr.next\n",
    "            count += 1\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:\n",
    "    result_ll = ListNode()\n",
    "    cur_res_node = result_ll # note we modify result_ll as we modify cur_res_node\n",
    "    carry = 0\n",
    "    while l1 or l2 or carry: # carry is here because of edge cases as 8 + 7 that would otherwise \n",
    "        # terminate the loop \n",
    "        v1 = l1.val if l1 else 0\n",
    "        v2 = l2.val if l2 else 0\n",
    "        \n",
    "        # carry, val = divmod(val_1+val_2+carry, 10) # does the bellow at once but less clear \n",
    "        # to see\n",
    "        \n",
    "        # new digit\n",
    "        val = v1+v2+carry \n",
    "        \n",
    "        # imagine we get 15 for example, which is a 2 digit number \n",
    "        # we need to get the carry out of it!\n",
    "        carry = val // 10 # this produces de carry (whole division by 10)\n",
    "        val = val % 10 # val can be greater than 9 so to get only the 'ones digit' as \n",
    "        # each list takes a single digit, we mod by 10. (remainder of devision)\n",
    "       \n",
    "        cur_res_node.next = ListNode(val) # note we modify result_ll as we modify cur_res_node\n",
    "        \n",
    "        # update pointers\n",
    "        cur_res_node = cur_res_node.next # we lose the current information by advancing but\n",
    "        # that is saved in the result_ll\n",
    "        l1 = l1.next if l1 else None\n",
    "        l2 = l2.next if l2 else None\n",
    "    \n",
    "    return result_ll.next\n",
    "        \n",
    "        \n",
    "l1 = ListNode(2)\n",
    "l1.next = ListNode(4)\n",
    "l1.next.next = ListNode(3)\n",
    "l2 = ListNode(5)        \n",
    "l2.next = ListNode(6)\n",
    "l2.next.next = ListNode(4)\n",
    "\n",
    "print(addTwoNumbers(l1,l2).val)\n",
    "print(addTwoNumbers(l1,l2).next.val)\n",
    "print(addTwoNumbers(l1,l2).next.next.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7\n",
      "0\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode:\n",
    "    added = ListNode()\n",
    "    cur = added\n",
    "    carry = 0\n",
    "    while l1 or l2 or carry:\n",
    "        # add numbers, considering carry\n",
    "        val1 = l1.val if l1 else 0\n",
    "        val2 = l2.val if l2 else 0\n",
    "        val = val1+val2+carry\n",
    "        # carry update\n",
    "        carry = val // 10\n",
    "        # result should keep ones digit only\n",
    "        val = val % 10\n",
    "        # assign value to pointer cur\n",
    "        cur.next = ListNode(val)\n",
    "        # moving forward\n",
    "        cur = cur.next\n",
    "        l1 = l1.next if l1 else None\n",
    "        l2 = l2.next if l2 else None\n",
    "    return added.next\n",
    "    \n",
    "l1 = ListNode(2)\n",
    "l1.next = ListNode(4)\n",
    "l1.next.next = ListNode(3)\n",
    "l2 = ListNode(5)        \n",
    "l2.next = ListNode(6)\n",
    "l2.next.next = ListNode(4)\n",
    "\n",
    "print(addTwoNumbers(l1,l2).val)\n",
    "print(addTwoNumbers(l1,l2).next.val)\n",
    "print(addTwoNumbers(l1,l2).next.next.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "966 ns ± 33.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n",
      "2.71 µs ± 95.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "# 217. Contains duplicate\n",
    "\n",
    "def containsDuplicate(nums: list[int]) -> bool:\n",
    "    return True if len(nums)!=len(set(nums)) else False\n",
    "    \n",
    "\n",
    "def containsDuplicate_alt(nums: list[int]) -> bool:\n",
    "    hashset = set()\n",
    "    for n in nums:\n",
    "        if n in hashset:\n",
    "            return True\n",
    "        hashset.add(n)\n",
    "    return False\n",
    "\n",
    "%timeit containsDuplicate([1,2,3,4,5,6,7,8,9,9,10,11,12,12,13])\n",
    "%timeit containsDuplicate_alt([1,2,3,4,5,6,7,8,9,9,10,11,12,12,13])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "868 ns ± 11.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n",
      "1.04 µs ± 26.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n",
      "1.08 µs ± 32.1 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n",
      "1.34 µs ± 7.08 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n",
      "467 ns ± 15.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n",
      "2.52 µs ± 155 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n",
      "2.48 µs ± 185 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "# 242.Valid Anagram\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "def isAnagram_1(s: str, t: str) -> bool:\n",
    "    if len(s) != len(t):\n",
    "        return False\n",
    "    hashmap_s = dict()\n",
    "    hashmap_t = dict()\n",
    "    for i in s:\n",
    "        hashmap_s[i] = hashmap_s.get(i,0)+1\n",
    "    for i in t:\n",
    "        hashmap_t[i] = hashmap_t.get(i, 0)+1\n",
    "    if hashmap_s == hashmap_t:\n",
    "        return True \n",
    "    else:\n",
    "        return False\n",
    "    \n",
    "def isAnagram_2(s: str, t: str) -> bool:\n",
    "    if len(s) != len(t):\n",
    "        return False\n",
    "    hashmap_s = {}\n",
    "    hashmap_t = {}\n",
    "    for i in range(len(s)):\n",
    "        hashmap_s[s[i]] = hashmap_s.get(s[i],0)+1\n",
    "        hashmap_t[t[i]] = hashmap_t.get(t[i], 0)+1\n",
    "    if hashmap_s == hashmap_t:\n",
    "        return True \n",
    "    else:\n",
    "        return False\n",
    "    \n",
    "    \n",
    "def isAnagram_3(s: str, t: str) -> bool:\n",
    "    if len(s) != len(t):\n",
    "        return False\n",
    "    hashmap_s = dict()\n",
    "    hashmap_t = dict()\n",
    "    for i in s:\n",
    "        hashmap_s[i] = hashmap_s.get(i,0)+1\n",
    "    for i in t:\n",
    "        hashmap_t[i] = hashmap_t.get(i, 0)+1\n",
    "    for c in hashmap_s:\n",
    "        if hashmap_s[c] != hashmap_t.get(c, 0):\n",
    "            return False\n",
    "    return True\n",
    "    \n",
    "def isAnagram_4(s: str, t: str) -> bool:\n",
    "    if len(s) != len(t):\n",
    "        return False\n",
    "    hashmap_s = dict()\n",
    "    hashmap_t = dict()\n",
    "    for i in range(len(s)):\n",
    "        hashmap_s[s[i]] = hashmap_s.get(s[i],0)+1\n",
    "        hashmap_t[t[i]] = hashmap_t.get(t[i],0)+1\n",
    "    for c in hashmap_s:\n",
    "        if hashmap_s[c] != hashmap_t.get(c, 0):\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def isAnagram_5(s: str, t: str) -> bool:\n",
    "    return sorted(s) == sorted(t)\n",
    "\n",
    "def isAnagram_6(s: str, t: str) -> bool:\n",
    "    if len(s) != len(t):\n",
    "        return False\n",
    "    count_s, count_t = Counter(s), Counter(t)\n",
    "    return count_s == count_t\n",
    "\n",
    "def isAnagram_7(s: str, t: str) -> bool:\n",
    "    return Counter(s) == Counter(t)\n",
    "\n",
    "   \n",
    "%timeit isAnagram_1(\"rat\",\"car\")\n",
    "%timeit isAnagram_2(\"rat\",\"car\")\n",
    "%timeit isAnagram_3(\"rat\",\"car\")\n",
    "%timeit isAnagram_4(\"rat\",\"car\")\n",
    "%timeit isAnagram_5(\"rat\",\"car\")\n",
    "%timeit isAnagram_6(\"rat\",\"car\")\n",
    "%timeit isAnagram_7(\"rat\",\"car\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "678 ns ± 29.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n",
      "475 ns ± 26.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "# 1. Two Sum\n",
    "\n",
    "def twoSum_1(nums: list[int], target: int) -> list[int]:\n",
    "    for i in range(len(nums)):\n",
    "        diff = target-nums[i]\n",
    "        for j in range(i+1, len(nums)):\n",
    "            if nums[j] == diff:\n",
    "                return (i, j)\n",
    "            \n",
    "def twoSum_2(nums: list[int], target: int) -> list[int]:\n",
    "    # val : index this is important because we are looking for the val and returning the index\n",
    "    hashmap = {} \n",
    "    for i in range(len(nums)):\n",
    "        diff = target-nums[i]\n",
    "        if diff in hashmap:\n",
    "            return(hashmap[diff], i)\n",
    "        hashmap[nums[i]] = i\n",
    "    return\n",
    "\n",
    "nums = [3,2,4]\n",
    "target = 6\n",
    "\n",
    "%timeit twoSum_1(nums, target)\n",
    "%timeit twoSum_2(nums, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]\n",
      "[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]\n",
      "6.24 µs ± 409 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n",
      "3.16 µs ± 266 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "# 49. Group Anagrams\n",
    "from collections import defaultdict\n",
    "\n",
    "def groupAnagrams_1(strs: list[str]) -> list[list[str]]:\n",
    "    hashmap = defaultdict(list) # to avoid edge case of list not existing inside the map\n",
    "    for i in range(len(strs)):\n",
    "        # make 26 elem empty array\n",
    "        count = 26*[0]\n",
    "        for j in strs[i]:\n",
    "            # here we convert \"a\" to 0, etc and increase the corresponding elem in array\n",
    "            count[ord(j)-97] += 1\n",
    "        # ....... (turned to tuple because list is mutable)\n",
    "        hashmap[tuple(count)] += [strs[i]] \n",
    "    return list(hashmap.values())\n",
    "\n",
    "def groupAnagrams_2(strs: list[str]) -> list[list[str]]:\n",
    "    hashmap = defaultdict(list) # to avoid edge case of list not existing inside the map\n",
    "    for i in range(len(strs)):\n",
    "        srt_wrd = sorted(strs[i]) # using the sorted word as a key for the word\n",
    "        hashmap[tuple(srt_wrd)] += [strs[i]] # adding to the map\n",
    "    return list(hashmap.values())\n",
    "\n",
    "print(groupAnagrams_1([\"eat\",\"tea\",\"tan\",\"ate\",\"nat\",\"bat\"]))\n",
    "print(groupAnagrams_2([\"eat\",\"tea\",\"tan\",\"ate\",\"nat\",\"bat\"]))\n",
    "%timeit groupAnagrams_1([\"eat\",\"tea\",\"tan\",\"ate\",\"nat\",\"bat\"])\n",
    "%timeit groupAnagrams_2([\"eat\",\"tea\",\"tan\",\"ate\",\"nat\",\"bat\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2]\n",
      "[1, 2]\n",
      "[1, 2]\n",
      "[1, 2]\n",
      "[1, 2]\n",
      "[1, 2]\n",
      "[1, 2]\n",
      "6.93 µs ± 830 ns per loop (mean ± std. dev. of 1000 runs, 100,000 loops each)\n",
      "5.08 µs ± 132 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n",
      "9.25 µs ± 197 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n",
      "7.86 µs ± 192 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n",
      "2.96 µs ± 97.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n",
      "5.57 µs ± 189 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n",
      "4.75 µs ± 166 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "# 347. Top K Frequent Elements\n",
    "\n",
    "from collections import Counter\n",
    "import heapq\n",
    "\n",
    "def topKFrequent_1(nums: list[int], k: int) -> list[int]:\n",
    "    return [x[0] for x in Counter(nums).most_common(k)]\n",
    "    \n",
    "def topKFrequent_2(nums: list[int], k: int) -> list[int]:\n",
    "    if k == len(nums):\n",
    "        return nums\n",
    "    count = {}\n",
    "    for n in nums:\n",
    "        count[n] = count.get(n, 0) + 1\n",
    "    # will heapify count, iterate over its keys and sort \n",
    "    # them according to the get function\n",
    "    # (which returns values, so sorting by value)\n",
    "    return heapq.nlargest(k,count.keys(), key=count.get)\n",
    "\n",
    "def topKFrequent_3(nums: list[int], k: int) -> list[int]:\n",
    "    count = {}\n",
    "    freq = [[] for i in range(len(nums)+1)]\n",
    "    # counting # times each number in nums occurs \n",
    "    for n in nums:\n",
    "        count[n] = count.get(n, 0) + 1\n",
    "    # n for number c for count\n",
    "    for n, c in count.items():\n",
    "    # the count is the index\n",
    "        freq[c].append(n)\n",
    "    res =[]\n",
    "    for i in range(len(freq)-1,0,-1):\n",
    "        for n in freq[i]:\n",
    "            res.append(n)\n",
    "            if len(res) ==k:\n",
    "                return res\n",
    "    \n",
    "\n",
    "def topKFrequent_4(nums: list[int], k: int) -> list[int]:\n",
    "    # adapted bucket-sort\n",
    "    # counting # times each number in nums occurs \n",
    "    count = Counter(nums)\n",
    "    freq = [[] for i in range(len(nums)+1)]\n",
    "    # n for number c for count\n",
    "    for n, c in count.items():\n",
    "    # the count is the index\n",
    "        freq[c].append(n)\n",
    "    res =[]\n",
    "    for i in range(len(freq)-1,0,-1):\n",
    "        for n in freq[i]:\n",
    "            res.append(n)\n",
    "            if len(res) ==k:\n",
    "                return res\n",
    "            \n",
    "            \n",
    "def topKFrequent_5(nums: list, k: int) -> list:\n",
    "    counts = []\n",
    "    for i in set(nums):\n",
    "        counts.append((i, nums.count(i)))\n",
    "    counts = sorted(counts, key=lambda x: x[1], reverse=True)\n",
    "    return [i[0] for i in counts[:k]]\n",
    "\n",
    "\n",
    "def topKFrequent_6(nums: list, k: int) -> list:\n",
    "    d = {}\n",
    "    for i in nums:\n",
    "        if i in d:\n",
    "            d[i]+=1\n",
    "        else:\n",
    "            d[i]=1\n",
    "    d_sort = dict(sorted(d.items(), key = lambda item : item[1], reverse = True))\n",
    "    final = list(d_sort.keys())\n",
    "    return final[:k]\n",
    "\n",
    "\n",
    "def topKFrequent_7(nums: list, k: int) -> list: \n",
    "    # O(1) time \n",
    "    if k == len(nums):\n",
    "        return nums\n",
    "    \n",
    "    # 1. build hash map : character and how often it appears\n",
    "    # O(N) time\n",
    "    count = Counter(nums)   \n",
    "    # 2-3. build max heap of top k frequent elements and\n",
    "    # convert it into an output array\n",
    "    # O(N log k) time\n",
    "    return heapq.nlargest(k, count.keys(), key=count.get)         \n",
    "\n",
    "    \n",
    "print(topKFrequent_1([1,1,1,2,2,3]*10,2))    \n",
    "print(topKFrequent_2([1,1,1,2,2,3]*10,2))\n",
    "print(topKFrequent_3([1,1,1,2,2,3]*10,2))\n",
    "print(topKFrequent_4([1,1,1,2,2,3]*10,2))\n",
    "print(topKFrequent_5([1,1,1,2,2,3]*10,2))\n",
    "print(topKFrequent_6([1,1,1,2,2,3]*10,2))\n",
    "print(topKFrequent_7([1,1,1,2,2,3]*10,2))\n",
    "\n",
    "%timeit topKFrequent_2([1,1,1,2,2,3]*10,2)\n",
    "%timeit topKFrequent_1([1,1,1,2,2,3]*10,2)\n",
    "%timeit topKFrequent_3([1,1,1,2,2,3]*10,2)\n",
    "%timeit topKFrequent_4([1,1,1,2,2,3]*10,2)\n",
    "%timeit topKFrequent_5([1,1,1,2,2,3]*10,2)\n",
    "%timeit topKFrequent_6([1,1,1,2,2,3]*10,2)\n",
    "%timeit topKFrequent_7([1,1,1,2,2,3]*10,2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[24, 12, 8, 6]\n",
      "[24, 12, 8, 6]\n",
      "2.48 µs ± 119 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)\n",
      "1.46 µs ± 50.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)\n"
     ]
    }
   ],
   "source": [
    "# 238. Product of Array Except Self\n",
    "\n",
    "def productExceptSelf_1(nums: list[int]) -> list[int]:\n",
    "    \n",
    "    def arr_elem_mult(arr: list[int]) -> int:\n",
    "        result = 1\n",
    "        for j in arr:\n",
    "            result = result*j\n",
    "        return result\n",
    "            \n",
    "    ans = []\n",
    "    for i in range(len(nums)):\n",
    "        popped = nums.pop(i)\n",
    "        ans.append(arr_elem_mult(nums))\n",
    "        nums.insert(i, popped)\n",
    "    return ans\n",
    "\n",
    "def productExceptSelf_2(nums: list[int]) -> list[int]:            \n",
    "    ans = [1]*len(nums)\n",
    "    pre = 1\n",
    "    for i in range(len(nums)):\n",
    "        ans[i] = pre\n",
    "        pre *= nums[i]\n",
    "    post = 1\n",
    "    for i in range(len(nums)-1,-1,-1):\n",
    "        ans[i] *= post\n",
    "        post *= nums[i]\n",
    "    return ans\n",
    "    \n",
    "print(productExceptSelf_1([1,2,3,4]))\n",
    "print(productExceptSelf_2([1,2,3,4]))\n",
    "%timeit productExceptSelf_1([1,2,3,4])\n",
    "%timeit productExceptSelf_2([1,2,3,4])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "board = \\\n",
    "[[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"]\n",
    ",[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"]\n",
    ",[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"]\n",
    ",[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"]\n",
    ",[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"]\n",
    ",[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"]\n",
    ",[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"]\n",
    ",[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"]\n",
    ",[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]\n",
    "\n",
    "def isValidSudoku_1(board: list[list[str]]) -> bool:\n",
    "    rows = defaultdict(set)\n",
    "    cols = defaultdict(set)\n",
    "    squares = defaultdict(set) # key = (r/3, c/3)\n",
    "    for r in range(9):\n",
    "        for c in range(9):\n",
    "            if board[r][c] == \".\":\n",
    "                continue\n",
    "            # Validation\n",
    "            if board[r][c] in rows[r] or \\\n",
    "               board[r][c] in cols[c] or \\\n",
    "               board[r][c] in squares[(r//3,c//3)]:\n",
    "                   return False\n",
    "        rows.add(board[r][c])\n",
    "        cols.add(board[r][c])\n",
    "        squares.add()\n",
    "print(isValidSudoku_1(board))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "2//3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(range(1,10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lst_2 in range(1,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "ename": "ValueError",
     "evalue": "invalid literal for int() with base 10: '.'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mValueError\u001b[0m                                Traceback (most recent call last)",
      "\u001b[1;32m/home/marc/Dropbox/Personal/CODDING/misc/algorithmic_problems/L33tcode_problems.ipynb Cell 27'\u001b[0m in \u001b[0;36m<cell line: 1>\u001b[0;34m()\u001b[0m\n\u001b[0;32m----> <a href='vscode-notebook-cell:/home/marc/Dropbox/Personal/CODDING/misc/algorithmic_problems/L33tcode_problems.ipynb#ch0000027?line=0'>1</a>\u001b[0m \u001b[39mint\u001b[39;49m(\u001b[39m\"\u001b[39;49m\u001b[39m.\u001b[39;49m\u001b[39m\"\u001b[39;49m)\n",
      "\u001b[0;31mValueError\u001b[0m: invalid literal for int() with base 10: '.'"
     ]
    }
   ],
   "source": [
    "int(\".\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "36b6448fd9a40bab90f00df4b24497c14bd71539231631101dd5e21975329f0e"
  },
  "kernelspec": {
   "display_name": "Python 3.9.12 ('stats')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}