Practice DSA

n_queens.py

class Solution:
  def __init__(self):
    self.solve_count = 0

  def solveNQueens(self, n: int) -> list[list[str]]:
    # Check if queen at row and columns is safe from other queens
    def issafe(r,c):
      n = len(board)
      for i in range(n):
        # Check Queen present at upper direction (same column)
        if board[i][c] == 'Q':
          return False
        # Check Queen is present at left upper diagonal direction
        if r - i >= 0 and c - i >= 0 and board[r-i][c-i] == 'Q':
          return False
        # Check Queen is present at right upper diagonal direction
        if r - i >= 0 and c + i < n and board[r-i][c+i] == 'Q':
          return False
      return True

    # Recursive method
    # Starts from row 0 and iterates all the columns
    #
    def solve(r):
      n = len(board)
      self.solve_count += 1
      # If row is at max, then add the solution to ANS and print current board
      if r == n:
        print(board)
        ans.append(["".join(i) for i in board])
        return

      # Iterate column by colum
      for c in range(0,n):
        # print(r,c)
        # If queen is not safe, then move back to previous row and change queen's column. Then check for safety
        if issafe(r,c):
          # If Queen is safe, then place the queen. Now, move to next row
          board[r][c] = 'Q'
          solve(r+1)
          # Remove the queen
          board[r][c] = '.'

    # Create Empty board
    board = [['.']*n for i in range(n)]
    # Collect all possible answerws
    ans =[]
    # start with 0th row
    solve(0)
    # At the very end, the board will be clear
    print(board)

    print(self.solve_count)
    return ans

s = Solution()
s.solveNQueens(8)

practice.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "3223ed8b-112d-40ca-8a1c-4661c60d1569",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 False\n",
      "2 True\n",
      "3 True\n",
      "4 False\n",
      "5 True\n",
      "6 False\n",
      "7 True\n",
      "8 False\n",
      "9 False\n",
      "10 False\n",
      "11 True\n",
      "12 False\n",
      "13 True\n",
      "14 False\n",
      "15 False\n",
      "16 False\n",
      "17 True\n",
      "18 False\n",
      "19 True\n",
      "20 False\n",
      "21 False\n",
      "22 False\n",
      "23 True\n",
      "24 False\n"
     ]
    }
   ],
   "source": [
    "# Find the prime number. Optimized version\n",
    "import math\n",
    "\n",
    "def is_prime(n):\n",
    "    if n == 1:\n",
    "        return False\n",
    "    if n == 2:\n",
    "        return True\n",
    "    if n > 2 and n % 2 == 0:\n",
    "        return False\n",
    "\n",
    "    max_divisor = math.floor(math.sqrt(n))\n",
    "    for d in range(2, 1 + max_divisor):\n",
    "        if n % d == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "\n",
    "for i in range(1, 25):\n",
    "    print(i, is_prime(i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "id": "796a665b-eafa-461e-a6f6-a73fb695d6a7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "8\n",
      "55\n",
      "55\n",
      "55\n"
     ]
    }
   ],
   "source": [
    "# Fibonacci Number\n",
    "\n",
    "# Recursive version\n",
    "def fib(n):\n",
    "    if n == 0 or n == 1:\n",
    "        return n\n",
    "    return fib(n - 1) + fib(n - 2)\n",
    "\n",
    "# with additional variable\n",
    "def fib_iterate(n):\n",
    "    a, b = 0, 1\n",
    "    for i in range(0, n):\n",
    "        temp = a\n",
    "        a = b\n",
    "        b = temp + b\n",
    "\n",
    "    return a\n",
    "\n",
    "# without additional variable\n",
    "def f(n):\n",
    "    a, b = 0, 1\n",
    "    for i in range(0, n):\n",
    "        a, b = b, a + b\n",
    "    return a\n",
    "\n",
    "print(fib(5))\n",
    "print(fib(6))\n",
    "print(fib(10))\n",
    "\n",
    "print(fib_iterate(10))\n",
    "print(f(10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "5a935dec-f5f3-4421-a2d2-f69093bba0d3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "temp = list(range(n))\n",
    "print(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "091a9128-4151-420c-8781-d8d74f0a3bc2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6]\n"
     ]
    }
   ],
   "source": [
    "# Remove duplicates from Sorted array\n",
    "def remove_duplicates(arr):\n",
    "    arr.sort()\n",
    "    n = len(arr)\n",
    "    j = 0\n",
    "    temp = [0] * n\n",
    "\n",
    "    # Iterate till n - 2 elements\n",
    "    for i in range(0, n - 1):\n",
    "        # If elements are different, then add to new array\n",
    "        if arr[i] != arr[i + 1]:\n",
    "            temp[j] = arr[i]\n",
    "            j += 1\n",
    "            \n",
    "    temp[j]= arr[n - 1]\n",
    "    j += 1\n",
    "\n",
    "    # return temp[: j]\n",
    "    for i in range(0, j):\n",
    "        arr[i] = temp[i]\n",
    "    # print(arr)\n",
    "    # print(temp)\n",
    "\n",
    "    return arr[:j]\n",
    "\n",
    "\n",
    "arr = [1, 2, 2, 3, 4, 4, 4, 5, 5, 5, 6]\n",
    "print(remove_duplicates(arr))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "4a23041c-7382-4b9b-8343-fca78cb2d086",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sum of the digits\n",
    "import math\n",
    "def sum_of_digits(n):\n",
    "    sum = 0\n",
    "    while n > 0:\n",
    "        sum += n % 10\n",
    "        n = math.floor(n / 10)\n",
    "\n",
    "    return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "8efcb6b1-9b7c-46db-b3c2-ebe9882fc8f1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14\n",
      "6\n",
      "21\n"
     ]
    }
   ],
   "source": [
    "print(sum_of_digits(239))\n",
    "print(sum_of_digits(123))\n",
    "print(sum_of_digits(123456))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "bbf465b4-265f-450c-9623-ac17f50d1b6b",
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "class LinkedList:\n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        self.tail = None\n",
    "\n",
    "    # Push to the front of the list\n",
    "    def push(self, value):\n",
    "        new_node = Node(value)\n",
    "        new_node.next = self.head\n",
    "        if self.tail == None:\n",
    "            self.tail = self.head\n",
    "        self.head = new_node\n",
    "\n",
    "    # Insert to the end of the list\n",
    "    def insert(self, value):\n",
    "        new_node = Node(value)\n",
    "        if self.head == None:\n",
    "            self.head = new_node\n",
    "        if self.tail != None:\n",
    "            self.tail.next = new_node    \n",
    "        self.tail = new_node\n",
    "\n",
    "    def print_list(self):\n",
    "        n = self.head\n",
    "        while n is not None:\n",
    "            print(n.value, end=' ')\n",
    "            n = n.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "5629b604-79b3-4ae3-afcd-56171534201e",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "642\n",
      "6 4 2 "
     ]
    }
   ],
   "source": [
    "## Add two numbers represented by Linked List\n",
    "\n",
    "def add_two_lists(first, second):\n",
    "    num1, num2 = 0, 0\n",
    "    while first.head:\n",
    "        num1 = num1 * 10 + first.head.value\n",
    "        first.head = first.head.next\n",
    "    num2 = 0\n",
    "    while second.head:\n",
    "        num2 = num2 * 10 + second.head.value\n",
    "        second.head = second.head.next\n",
    "    sum = num1 + num2\n",
    "    print(sum)\n",
    "    ans = LinkedList()\n",
    "    while sum > 0:\n",
    "        val = sum % 10\n",
    "        sum = sum // 10\n",
    "        ans.push(val)\n",
    "    return ans\n",
    "        \n",
    "\n",
    "list_a = LinkedList()\n",
    "list_a.push(1)\n",
    "list_a.push(2)\n",
    "list_a.push(3)\n",
    "\n",
    "# list_a.print_list()\n",
    "\n",
    "list_b = LinkedList()\n",
    "list_b.push(1)\n",
    "list_b.push(2)\n",
    "list_b.push(3)\n",
    "# list_b.print_list()\n",
    "\n",
    "ans = add_two_lists(list_a, list_b)\n",
    "ans.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "e076f11d-98d4-400a-b1bf-908db290db9f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 5 6 \n",
      "4\n",
      "4\n",
      "None\n",
      "1 2 3 4 5 6 "
     ]
    }
   ],
   "source": [
    "# Middle of Linked List\n",
    "# Two pointer\n",
    "def middle_of_linked_list(list):\n",
    "    slow = list.head\n",
    "    fast = list.head\n",
    "\n",
    "    while fast != None and fast.next != None:\n",
    "        # Now returns second middle node\n",
    "        # if fast.next.next != None:\n",
    "            # slow = slow.next\n",
    "        slow = slow.next\n",
    "        fast = fast.next.next\n",
    "\n",
    "    return slow.value\n",
    "\n",
    "def k_from_last(list, k):\n",
    "    fast = list.head\n",
    "    slow = list.head\n",
    "    count = 1\n",
    "    while fast.next != None:\n",
    "        if count >= k:\n",
    "            slow = slow.next\n",
    "        fast = fast.next\n",
    "        count += 1\n",
    "    if count < k:\n",
    "        return None\n",
    "    return slow.value\n",
    "\n",
    "list_a = LinkedList()\n",
    "\n",
    "for i in range(6, 0, -1):\n",
    "    list_a.push(i)\n",
    "\n",
    "list_a.print_list()\n",
    "print()\n",
    "print(middle_of_linked_list(list_a))\n",
    "print(k_from_last(list_a, 3))\n",
    "print(k_from_last(list_a, 13))\n",
    "\n",
    "list_a = LinkedList()\n",
    "\n",
    "for i in range(1, 7):\n",
    "    list_a.insert(i)\n",
    "\n",
    "list_a.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cee9f66e-6f01-41e7-bd7b-0c8d45490167",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sum of two linked lists using Stack\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "005086fa-b2a8-45ba-b08f-04168766c45d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# HashTable\n",
    "## Constraints and assumptions\n",
    "# - For simplicity, are the keys integers only?\n",
    "# Yes\n",
    "# - For collision resolution, can we use chaining?\n",
    "# Yes\n",
    "# - Do we have to worry about load factors?\n",
    "# No\n",
    "# - Can we assume inputs are valid or do we have to validate them?\n",
    "# Assume they're valid\n",
    "# - Can we assume this fits memory?\n",
    "# Yes\n",
    "\n",
    "class Item:\n",
    "    def __init__(self, key, val):\n",
    "        self.key = key\n",
    "        self.val = val\n",
    "\n",
    "class HashTable(object):\n",
    "    def __init__(self, size):\n",
    "        self.size = size\n",
    "        self.table = [[] for _ in range(size)]\n",
    "\n",
    "    def _hash_function(self, key):\n",
    "        return key % self.size\n",
    "\n",
    "    def get(self, key):\n",
    "        hash_index = self._hash_function(key)\n",
    "        for item in self.table[hash_index]:\n",
    "            if item.key == key:\n",
    "                return item.val\n",
    "        raise KeyError('Key not found')\n",
    "\n",
    "    def set(self, key, value):\n",
    "        hash_index = self._hash_function(key)\n",
    "        for item in self.table[hash_index]:\n",
    "            if item.key == key:\n",
    "                item.val = value\n",
    "                return\n",
    "        self.table[hash_index].append(Item(key, value))\n",
    "\n",
    "    def remove(self, key):\n",
    "        hash_index = self._hash_function(key)\n",
    "        for index, item in enumerate(self.table[hash_index]):\n",
    "            if item.key == key:\n",
    "                del self.table[hash_index][index]\n",
    "                return\n",
    "        raise KeyError('Key not found')\n",
    "\n",
    "    # def get_keys(self):\n",
    "    # def get_values(self):\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "777c4e73-797b-44e8-b643-4eddb98b20e0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[], [], [], [], [], [], [], [], [], []]\n"
     ]
    }
   ],
   "source": [
    "# Bloom Filters\n",
    "# Consistent Hashing\n",
    "# Sorting Algorithms\n",
    "\n",
    "# GUID - 12 bytes, 20 chars, configuration free, sortable\n",
    "    # Xid is using Mongo Object ID algorithm to generate globally unique ids with a different serialization (base64) to make it shorter when transported as a string: https://docs.mongodb.org/manual/reference/object-id/\n",
    "    \n",
    "    # 4-byte value representing the seconds since the Unix epoch,\n",
    "    # 3-byte machine identifier,\n",
    "    # 2-byte process id, and\n",
    "    # 3-byte counter, starting with a random value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "4da298fa-d2b1-42aa-ae11-980e991ae774",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n",
      "1242134124\n",
      "4523599088269309470\n"
     ]
    }
   ],
   "source": [
    "print(hash(10))\n",
    "print(hash(1242134124))\n",
    "print(hash('valar'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "id": "bfa1515f-4a57-46a1-b9ca-bec6c5c5e32f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "7\n",
      "-1\n"
     ]
    }
   ],
   "source": [
    "# Coin Change - Dynamic Programming - Bottom-up approach\n",
    "# Memoise the solution of sub-problems and use them\n",
    "# https://www.interviewcake.com/concept/python/bottom-up?#related_questions\n",
    "\n",
    "# Calculate coins change for the amount-1, amount-2,....,1\n",
    "# Calculate the minimum coin count\n",
    "def coin_change(coins, amount):\n",
    "    # Memoise storage\n",
    "    dp = [0] + [amount + 1] * amount\n",
    "\n",
    "    for i in range(1, amount + 1):\n",
    "        for coin in coins:\n",
    "            if i - coin >= 0:\n",
    "                dp[i] = min(dp[i], dp[i - coin] + 1)\n",
    "\n",
    "    if dp[amount] != amount + 1:\n",
    "        return dp[amount]\n",
    "    return -1\n",
    "\n",
    "\n",
    "print(coin_change([ 3, 4, 5], 7))\n",
    "print(coin_change([1], 7))\n",
    "print(coin_change([2], 7))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "7d9dfe39-191b-411b-a1bd-329902306db7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "120\n",
      "3628800\n"
     ]
    }
   ],
   "source": [
    "def product_1_to_n(n):\n",
    "    product = 1\n",
    "\n",
    "    for i in range(1, n + 1):\n",
    "        product *= i\n",
    "\n",
    "    print(product)\n",
    "\n",
    "product_1_to_n(3)\n",
    "product_1_to_n(5)\n",
    "product_1_to_n(10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "deaf0500-931f-4a03-84a8-6571cc94856b",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "555\n",
      "1800\n"
     ]
    }
   ],
   "source": [
    "# Cake Theif\n",
    "# https://coursehunters.online/t/the-interview-cake-course-6-dynamic-programming-and-recursion/3183\n",
    "\n",
    "# You are a renowned thief who has recently switched from stealing precious metals to stealing cakes because of the insane profit margins. You end up hitting the jackpot, breaking into the world’s largest privately owned stock of cakes—the vault of the Queen of England.\n",
    "\n",
    "# While Queen Elizabeth has a limited number of types of cake, she has an unlimited supply of each type.\n",
    "\n",
    "# Each type of cake has a weight and a value, stored in a tuple with two indices:\n",
    "\n",
    "# An integer representing the weight of the cake in kilograms\n",
    "# An integer representing the monetary value of the cake in British shillings\n",
    "# For example:\n",
    "\n",
    "# # Weighs 7 kilograms and has a value of 160 shillings\n",
    "# (7, 160)\n",
    "\n",
    "# # Weighs 3 kilograms and has a value of 90 shillings\n",
    "# (3, 90)\n",
    "\n",
    "# the unbounded knapsack problem\n",
    "\n",
    "def max_duffel_bag_value(cake_tuples, weight_capacity):\n",
    "    # We make a list to hold the maximum possible value at every\n",
    "    # duffel bag weight capacity from 0 to weight_capacity\n",
    "    # starting each index with value 0\n",
    "    max_values_at_capacities = [0] * (weight_capacity + 1)\n",
    "\n",
    "    for current_capacity in range(weight_capacity + 1):\n",
    "        # Set a variable to hold the max monetary value so far\n",
    "        # for current_capacity\n",
    "        current_max_value = 0\n",
    "\n",
    "        for cake_weight, cake_value in cake_tuples:\n",
    "            # If a cake weighs 0 and has a positive value the value of our duffel bag is infinite!\n",
    "            if cake_weight == 0 and cake_value != 0:\n",
    "                return float('inf')\n",
    "\n",
    "            # If the current cake weighs as much or less than the\n",
    "            # current weight capacity it's possible taking the cake\n",
    "            # would get a better value\n",
    "            if cake_weight <= current_capacity:\n",
    "\n",
    "                # So we check: should we use the cake or not?\n",
    "                # If we use the cake, the most kilograms we can include in\n",
    "                # addition to the cake we're adding is the current capacity\n",
    "                # minus the cake's weight. We find the max value at that\n",
    "                # integer capacity in our list max_values_at_capacities\n",
    "                max_value_using_cake = (cake_value + max_values_at_capacities[current_capacity - cake_weight])\n",
    "\n",
    "                # Now we see if it's worth taking the cake. how does the\n",
    "                # value with the cake compare to the current_max_value?\n",
    "                current_max_value = max(max_value_using_cake, current_max_value)\n",
    "\n",
    "        # Add each capacity's max value to our list so we can use them\n",
    "        # when calculating all the remaining capacities\n",
    "        max_values_at_capacities[current_capacity] = current_max_value\n",
    "\n",
    "    return max_values_at_capacities[weight_capacity]\n",
    "\n",
    "print(max_duffel_bag_value([(7, 160), (3, 90), (2, 15)], 20))\n",
    "print(max_duffel_bag_value([(7, 160), (3, 90), (2, 15), (1, 90), (50, 200)], 20))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "fda3966c-1cf2-44c3-baae-4e0c985790e0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[]\n",
      "[1, 2]\n",
      "[0, 2]\n"
     ]
    }
   ],
   "source": [
    "# Two sum. Returns index of items\n",
    "# Using hash to store index of previously found number\n",
    "def two_sum(list, target):\n",
    "    dic = {}\n",
    "    for i, num in enumerate(list):\n",
    "        temp = target - num\n",
    "        if temp in dic:\n",
    "            return [dic[temp], i]\n",
    "        dic[num] = i\n",
    "    return []\n",
    "\n",
    "\n",
    "print(two_sum([2, 7, 11, 15], 10))\n",
    "print(two_sum([3, 2,4], 6))\n",
    "print(two_sum([3, 2, 3], 6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "44b09a56-7d76-488a-8de2-f9267a575c49",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "True\n",
      "False\n",
      "True\n",
      "True\n",
      "True\n",
      "False\n",
      "<__main__.TrieNode object at 0x106952670>\n"
     ]
    }
   ],
   "source": [
    "# Trie\n",
    "# WordDictionary\n",
    "# Web Crawler application\n",
    "# Website visitor\n",
    "# AutoCompletion dropdown\n",
    "\n",
    "class TrieNode:\n",
    "    def __init__(self):\n",
    "        self.childrens = {}\n",
    "        self.leaf = False\n",
    "\n",
    "# In this Trie, intermediate Nodes also have leaf=True. This is because we need to find the exact words.\n",
    "class WordDictionary:\n",
    "    def __init__(self):\n",
    "        self.root = TrieNode()\n",
    "\n",
    "    def add_word(self, word):\n",
    "        if len(word) < 1 or len(word) > 25:\n",
    "            return \n",
    "\n",
    "        temp = self.root\n",
    "        for c in word:\n",
    "            if c not in temp.childrens:\n",
    "                temp.childrens[c] = TrieNode()\n",
    "            temp = temp.childrens[c]\n",
    "        temp.leaf = True\n",
    "\n",
    "    def search(self, word):\n",
    "        temp = self.root\n",
    "        print(self.dfs(temp, word, 0))\n",
    "\n",
    "    def prefix_search(self, word):\n",
    "        temp = self.root\n",
    "        print(self.dfs(temp, word, 0, True))\n",
    "        \n",
    "    def dfs(self, node, word, index, prefix_match = False):\n",
    "        if len(word) > index and word[index] in node.childrens:\n",
    "            child = node.childrens[word[index]]\n",
    "            if (child.leaf == True or prefix_match == True) and len(word) - 1 == index:\n",
    "                return True\n",
    "            return self.dfs(child, word, index + 1, prefix_match)\n",
    "        return False\n",
    "\n",
    "\n",
    "wordDictionary = WordDictionary()\n",
    "wordDictionary.add_word(\"bad\")\n",
    "wordDictionary.add_word(\"badass\")\n",
    "wordDictionary.add_word(\"dad\")\n",
    "wordDictionary.add_word(\"mad\")\n",
    "\n",
    "wordDictionary.search(\"pad\")\n",
    "wordDictionary.search(\"bad\")\n",
    "wordDictionary.search(\"badas\")\n",
    "wordDictionary.search(\"badass\")\n",
    "wordDictionary.search(\"mad\")\n",
    "\n",
    "wordDictionary.prefix_search(\"b\")\n",
    "wordDictionary.prefix_search(\"badasss\")\n",
    "print(wordDictionary.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "945383eb-491c-4594-9579-1412ed04d8cd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4]\n",
      "[0, 1, 2, 3]\n",
      "\n",
      "[0, 1, 2, 3, 4, '_', '_', '_', '_', '_']\n",
      "5\n",
      "\n",
      "[0, 1, 2, 3, '_', '_', '_', '_', '_', '_']\n",
      "4\n",
      "[0, 1]\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Remove Duplicates from the Sorted Array\n",
    "\n",
    "class Solution:\n",
    "    def remove_duplicates(self, nums: list[int]) -> int:\n",
    "        unique = []\n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] != nums[i + 1]:\n",
    "                unique.append(nums[i])\n",
    "                \n",
    "        unique.append(nums[i + 1])\n",
    "    \n",
    "        print(unique)\n",
    "        return unique\n",
    "\n",
    "    def remove_duplicates_in_place(self, nums: list[int]) -> int:\n",
    "        unique = 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            if nums[i] != nums[i + 1]:\n",
    "                nums[unique] = nums[i]\n",
    "                unique += 1\n",
    "\n",
    "        nums[unique] = nums[-1]\n",
    "        unique += 1\n",
    "        for i in range(unique, len(nums)):\n",
    "            nums[i] = '_'\n",
    "\n",
    "        print(nums)\n",
    "        return unique\n",
    "                \n",
    "\n",
    "s = Solution()\n",
    "s.remove_duplicates([0,0,1,1,1,2,2,3,3,4])\n",
    "s.remove_duplicates([0,0,1,1,1,2,2,3,3])\n",
    "\n",
    "print()\n",
    "print(s.remove_duplicates_in_place([0,0,1,1,1,2,2,3,3,4]))\n",
    "print()\n",
    "print(s.remove_duplicates_in_place([0,0,1,1,1,2,2,3,3,3]))\n",
    "s.remove_duplicates_in_place([0,1])\n",
    "print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "f424b521-ca16-4352-ab8e-c5d54f5aabdc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 5, 6, 7, 1, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "# Rotate Array using Recursion. In-place rotation\n",
    "\n",
    "# Array rotation using recusion\n",
    "def rotate_array(arr, k):\n",
    "    if k == 0:\n",
    "        return arr\n",
    "\n",
    "    temp = arr[-1]\n",
    "    n = len(arr)\n",
    "    for i in range(n - 1, 0, -1):\n",
    "        arr[i] = arr[i - 1]\n",
    "    arr[0] = temp\n",
    "\n",
    "    return rotate_array(arr, k - 1)\n",
    "\n",
    "    \n",
    "print(rotate_array([1,2,3,4,5,6,7], 4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "f07d384b-287b-4ba0-9bd3-643c03724eea",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "4\n",
      "2\n",
      "4\n",
      "4\n",
      "2\n",
      "0\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "# Find a Single number from an array with pairs\n",
    "# Sort, then compare next-next elements.\n",
    "def single_number(arr):\n",
    "    arr.sort()\n",
    "    if len(arr) == 1:\n",
    "        return arr[0]\n",
    "    # Iterate using 2 steps at a time\n",
    "    for i in range(0, len(arr) - 1, 2):\n",
    "        if arr[i] != arr[i + 1]:\n",
    "            return arr[i]\n",
    "    return arr[-1]\n",
    "\n",
    "# Using XOR bitwise operation. 4^4 is 0. Finally the Single number will be in the result\n",
    "def single_number_xor(arr):\n",
    "    if len(arr) == 1:\n",
    "        return arr[0]\n",
    "    xor = 0\n",
    "    for i in range(len(arr)):\n",
    "        xor = xor ^ arr[i]\n",
    "\n",
    "    return xor\n",
    "\n",
    "print(single_number([4,1,2,1,2]))\n",
    "print(single_number([4]))\n",
    "print(single_number([1, 2, 1]))\n",
    "\n",
    "print(single_number_xor([4,1,2,1,2]))\n",
    "print(single_number_xor([4]))\n",
    "print(single_number_xor([1, 2, 1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "3dfa83a2-2c5f-4fff-ba5d-6bdba8216773",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3, 12, 0, 0]\n",
      "[0]\n",
      "[1, 0]\n"
     ]
    }
   ],
   "source": [
    "# Move zeros to the end\n",
    "# Using a two-pointer approach. Compare next-next elements and discard 0 in the middle. Then append at the end\n",
    "def move_zeroes(nums):\n",
    "    non_zero = 0\n",
    "    n = len(nums)\n",
    "    for i in range(n):\n",
    "        if nums[i] != 0:\n",
    "            nums[non_zero] = nums[i]\n",
    "            non_zero += 1\n",
    "\n",
    "    for i in range(non_zero, n):\n",
    "        nums[i] = 0\n",
    "    return nums\n",
    "\n",
    "print(move_zeroes([0,1,0,3,12]))\n",
    "print(move_zeroes([0]))\n",
    "print(move_zeroes([0,1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "7106dec8-9c59-438c-a74c-62ff6cd1c697",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 4]\n",
      "[1, 3, 0]\n",
      "[1, 0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "# Plus one\n",
    "def plusOne(digits):\n",
    "        \n",
    "    number = 0\n",
    "    for i in range(len(digits)):\n",
    "        number = (number * 10) + digits[i]\n",
    "        \n",
    "    number += 1\n",
    "    \n",
    "    x = []\n",
    "    while number > 0:\n",
    "        x.insert(0, number % 10)\n",
    "        number = number // 10\n",
    "        \n",
    "    return x\n",
    "\n",
    "print(plusOne([1, 2, 3]))\n",
    "print(plusOne([1, 2, 9]))\n",
    "print(plusOne([9, 9, 9]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "7faecd67-3247-4a2e-851f-dcb4f4ececa1",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "# Valid Sudoku - 9*9\n",
    "# Each row must contain the digits 1-9 without repetition.\n",
    "# Each column must contain the digits 1-9 without repetition.\n",
    "# Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.\n",
    "\n",
    "# Using Hash to store the elements from Row, Column and 3*3 Block.\n",
    "def is_valid_sudoku(board):\n",
    "    duplicate = {}\n",
    "    for row in range(9):\n",
    "        for column in range(9):\n",
    "            num = board[row][column]\n",
    "            if num != '.':\n",
    "                # Row Key\n",
    "                key = num + 'R' + str(row)\n",
    "                if key in duplicate:\n",
    "                    return False\n",
    "                duplicate[key] = True\n",
    "\n",
    "                # column Key\n",
    "                key = num + 'C' + str(column)\n",
    "                if key in duplicate:\n",
    "                    return False\n",
    "                duplicate[key] = True\n",
    "\n",
    "                # 3*3 Block Key\n",
    "                key = num + 'BLOCK' + str(row//3) + str(column//3)\n",
    "                if key in duplicate:\n",
    "                    return False\n",
    "                duplicate[key] = True\n",
    "    return True\n",
    "\n",
    "board = [[\"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",
    "print(is_valid_sudoku(board))\n",
    "\n",
    "board = [[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"]\n",
    ",[\"6\",\"5\",\".\",\"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",
    "print(is_valid_sudoku(board))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "0d9f6d93-7db3-476f-962b-5e8a100cb8c4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "tset\n",
      "ralav\n",
      "dlrow ,olleh\n"
     ]
    }
   ],
   "source": [
    "# Reverse String\n",
    "def reverse_string(str):\n",
    "\n",
    "    return str[::-1]\n",
    "\n",
    "print(reverse_string(\"test\"))\n",
    "print(reverse_string(\"valar\"))\n",
    "\n",
    "res = \"\"\n",
    "s = list(\"hello, world\")\n",
    "for c in s:\n",
    "    res = c + res\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "b30ce9bd-286f-42ba-890f-10d99c18cc9a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "2\n",
      "-1\n"
     ]
    }
   ],
   "source": [
    "# First Unique Character\n",
    "# Using Array to store the char count\n",
    "def first_unique_char(str):\n",
    "    count = [0] * 26\n",
    "    # Count chars\n",
    "    for c in str:\n",
    "        count[ord(c) - 97] += 1\n",
    "    # Iterate the str and find the first unique char\n",
    "    for i in range(len(str)):\n",
    "        if count[ord(str[i]) - 97] == 1:\n",
    "            return i\n",
    "    return -1\n",
    "\n",
    "print(first_unique_char(\"leetcode\"))\n",
    "print(first_unique_char(\"loveleetcode\"))\n",
    "print(first_unique_char(\"aa\"))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "3493e674-6c6b-45de-965c-2e05afe4e3e8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['flight', 'flow', 'flower']\n",
      "fl\n",
      "['car', 'dog', 'flight', 'flow', 'flower', 'racecar']\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Longest Common Prefix\n",
    "def longest_common_prefix(strs):\n",
    "    # Sort the elements O(n logn)\n",
    "    strs.sort()\n",
    "    print(strs)\n",
    "    first = strs[0]\n",
    "    last = strs[-1]\n",
    "    ans = \"\"\n",
    "\n",
    "    # Compare first and last string chars\n",
    "    for i in range(min(len(first), len(last))):\n",
    "        if first[i] == last[i]:\n",
    "            ans += first[i]\n",
    "        else:\n",
    "            break\n",
    "            \n",
    "    return ans\n",
    "\n",
    "print(longest_common_prefix([\"flower\", \"flow\", \"flight\"]))\n",
    "print(longest_common_prefix([\"flower\", \"flow\", \"flight\", \"dog\",\"racecar\",\"car\"]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "31388d2f-aa52-4d58-8852-b7ba43e264ee",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n",
      "False\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "# Valid Anagram\n",
    "# Using array to store char count\n",
    "def is_valid_anagram(s1, s2):\n",
    "    n = len(s1)\n",
    "    if n != len(s2):\n",
    "        return False\n",
    "    count = [0] * 26\n",
    "\n",
    "    for i in range(n):\n",
    "        count[ord(s1[i]) - ord('a')] += 1\n",
    "\n",
    "    for i in range(n):\n",
    "        count[ord(s2[i]) - ord('a')] -= 1\n",
    "\n",
    "    for i in range(26):\n",
    "        if count[i] != 0:\n",
    "            return False\n",
    "        \n",
    "    return True\n",
    "\n",
    "# Using sort\n",
    "def is_valid_anagram_v2(s1, s2):\n",
    "    x = sorted(s1)\n",
    "    y = sorted(s2)\n",
    "\n",
    "    return x == y\n",
    "\n",
    "# Using Hash to store char count\n",
    "def is_valid_anagram_v3(s1, s2):\n",
    "    count = {}\n",
    "    for i in range(97, 123):\n",
    "        count[chr(i)] = 0\n",
    "    n = len(s1)\n",
    "\n",
    "    for i in range(n):\n",
    "        count[s1[i]] += 1\n",
    "\n",
    "    for i in range(n):\n",
    "        count[s2[i]] -= 1\n",
    "\n",
    "    for k in count:\n",
    "        if count[k] != 0:\n",
    "            return False\n",
    "    return True\n",
    "    \n",
    "\n",
    "print(is_valid_anagram(\"anagram\", \"nagaram\"))\n",
    "print(is_valid_anagram(\"car\", \"rat\"))\n",
    "\n",
    "print(is_valid_anagram_v2(\"anagram\", \"nagaram\"))\n",
    "print(is_valid_anagram_v2(\"car\", \"rat\"))\n",
    "\n",
    "print(is_valid_anagram_v3(\"anagram\", \"nagaram\"))\n",
    "print(is_valid_anagram_v3(\"car\", \"rat\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "f35cd1d5-6586-4a41-8727-8e40ae8d11dd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1, 6], [8, 10], [15, 18]]\n",
      "[[1, 5]]\n",
      "[[1, 10]]\n"
     ]
    }
   ],
   "source": [
    "# Merge Intervals\n",
    "def merge_intervals(intervals):\n",
    "    result = []\n",
    "    # Sort the intervals based on start\n",
    "    # intervals.sort()\n",
    "    intervals.sort(key = lambda x: x[0])\n",
    "    for i in intervals:\n",
    "        # If the merged interval is empty or not overlapping, then add it.\n",
    "        if not result or result[-1][-1] < i[0]:\n",
    "            result.append(i)\n",
    "        else:\n",
    "            # If overlapping, then find the max end and set it to last merged interval\n",
    "            result[-1][-1] = max(i[1], result[-1][-1])\n",
    "\n",
    "    return result\n",
    "\n",
    "print(merge_intervals([[1,3],[8,10],[2,6],[15,18]]))\n",
    "print(merge_intervals([[1,4],[4,5]]))\n",
    "print(merge_intervals([[1,4],[1,10], [2, 3]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "65e0b66d-979a-4d20-927d-70859bcd111c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "9\n",
      "1\n",
      "0\n",
      "3\n",
      "3\n",
      "\n",
      "3\n",
      "9\n",
      "1\n",
      "0\n",
      "3\n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# longest substring without repeating characters\n",
    "def length_of_longest_substr(s):\n",
    "    max_l = 0\n",
    "    unique = []\n",
    "\n",
    "    for i in range(len(s)):\n",
    "        if s[i] not in unique:\n",
    "            unique.append(s[i])\n",
    "            max_l = max(max_l, len(unique))\n",
    "        else:\n",
    "            index_of_repeating_chr = unique.index(s[i])\n",
    "            unique = unique[index_of_repeating_chr + 1::]\n",
    "            unique.append(s[i])\n",
    "    return max_l\n",
    "\n",
    "def length_of_longest_substr_v2(s):\n",
    "    max_l = 0\n",
    "    start = 0\n",
    "    unique = {}\n",
    "\n",
    "    for right in range(len(s)):\n",
    "        if s[right] in unique and unique[s[right]] >= start:\n",
    "            start = unique[s[right]] + 1\n",
    "        unique[s[right]] = right\n",
    "        max_l = max(max_l, right - start + 1)\n",
    "    return max_l\n",
    "\n",
    "print(length_of_longest_substr(\"abcabcbb\"))\n",
    "print(length_of_longest_substr(\"abcdefghid\"))\n",
    "print(length_of_longest_substr(\"bbbb\"))\n",
    "print(length_of_longest_substr(\"\"))\n",
    "print(length_of_longest_substr(\"pwwkew\"))\n",
    "print(length_of_longest_substr(\"dvdf\"))\n",
    "print()\n",
    "print(length_of_longest_substr_v2(\"abcabcbb\"))\n",
    "print(length_of_longest_substr_v2(\"abcdefghid\"))\n",
    "print(length_of_longest_substr_v2(\"bbbb\"))\n",
    "print(length_of_longest_substr_v2(\"\"))\n",
    "print(length_of_longest_substr_v2(\"pwwkew\"))\n",
    "print(length_of_longest_substr_v2(\"dvdf\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "id": "7cd540f6-35c0-4ef4-90d4-c070cb722dd8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 9, 16, 100]\n",
      "[4, 9, 9, 49, 121]\n"
     ]
    }
   ],
   "source": [
    "# Sorted squared array\n",
    "def sorted_squred_array(arr):\n",
    "    i = 0\n",
    "    j = len(arr) - 1\n",
    "    result = [0] * len(arr)\n",
    "\n",
    "    for k in range(len(arr) - 1, -1, -1):\n",
    "        if abs(arr[i]) > abs(arr[j]):\n",
    "            result[k] = arr[i] * arr[i]\n",
    "            i += 1\n",
    "        else:\n",
    "            result[k] = arr[j] * arr[j]\n",
    "            j -= 1\n",
    "\n",
    "    return result\n",
    "\n",
    "print(sorted_squred_array([-4,-1,0,3,10]))\n",
    "print(sorted_squred_array([-7,-3,2,3,11]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "65f2fa3d-25b2-4695-9ecd-9609434e5ce6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[24, 12, 8, 6]\n",
      "[24, 12, 8, 6]\n"
     ]
    }
   ],
   "source": [
    "# Product except itself\n",
    "\n",
    "def product_except_itself(nums):\n",
    "    left_product = [1] * len(nums)\n",
    "    right_product = [1] * len(nums)\n",
    "\n",
    "    n = len(nums)\n",
    "\n",
    "    # Left-side products\n",
    "    for i in range(1, n):\n",
    "        left_product[i] = left_product[i - 1] * nums[i - 1]\n",
    "\n",
    "    # Right side products\n",
    "    for i in range(n - 2, -1, -1):\n",
    "        right_product[i] = right_product[i + 1] * nums[i + 1]\n",
    "\n",
    "    # Combine both products\n",
    "    for i in range(n):\n",
    "        nums[i] = left_product[i] * right_product[i]\n",
    "\n",
    "    return nums\n",
    "\n",
    "\n",
    "def product_except_itself_v2(nums):\n",
    "    left_product = [1] * len(nums)\n",
    "    n = len(nums)\n",
    "\n",
    "    # Left-side products\n",
    "    for i in range(1, n):\n",
    "        left_product[i] = left_product[i - 1] * nums[i - 1]\n",
    "\n",
    "    right = 1\n",
    "    # Combine both products store in the Left\n",
    "    for i in range(n - 1, -1, -1):\n",
    "        left_product[i] *= right\n",
    "        right *= nums[i]\n",
    "\n",
    "    return left_product\n",
    "\n",
    "\n",
    "print(product_except_itself([1,2,3,4]))\n",
    "\n",
    "print(product_except_itself_v2([1,2,3,4]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 132,
   "id": "2e154543-4d0b-452a-8efa-7ac2da2e1480",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Kth Largest from array\n",
    "# 1st approach:\n",
    "def kth_largest(arr, k):\n",
    "    for i in range(k-1):\n",
    "        arr.remove(max(arr))\n",
    "    return max(arr)\n",
    "\n",
    "\n",
    "# 2nd approach:\n",
    "def kth_largest(arr, k):\n",
    "    n = len(arr)\n",
    "    arr.sort()\n",
    "    return arr[n-k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "89b1dfc6-65c3-40d6-afff-90bbc0dfd8d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 3 sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2f9b209c-2819-454f-90bd-c459568e538f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Merge K sorted lists\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "362a0b02-3783-478f-aedd-127de24e2f70",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Rotate Image - Matrix rotation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "f2aacaf3-15b8-4659-8d15-fbace2b2df60",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "# Maximum Subarray\n",
    "# Given an integer array nums, find the subarray with the largest sum, and return its sum\n",
    "# https://medium.com/@rishu__2701/mastering-sliding-window-techniques-48f819194fd7\n",
    "def max_subarray(arr, count):\n",
    "    max_sum = 0\n",
    "    window_sum = sum(arr[:count])\n",
    "\n",
    "    for i in range(count, len(arr)):\n",
    "        window_sum += arr[i] - arr[i - count]\n",
    "        max_sum = max(max_sum, window_sum)\n",
    "    return max_sum\n",
    "\n",
    "\n",
    "print(max_subarray([-2,1,-3,4,-1,2,1,-5,4], 6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "16c7ce07-153f-483e-8bb7-803ebe47e844",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "5\n",
      "6\n",
      "0\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "# Length of last word\n",
    "def length_of_lastword(str):\n",
    "    n = len(str) - 1\n",
    "\n",
    "    while n >= 0:\n",
    "        if str[n] == ' ':\n",
    "            n -= 1\n",
    "        else:\n",
    "            break\n",
    "\n",
    "    last_char = n\n",
    "    while n >= 0:\n",
    "        if str[n] != ' ':\n",
    "            n -= 1\n",
    "        else:\n",
    "            break\n",
    "\n",
    "    return last_char - n\n",
    "\n",
    "\n",
    "print(length_of_lastword(\"Length of last word\"))\n",
    "print(length_of_lastword(\"Length of last wordd \"))\n",
    "print(length_of_lastword(\"Length \"))\n",
    "print(length_of_lastword(\"  \"))\n",
    "print(length_of_lastword(\"  s\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7057490e-fd58-4d91-93be-7d31aac09143",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Remove duplicate element from array II"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "4749dede-5d00-462f-9c79-537273f064bb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 2 1 \n",
      "1 2 3 "
     ]
    }
   ],
   "source": [
    "# Reverse Linked List - in-place o(n)\n",
    "def reverse_list(list):\n",
    "    head = list.head\n",
    "\n",
    "    new_head = None\n",
    "    while head is not None:\n",
    "        temp = head.next\n",
    "        head.next = new_head\n",
    "        new_head = head\n",
    "        head = temp\n",
    "        \n",
    "    list.head = new_head\n",
    "\n",
    "list_1 = LinkedList()\n",
    "list_1.push(1)\n",
    "list_1.push(2)\n",
    "list_1.push(3)\n",
    "\n",
    "list_1.print_list()\n",
    "print()\n",
    "reverse_list(list_1)\n",
    "list_1.print_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "01e0ba37-441a-43c8-b962-0c3506592fc5",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Tree Node\n",
    "class TreeNode(object):\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.left  = None\n",
    "        self.right = None\n",
    "\n",
    "    def insert_left(self, value):\n",
    "        self.left = TreeNode(value)\n",
    "        return self.left\n",
    "\n",
    "    def insert_right(self, value):\n",
    "        self.right = TreeNode(value)\n",
    "        return self.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "b0aea305-1e13-4e01-aee1-4c400f83d74c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 -3 -10 9 5 \n",
      "-10 -3 0 5 9 \n",
      "-10 -3 5 9 0 \n",
      "-10 -3 0 5 9 \n",
      "0 9 5 -3 -10 "
     ]
    }
   ],
   "source": [
    "# Convert sorted array to Binary search tree\n",
    "# Search\n",
    "# Insert\n",
    "# Delete\n",
    "# Traverse\n",
    "\n",
    "def sorted_array_to_BST(arr):\n",
    "    n = len(arr)\n",
    "    if n == 0:\n",
    "        return None\n",
    "    mid = n // 2\n",
    "    root = TreeNode(arr[mid])\n",
    "\n",
    "    root.left = sorted_array_to_BST(arr[:mid])\n",
    "    root.right = sorted_array_to_BST(arr[mid+1:])\n",
    "    return root\n",
    "\n",
    "# Tree Traversals - BFS and DFS\n",
    "# DFS - inorder, preorder and postorder\n",
    "def inorder(root):\n",
    "    if root == None:\n",
    "        # print(\"null\", end=\" \")\n",
    "        return\n",
    "    print(root.value, end=\" \")\n",
    "    inorder(root.left)\n",
    "    inorder(root.right)\n",
    "\n",
    "\n",
    "def preorder(root):\n",
    "    if root == None:\n",
    "        # print(\"null\", end=\" \")\n",
    "        return\n",
    "    preorder(root.left)\n",
    "    print(root.value, end=\" \")\n",
    "    preorder(root.right)\n",
    "\n",
    "def postorder(root):\n",
    "    if root == None:\n",
    "        # print(\"null\", end=\" \")\n",
    "        return\n",
    "    postorder(root.left)\n",
    "    postorder(root.right)\n",
    "    print(root.value, end=\" \")\n",
    "\n",
    "def dfs(root):\n",
    "    if root == None:\n",
    "        return\n",
    "    dfs(root.left)\n",
    "    print(root.value, end=\" \")\n",
    "    dfs(root.right)\n",
    "\n",
    "# printLevelOrder\n",
    "def bfs(root):\n",
    "    if root == None:\n",
    "        return\n",
    "    queue = []\n",
    "    queue.append(root)\n",
    "\n",
    "    while len(queue) > 0:\n",
    "        temp = queue.pop()\n",
    "        print(temp.value, end=\" \")\n",
    "\n",
    "        if temp.left != None:\n",
    "            queue.append(temp.left)\n",
    "        if temp.right != None:\n",
    "            queue.append(temp.right)\n",
    "\n",
    "tree = sorted_array_to_BST([-10,-3,0,5,9])\n",
    "inorder(tree)\n",
    "print()\n",
    "preorder(tree)\n",
    "print()\n",
    "postorder(tree)\n",
    "print()\n",
    "dfs(tree)\n",
    "print()\n",
    "bfs(tree)\n",
    "\n",
    "def insert(root, value):\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "d65b0ad9-0dbf-4b60-8943-71f8a5a673d8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6 13 4 8 5 8 1 2 7 3 \n",
      "6 8 2 3 7 1 13 5 4 8 "
     ]
    }
   ],
   "source": [
    "# Reverse Binary Tree\n",
    "def reverse_tree(root):\n",
    "    if root is None:\n",
    "        return\n",
    "    root.left, root.right = root.right, root.left\n",
    "    reverse_tree(root.left)\n",
    "    reverse_tree(root.right)\n",
    "\n",
    "root = TreeNode(6)\n",
    "root.insert_left(13)\n",
    "root.left.insert_left(4)\n",
    "root.left.insert_right(5)\n",
    "root.left.left.insert_left(8)\n",
    "\n",
    "root.insert_right(8)\n",
    "root.right.insert_left(1)\n",
    "root.right.insert_right(2)\n",
    "root.right.right.insert_left(7)\n",
    "root.right.right.insert_right(3)\n",
    "\n",
    "inorder(root)\n",
    "print()\n",
    "reverse_tree(root)\n",
    "inorder(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d5f25f2c-341c-46f2-bbb6-db2fe8d4041d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Is Mirror Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ac261711-e062-4594-9760-22f38118c16e",
   "metadata": {},
   "outputs": [],
   "source": [
    "# longest consecutive elements sequence"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "67a8e8b9-c405-4bbd-b5d8-d7015003f1ec",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Word break\n",
    "# Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.\n",
    "\n",
    "def word_break(s, words):\n",
    "    \n",
    "\n",
    "print(word_break(\"leetcode\", [\"leet\",\"code\"]))\n",
    "print(word_break(\"applepenapple\", [\"apple\",\"pen\"]))\n",
    "print(word_break(\"catsandog\", [\"cats\",\"dog\",\"sand\",\"and\",\"cat\"]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "48c3a22a-6a03-433b-9ca9-36f7392959ca",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Maximum product subarray"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "769d17a5-e22f-4e47-82ef-d599a7e3d1bd",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Timestamp: 1713119728.7512372\n",
      "0 ! ->  1\n",
      "1 ! ->  1\n",
      "2 ! ->  2\n",
      "3 ! ->  6\n",
      "4 ! ->  24\n",
      "5 ! ->  120\n",
      "6 ! ->  720\n",
      "7 ! ->  5040\n",
      "8 ! ->  40320\n",
      "9 ! ->  362880\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "current_timestamp = time.time()\n",
    "print(\"Timestamp:\", current_timestamp)\n",
    "\n",
    "def factorial(n):\n",
    "    if n <= 1:\n",
    "        return 1\n",
    "    return n * factorial(n - 1)\n",
    "\n",
    "for i in range(10):\n",
    "    print(i, \"! -> \",factorial(i))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "9f1d606b-a1a5-48f9-afa2-305d059f7a73",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n",
      "[2, 3]\n",
      "[3]\n",
      "[]\n",
      "[2]\n",
      "[]\n",
      "[1, 3]\n",
      "[3]\n",
      "[]\n",
      "[1]\n",
      "[]\n",
      "[1, 2]\n",
      "[2]\n",
      "[]\n",
      "[1]\n",
      "[]\n",
      "[[3, 2, 1], [2, 3, 1], [3, 1, 2], [1, 3, 2], [2, 1, 3], [1, 2, 3]]\n"
     ]
    }
   ],
   "source": [
    "# Permutations - Using Backtracking\n",
    "# Time complexity: O(n! * n),\n",
    "def permutations(nums):\n",
    "    res = []\n",
    "    dfs(nums, [], res)\n",
    "    return res\n",
    "count = 0\n",
    "def dfs(nums, path, res):\n",
    "    global count\n",
    "    count += 1\n",
    "    print(count, \"\\t\", nums, \"\\t\", path, \"\\t\",res)\n",
    "    if not nums:\n",
    "        res.append(path)\n",
    "        # return # backtracking\n",
    "    for i in range(len(nums)):\n",
    "        dfs(nums[:i] + nums[i+1:], path + [nums[i]], res)\n",
    "\n",
    "def get_permutations(arr):\n",
    "    print(arr)\n",
    "    if len(arr) == 0:\n",
    "        return [arr]\n",
    "    permutations = []\n",
    "    for i in range(len(arr)):\n",
    "        if arr[i] not in arr[:i]:\n",
    "            remaining = get_permutations(arr[:i] + arr[i+1:])\n",
    "            for permutation in remaining:\n",
    "                permutation.append(arr[i])\n",
    "                permutations.append(permutation)\n",
    "    return permutations\n",
    "    \n",
    "    \n",
    "\n",
    "# print(permutations([1,2,3]))\n",
    "# print(count)\n",
    "# count = 0\n",
    "print(get_permutations([1,2,3]))\n",
    "# print(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "74a192b1-2e3f-4828-9055-3a6e9620cf51",
   "metadata": {},
   "outputs": [
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mIndexError\u001b[0m                                Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[22], line 2\u001b[0m\n\u001b[1;32m      1\u001b[0m a \u001b[38;5;241m=\u001b[39m []\n\u001b[0;32m----> 2\u001b[0m \u001b[43ma\u001b[49m\u001b[43m[\u001b[49m\u001b[38;5;241;43m1\u001b[39;49m\u001b[43m]\u001b[49m\n",
      "\u001b[0;31mIndexError\u001b[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "a = []\n",
    "a[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ff90887-067e-44ac-9a9a-1c7c22f42f98",
   "metadata": {},
   "source": [
    "###### Dynamic programming\n",
    "# Dynamic programming is a method of solving complex problems by breaking them down into simpler steps. \n",
    "# It applies to problems that exhibit the properties of \n",
    "# 1) overlapping subproblems which are only slightly smaller and \n",
    "# 2) optimal substructure.\n",
    "\n",
    "# Top-Down approach -> Recursive -> Memoisation\n",
    "# Bottom-up approach -> For loops -> Tabulation (Initialize values in a array and store computed result)\n",
    "\n",
    "- Longest Common Subsequence\n",
    "- Coin Change\n",
    "- Cake Thief\n",
    "- Fibonacci\n",
    "\n",
    "# Backtracking\n",
    "Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, \n",
    "that incrementally builds candidates to the solutions, \n",
    "and abandons each partial candidate c (\"backtracks\") as soon as it determines that c cannot possibly be completed to a valid solution.\n",
    "\n",
    "- N-Queens\n",
    "- Sudoku Solver\n",
    "- Permutations\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "53e72112-5ca7-4960-9c9b-17fb7ba852a8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 2 1 0 \n",
      "2 2 1 0 \n",
      "2 2 1 0 \n",
      "1 1 1 0 \n",
      "1 1 1 0 \n",
      "0 0 0 0 \n",
      "\n",
      "3\n",
      "0 0 0 0 \n",
      "0 1 1 1 \n",
      "0 1 1 1 \n",
      "0 1 2 2 \n",
      "0 1 2 2 \n",
      "0 1 2 3 \n",
      "\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "# longest common subsequence\n",
    "# Dynamic programming - Tabulation approach\n",
    "# time and space complexity - O(n*m)\n",
    "def longest_common_subsequence(s1, s2):\n",
    "    dp = [[0]*(len(s2)+1) for j in range(len(s1) + 1)]\n",
    "\n",
    "    for i in range(len(s1) - 1, -1, -1):\n",
    "        for j in range(len(s2) - 1, -1, -1):\n",
    "            if s1[i] == s2[j]:\n",
    "                dp[i][j] = 1 + dp[i + 1][j + 1]\n",
    "            else:\n",
    "                dp[i][j] = max(dp[i][j+1], dp[i+1][j])\n",
    "    print_arr(dp)\n",
    "    return dp[0][0]\n",
    "\n",
    "def longest_common_subsequence_v2(s1, s2):\n",
    "    m = len(s1)\n",
    "    n = len(s2)\n",
    "    dp = [[0] * (n + 1) for j in range(m + 1)]\n",
    "    # print_arr(dp)\n",
    "    for i in range(1, m + 1):\n",
    "        for j in range(1, n + 1):\n",
    "            if s1[i - 1] == s2[j - 1]:\n",
    "                dp[i][j] = 1 + dp[i - 1][j - 1]\n",
    "            else:\n",
    "                dp[i][j] = max(dp[i][j - 1], dp[i-1][j])\n",
    "    print_arr(dp)\n",
    "    return dp[n][n]\n",
    "\n",
    "def print_arr(arr):\n",
    "    for i in range(len(arr)):\n",
    "        for j in range(len(arr[i])):\n",
    "            print(arr[i][j], end=\" \")\n",
    "        print()\n",
    "    print()\n",
    "    \n",
    "\n",
    "print(longest_common_subsequence(\"abcde\", \"ace\"))\n",
    "# print(longest_common_subsequence(\"abcdefghct\", \"ace\"))\n",
    "# print(longest_common_subsequence(\"abc\", \"abc\"))\n",
    "# print(longest_common_subsequence(\"abc\", \"def\"))\n",
    "\n",
    "print(longest_common_subsequence_v2(\"abcde\", \"ace\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "id": "bdbbbd80-4b69-4ddb-a28f-e5958ad545b6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "# O(m * n)\n",
    "# LCS\n",
    "def longest_common_subsequence_v2(s1, s2):\n",
    "    m = len(s1)\n",
    "    n = len(s2)\n",
    "    dp = [[0] * (n+1) for i in range(m+1)]\n",
    "\n",
    "    for i in range(1, m + 1):\n",
    "        for j in range(1, n+1):\n",
    "            if s1[i - 1] == s2[j - 1]:\n",
    "                dp[i][j] = 1 + dp[i - 1][j - 1]\n",
    "            else:\n",
    "                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])\n",
    "    return dp[m][n]\n",
    "\n",
    "print(longest_common_subsequence_v2(\"abcde\", \"ace\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 206,
   "id": "b08e0afe-a3fc-4dd8-b8e2-9f385e65640f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 12 12 12 12 12 12 12 12 12 12 12 \n",
      "0 12 12 12 12 12 12 12 12 12 12 12 \n",
      "0 12 12 12 12 12 12 12 12 12 12 12 \n",
      "0 12 12 12 12 12 12 12 12 12 12 12 \n",
      "0 12 12 12 12 1 12 12 12 12 12 12 \n",
      "0 12 12 12 12 1 12 12 12 12 12 12 \n",
      "0 12 12 12 12 1 12 12 12 12 12 12 \n",
      "0 12 12 12 12 1 12 12 12 12 12 12 \n",
      "0 12 12 12 12 1 12 12 12 12 12 12 \n",
      "0 12 12 12 12 1 12 12 12 12 2 12 \n",
      "0 12 12 12 12 1 12 12 12 12 2 12 \n",
      "-1\n",
      "0 8 8 8 8 8 8 8 \n",
      "0 8 1 8 8 8 8 8 \n",
      "0 8 1 1 8 8 8 8 \n",
      "0 8 1 1 2 8 8 8 \n",
      "0 8 1 1 2 2 8 8 \n",
      "0 8 1 1 2 2 2 8 \n",
      "0 8 1 1 2 2 2 3 \n",
      "3\n"
     ]
    }
   ],
   "source": [
    "# Coin Change\n",
    "# If we need to find the min value then, initialize the DP array with a possible max value\n",
    "# Finding min coins for 1, 2, 3, ... n\n",
    "def coin_change(coins, amount):\n",
    "    # Initialize min_coins array with amount+1 coins\n",
    "    min_coins = [0] + [amount + 1] * amount\n",
    "\n",
    "    for current_amount in range(1, amount + 1):\n",
    "        for coin in coins:\n",
    "            if current_amount - coin >= 0:\n",
    "                min_coins[current_amount] = min(min_coins[current_amount], min_coins[current_amount - coin] + 1)\n",
    "        print_arr_1(min_coins)\n",
    "    # Check if the coin count is not equal to the initialized count, then return it\n",
    "    if min_coins[amount] != amount + 1:\n",
    "        return min_coins[amount]\n",
    "    return -1\n",
    "\n",
    "\n",
    "def print_arr_1(arr):\n",
    "    for i in range(len(arr)):\n",
    "        print(arr[i], end=\" \")\n",
    "    print()\n",
    "    \n",
    "print(coin_change([5], 11))\n",
    "print(coin_change([2, 3], 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "id": "aefddda7-aa87-4763-a54b-49ef41750584",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 2 3 4 5 \n",
      "1 0 1 2 3 4 \n",
      "2 1 0 1 2 3 \n",
      "3 2 1 1 2 3 \n",
      "4 3 2 2 2 3 \n",
      "5 4 3 2 3 3 \n",
      "6 5 4 3 2 3 \n",
      "\n",
      "3\n",
      "0 1 2 3 4 5 6 7 \n",
      "1 0 1 2 3 4 5 6 \n",
      "2 1 0 1 2 3 4 5 \n",
      "3 2 1 0 1 2 3 4 \n",
      "4 3 2 1 0 1 2 3 \n",
      "5 4 3 2 1 1 1 2 \n",
      "6 5 4 3 2 2 2 1 \n",
      "\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "# levenshtein Edit Distance\n",
    "# Operations Insert, Delete, and Substitute\n",
    "# The matrix is built iteratively using the following recurrence relation:\n",
    "# - If word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1]. That is, no operation is required because the characters at positions i-1 and j-1 are already the same.\n",
    "#   Otherwise, dp[i][j] is the minimum of the following three values:\n",
    "# - dp[i-1][j-1] + 1: replace the character at position i-1 in word1 with the character at position j-1 in word2.\n",
    "# - dp[i-1][j] + 1: delete the character at position i-1 in word1.\n",
    "# - dp[i][j-1] + 1: insert the character at position j-1 in word2 into word1 at position i.\n",
    "\n",
    "def edit_distance(s1, s2):\n",
    "    n = len(s1)\n",
    "    m = len(s2)\n",
    "    dp = [[0] * (m + 1) for i in range(n+1)]\n",
    "\n",
    "    for j in range(1, m + 1):\n",
    "        dp[0][j] = j\n",
    "    for i in range(1, n + 1):\n",
    "        dp[i][0] = i\n",
    "\n",
    "    for i in range(1, n + 1):\n",
    "        for j in range(1, m + 1):\n",
    "            if s1[i - 1] == s2[j - 1]:\n",
    "                dp[i][j] = dp[i - 1][j - 1]\n",
    "            else:\n",
    "                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])\n",
    "                \n",
    "    print_arr(dp)\n",
    "    return dp[n][m]\n",
    "\n",
    "print(edit_distance(\"inside\", \"index\"))\n",
    "print(edit_distance(\"inside\", \"insisde\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "05fbdbc3-0fd0-481f-a701-e77c62fb2c97",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 1 1 1 0 \n",
      "0 0 0 0 0 \n",
      "0 0 0 0 0 \n",
      "0 0 0 0 0 \n",
      "\n",
      "1 1 1 1 0 \n",
      "0 1 0 1 1 \n",
      "0 1 0 1 2 \n",
      "0 1 1 2 4 \n",
      "\n",
      "4\n",
      "0 0 0 0 \n",
      "0 0 0 0 \n",
      "\n",
      "0 0 0 0 \n",
      "0 0 0 0 \n",
      "\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "# Paths in Matrix\n",
    "# Dynamic programming - Tabulation\n",
    "# Time and Space O(mn)\n",
    "def paths(matrix):\n",
    "    m = len(matrix[0]) # Column count\n",
    "    n = len(matrix) # Row count\n",
    "    dp = [[0] * m for i in range(n)]\n",
    "\n",
    "    if matrix[0][0] == 1:\n",
    "        dp[0][0] = 0\n",
    "    else:\n",
    "        dp[0][0] = 1\n",
    "        \n",
    "    for i in range(1, n):\n",
    "        if matrix[i][0] == 1:\n",
    "            dp[i][0] = 0\n",
    "        else:\n",
    "            dp[i][0] = dp[i - 1][0]\n",
    "\n",
    "    for j in range(1, m):\n",
    "        if matrix[0][j] == 1:\n",
    "            dp[0][j] = 0\n",
    "        else:\n",
    "            dp[0][j] = dp[0][j - 1]\n",
    "\n",
    "    print_arr(dp)\n",
    "    for i in range(1, n):\n",
    "        for j in range(1, m):\n",
    "            if matrix[i][j] == 1:\n",
    "                dp[i][j] = 0\n",
    "            else:\n",
    "                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]\n",
    "    print_arr(dp)\n",
    "    return dp[n - 1][m - 1]\n",
    "\n",
    "\n",
    "print(paths([[0, 0, 0, 0, 1], [1, 0, 1, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 0]]))\n",
    "print(paths([[1, 0, 0, 0], [0, 0, 0, 0]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c46e4917-4bcc-41bc-bb13-3e6dd65a29c8",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}

RateLimitter.ipynb

N Queens - Total iterations 2057
Total answers - 92 (from wiki)