LeetCode.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true,
    "pycharm": {
     "name": "#%%\n"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "# leet code 202.Happy Number\n",
    "# https://leetcode.com/problems/happy-number/\n",
    "\n",
    "\n",
    "def solve(n,memo={}):\n",
    "    if n == 1 : return True\n",
    "\n",
    "    if n in memo:\n",
    "        return False\n",
    "\n",
    "    s = 0\n",
    "    b = n\n",
    "    for _ in range(len(str(n))):\n",
    "        s = s + (n%10)**2\n",
    "        n = n // 10\n",
    "    memo[b] = s\n",
    "    return solve(s,memo)\n",
    "\n",
    "print(solve(11))\n",
    "\n",
    "# status : AC"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['abc', 'cba']\n"
     ]
    }
   ],
   "source": [
    "# leet code 890.Find and Replace Pattern\n",
    "# https://leetcode.com/problems/find-and-replace-pattern/\n",
    "\n",
    "\n",
    "def solve(words,pattern):\n",
    "    word_list = []\n",
    "    for word in words:\n",
    "        # print(word)\n",
    "        dict = {}\n",
    "        if len(word) != len(pattern):\n",
    "            continue\n",
    "        if len(set(word)) != len(set(pattern)):\n",
    "            continue\n",
    "        for w,p in zip(word,pattern):\n",
    "            if w not in dict:\n",
    "                dict[w] = p\n",
    "            else:\n",
    "                if dict[w] != p:\n",
    "                    break\n",
    "        else:\n",
    "            word_list.append(word)\n",
    "    return word_list\n",
    "\n",
    "\n",
    "words = [\"abc\",\"cba\",\"xyx\",\"yxx\",\"yyx\"]\n",
    "# words = [\"a\",\"b\",\"c\"]\n",
    "# words = [\"ccc\"]\n",
    "pattern = \"abc\"\n",
    "print(solve(words,pattern))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['amazon', 'apple', 'facebook', 'google', 'leetcode']\n"
     ]
    }
   ],
   "source": [
    "# leet code 916:WordSubsets\n",
    "# https://leetcode.com/problems/word-subsets/\n",
    "def solve(words1 , words2):\n",
    "\n",
    "\n",
    "words1 = [\"amazon\",\"apple\",\"facebook\",\"google\",\"leetcode\"]\n",
    "\n",
    "words2 = [\"lo\",\"eo\"]\n",
    "\n",
    "print(solve(words1,words2))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "a = \"google\"\n",
    "print(a.count(\"o\"))\n",
    "# check if a contains substring of b\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['a', 'b', 'd', 'e', 'c', 'f']\n",
      "['a', 'b', 'd', 'e', 'c', 'f']\n"
     ]
    }
   ],
   "source": [
    "# learning Binary Tree BFS\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "def depth_first_value(root):\n",
    "    stack = [root]\n",
    "    result = []\n",
    "    while stack:\n",
    "        node = stack.pop()\n",
    "        result.append(node.data)\n",
    "        if node.right:\n",
    "            stack.append(node.right)\n",
    "        if node.left:\n",
    "            stack.append(node.left)\n",
    "    return result\n",
    "\n",
    "def depth_first_value_recursive(root):\n",
    "    if root is None:\n",
    "        return []\n",
    "    leftValues = depth_first_value_recursive(root.left)\n",
    "    rightValues = depth_first_value_recursive(root.right)\n",
    "    return [root.data] + leftValues + rightValues\n",
    "\n",
    "\n",
    "a = Node('a')\n",
    "b = Node('b')\n",
    "c = Node('c')\n",
    "d = Node('d')\n",
    "e = Node('e')\n",
    "f = Node('f')\n",
    "\n",
    "a.left = b\n",
    "a.right = c\n",
    "b.left = d\n",
    "b.right = e\n",
    "c.right = f\n",
    "print(depth_first_value(a))\n",
    "print(depth_first_value_recursive(a))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "outputs": [
    {
     "data": {
      "text/plain": "['a', 'b', 'c', 'd', 'e', 'f']"
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# BFS\n",
    "class Node:\n",
    "    def __init__(self,data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "def breadth_first_value(root):\n",
    "    queue = [root]\n",
    "    result = []\n",
    "    while queue:\n",
    "        node = queue.pop(0)\n",
    "        result.append(node.data)\n",
    "        if node.left:queue.append(node.left)\n",
    "        if node.right:queue.append(node.right)\n",
    "    return result\n",
    "\n",
    "breadth_first_value(a)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "outputs": [
    {
     "data": {
      "text/plain": "True"
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# check if binary tree contains an element target\n",
    "\n",
    "def tree_includes(root,target):\n",
    "    if root is None:\n",
    "        return False\n",
    "    queue = [root]\n",
    "    while queue:\n",
    "        node = queue.pop(0)\n",
    "        if node.data == target:\n",
    "            return True\n",
    "        if node.left:\n",
    "            queue.append(node.left)\n",
    "        if node.right:\n",
    "            queue.append(node.right)\n",
    "    return False\n",
    "\n",
    "def tree_includes_recursive(root,target):\n",
    "    if root is None:return False\n",
    "    if root.data == target:return True\n",
    "    return tree_includes_recursive(root.left,target) or tree_includes_recursive(root.right,target)\n",
    "\n",
    "# tree_includes(a, 'e')\n",
    "tree_includes_recursive(a, 'e')"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "21\n"
     ]
    }
   ],
   "source": [
    "def tree_sum(root):\n",
    "    if root is None:\n",
    "        return 0\n",
    "    return root.data + tree_sum(root.left) + tree_sum(root.right)\n",
    "\n",
    "a = Node(3)\n",
    "b = Node(11)\n",
    "c = Node(4)\n",
    "d = Node(4)\n",
    "e = Node(-2)\n",
    "f = Node(1)\n",
    "\n",
    "a.left = b\n",
    "a.right = c\n",
    "b.left = d\n",
    "b.right = e\n",
    "c.right = f\n",
    "print(tree_sum(a))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "outputs": [
    {
     "data": {
      "text/plain": "21"
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# iterative way to find the sum of all the nodes in a binary tree\n",
    "def tree_sum_iterative(root):\n",
    "    if root is None:\n",
    "        return 0\n",
    "    queue = [root]\n",
    "    totalSum = 0\n",
    "    while queue:\n",
    "        node = queue.pop(0)\n",
    "        totalSum += node.data\n",
    "        if node.left:queue.append(node.left)\n",
    "        if node.right:queue.append(node.right)\n",
    "    return totalSum\n",
    "\n",
    "tree_sum_iterative(a)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "outputs": [
    {
     "data": {
      "text/plain": "-2"
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# get the smallest element in a binary tree using iterative way\n",
    "import math\n",
    "def tree_min(root):\n",
    "    smallest = math.inf\n",
    "    stack = [root]\n",
    "    while stack:\n",
    "        current = stack.pop()\n",
    "        if current.data < smallest:\n",
    "            smallest = current.data\n",
    "        if current.right: stack.append(current.right)\n",
    "        if current.left: stack.append(current.left)\n",
    "    return smallest\n",
    "tree_min(a)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "outputs": [
    {
     "data": {
      "text/plain": "-2"
     },
     "execution_count": 79,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# get the smallest element in a binary tree using recursive way\n",
    "def tree_min_recursive(root):\n",
    "    if root is None:\n",
    "        return math.inf\n",
    "    left_min = tree_min_recursive(root.left)\n",
    "    right_min = tree_min_recursive(root.right)\n",
    "    return min(left_min,right_min,root.data)\n",
    "tree_min_recursive(a)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "outputs": [
    {
     "data": {
      "text/plain": "18"
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# max path sum in a binary tree\n",
    "def max_path_sum(root):\n",
    "    if root is None : return -math.inf\n",
    "    if root.left is None and root.right is None:\n",
    "        return root.data\n",
    "    left_max = max_path_sum(root.left)\n",
    "    right_max = max_path_sum(root.right)\n",
    "    return root.data + max(left_max,right_max)\n",
    "max_path_sum(a)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 2 3 4 \n",
      "5 6 7 8 \n",
      "9 10 11 12 \n",
      "1 2 3 4 \n",
      "5 6 7 8 \n",
      "9 10 11 12 \n"
     ]
    }
   ],
   "source": [
    "# 54. Spiral Matrix\n",
    "# https://leetcode.com/problems/spiral-matrix/\n",
    "class Node:\n",
    "    def __init__(self,i,j,data):\n",
    "        self.data = data\n",
    "        self.i = i\n",
    "        self.j = j\n",
    "        self.top = None\n",
    "        self.bottom = None\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "\n",
    "def create_grid(matrix):\n",
    "    n = len(matrix)\n",
    "    m = len(matrix[0])\n",
    "    grid = [[0 for i in range(m)] for j in range(n)]\n",
    "    for i in range(n):\n",
    "        for j in range(m):\n",
    "            grid[i][j] = Node(i,j,matrix[i][j])\n",
    "    return grid\n",
    "\n",
    "def print_grid(grid):\n",
    "    for i in range(len(grid)):\n",
    "        for j in range(len(grid[0])):\n",
    "            print(grid[i][j].data,end=\" \")\n",
    "        print()\n",
    "\n",
    "def create_neigbours(grid):\n",
    "    for i in range(len(grid)):\n",
    "        for j in range(len(grid[0])):\n",
    "            if i > 0:\n",
    "                grid[i][j].top = grid[i-1][j]\n",
    "            if i < len(grid)-1:\n",
    "                grid[i][j].bottom = grid[i+1][j]\n",
    "            if j > 0:\n",
    "                grid[i][j].left = grid[i][j-1]\n",
    "            if j < len(grid[0])-1:\n",
    "                grid[i][j].right = grid[i][j+1]\n",
    "    return grid\n",
    "mat = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]\n",
    "mat = create_grid(mat)\n",
    "print_grid(mat)\n",
    "mat = create_neigbours(mat)\n",
    "print_grid(mat)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [
    {
     "ename": "IndexError",
     "evalue": "list index out of range",
     "output_type": "error",
     "traceback": [
      "\u001B[1;31m---------------------------------------------------------------------------\u001B[0m",
      "\u001B[1;31mIndexError\u001B[0m                                Traceback (most recent call last)",
      "Input \u001B[1;32mIn [4]\u001B[0m, in \u001B[0;36m<cell line: 27>\u001B[1;34m()\u001B[0m\n\u001B[0;32m     35\u001B[0m     direction \u001B[38;5;241m=\u001B[39m \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mbottom\u001B[39m\u001B[38;5;124m\"\u001B[39m\n\u001B[0;32m     36\u001B[0m     \u001B[38;5;28;01mcontinue\u001B[39;00m\n\u001B[1;32m---> 37\u001B[0m \u001B[38;5;28;01mif\u001B[39;00m \u001B[43mmatrix\u001B[49m\u001B[43m[\u001B[49m\u001B[43mi\u001B[49m\u001B[43m]\u001B[49m\u001B[43m[\u001B[49m\u001B[43mj\u001B[49m\u001B[38;5;241;43m+\u001B[39;49m\u001B[38;5;241;43m1\u001B[39;49m\u001B[43m]\u001B[49m\u001B[38;5;241m==\u001B[39m\u001B[38;5;241m0\u001B[39m:\n\u001B[0;32m     38\u001B[0m     direction \u001B[38;5;241m=\u001B[39m \u001B[38;5;124m\"\u001B[39m\u001B[38;5;124mbottom\u001B[39m\u001B[38;5;124m\"\u001B[39m\n\u001B[0;32m     40\u001B[0m \u001B[38;5;28;01melse\u001B[39;00m:j\u001B[38;5;241m+\u001B[39m\u001B[38;5;241m=\u001B[39m\u001B[38;5;241m1\u001B[39m\n",
      "\u001B[1;31mIndexError\u001B[0m: list index out of range"
     ]
    }
   ],
   "source": [
    "# alternate approach\n",
    "# matrix = [[0,0,0,0,0,0],[0,1,2,3,4,0],[0,5,6,7,8,0],[0,9,10,11,12,0],[0,0,0,0,0,0]]\n",
    "# actual_matrix = [[1,2,3],[4,5,6],[7,8,9]]\n",
    "# matrix = [[0,0,0,0,0],[0,1,2,3,0],[0,4,5,6,0],[0,7,8,9,0],[0,0,0,0,0]]\n",
    "\n",
    "actual_matrix = [[1,2,3],[4,5,6],[7,8,9]]\n",
    "def padded_grid(grid):\n",
    "    n = len(grid[0])\n",
    "    x = [0 for _ in range(n + 2)]\n",
    "    [lst.append(0) for lst in grid]\n",
    "    [lst.insert(0, 0) for lst in grid]\n",
    "    grid.insert(0,x)\n",
    "    grid.append(x)\n",
    "    return grid\n",
    "matrix = padded_grid(actual_matrix)\n",
    "# print(type(matrix1))\n",
    "# add zeros to the exterior of the matrix\n",
    "count = 0\n",
    "direction = \"right\"\n",
    "visited = []\n",
    "spiral_matrix = []\n",
    "i=1\n",
    "j=1\n",
    "n=len(actual_matrix)\n",
    "m=len(actual_matrix[0])\n",
    "while len(visited)<n*m:\n",
    "    # print(matrix[i][j],direction,(i,j))\n",
    "    spiral_matrix.append(matrix[i][j])\n",
    "    visited.append((i,j))\n",
    "    # right bottom left top - clockwise\n",
    "\n",
    "    if direction == \"right\":\n",
    "        if (i,j+1) in visited:\n",
    "            direction = \"bottom\"\n",
    "            continue\n",
    "        if matrix[i][j+1]==0:\n",
    "            direction = \"bottom\"\n",
    "\n",
    "        else:j+=1\n",
    "    if direction == \"bottom\":\n",
    "        if (i+1,j) in visited:\n",
    "            direction = \"left\"\n",
    "            continue\n",
    "        if matrix[i+1][j]==0:\n",
    "            direction = \"left\"\n",
    "\n",
    "        else:i+=1\n",
    "    if direction == \"left\":\n",
    "        if (i,j-1) in visited:\n",
    "            direction = \"top\"\n",
    "            continue\n",
    "        if matrix[i][j-1]==0:\n",
    "            direction = \"top\"\n",
    "\n",
    "        else:j-=1\n",
    "    if direction == \"top\":\n",
    "        if (i-1,j) in visited:\n",
    "            direction = \"right\"\n",
    "            j=j+1\n",
    "            continue\n",
    "        if matrix[i-1][j]==0:\n",
    "            direction = \"right\"\n",
    "\n",
    "        else:i-=1\n",
    "\n",
    "print(spiral_matrix)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "matrix = [[0,0,0,0,0,0],[0,1,2,3,4,0],[0,5,6,7,8,0],[0,9,10,11,12,0],[0,0,0,0,0,0]]\n",
    "print(matrix[1][3])"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<class 'list'>\n"
     ]
    }
   ],
   "source": [
    "actual_matrix = [[1,2,3],[4,5,6],[7,8,9]]\n",
    "def padded_grid(grid):\n",
    "    n = len(grid[0])\n",
    "    x = [0 for _ in range(n + 2)]\n",
    "    [lst.append(0) for lst in grid]\n",
    "    [lst.insert(0, 0) for lst in grid]\n",
    "    grid.insert(0,x)\n",
    "    grid.append(x)\n",
    "    return grid\n",
    "mat = padded_grid(actual_matrix)\n",
    "print(type(mat))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.actual_matrix = []\n",
    "        self.direction = \"right\"\n",
    "        self.visited = []\n",
    "        self.spiral_matrix = []\n",
    "\n",
    "    def padded_grid(self,grid):\n",
    "        n = len(grid[0])\n",
    "        x = [0 for _ in range(n + 2)]\n",
    "        [lst.append(0) for lst in grid]\n",
    "        [lst.insert(0, 0) for lst in grid]\n",
    "        grid.insert(0,x)\n",
    "        grid.append(x)\n",
    "        return grid\n",
    "    def spiralOrder(self,matrix):\n",
    "        self.actual_matrix = matrix\n",
    "        self.n=len(self.actual_matrix)\n",
    "        self.m=len(self.actual_matrix[0])\n",
    "        self.nmatrix = self.padded_grid(self.actual_matrix)\n",
    "        while len(self.visited)<self.n*self.m:\n",
    "            # print(matrix[i][j],direction,(i,j))\n",
    "            self.spiral_matrix.append(self.nmatrix[self.i][self.j])\n",
    "            self.visited.append((self.i,self.j))\n",
    "            # right bottom left top - clockwise\n",
    "\n",
    "            if self.direction == \"right\":\n",
    "                if (self.i,self.j+1) in self.visited:\n",
    "                    self.direction = \"bottom\"\n",
    "                    continue\n",
    "                if self.nmatrix[self.i][self.j+1]==0:\n",
    "                    self.direction = \"bottom\"\n",
    "\n",
    "                else:self.j+=1\n",
    "            if self.direction == \"bottom\":\n",
    "                if (self.i+1,self.j) in self.visited:\n",
    "                    self.direction = \"left\"\n",
    "                    continue\n",
    "                if self.nmatrix[self.i+1][self.j]==0:\n",
    "                    self.direction = \"left\"\n",
    "\n",
    "                else:self.i+=1\n",
    "            if self.direction == \"left\":\n",
    "                if (self.i,self.j-1) in self.visited:\n",
    "                    self.direction = \"top\"\n",
    "                    continue\n",
    "                if self.nmatrix[self.i][self.j-1]==0:\n",
    "                    direction = \"top\"\n",
    "\n",
    "                else:self.j-=1\n",
    "            if self.direction == \"top\":\n",
    "                if (self.i-1,self.j) in self.visited:\n",
    "                    self.direction = \"right\"\n",
    "                    self.j=self.j+1\n",
    "                    continue\n",
    "                if self.nmatrix[self.i-1][self.j]==0:\n",
    "                    self.direction = \"right\"\n",
    "                else:self.i-=1\n",
    "        return self.spiral_matrix\n",
    "        return self.spiral_matrix"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[101, 101, 101, 101], [101, 2, 5, 101], [101, 8, 4, 101], [101, 0, -1, 101], [101, 101, 101, 101]]\n"
     ]
    }
   ],
   "source": [
    "actual_matrix = [[2, 5], [8, 4], [0, -1]]\n",
    "n = len(actual_matrix[0])\n",
    "x = [101 for _ in range(n + 2)]\n",
    "# print(x)\n",
    "[lst.append(101) for lst in actual_matrix]\n",
    "# print(actual_matrix)\n",
    "[lst.insert(0, 101) for lst in actual_matrix]\n",
    "# print(actual_matrix)\n",
    "actual_matrix.insert(0, x)\n",
    "actual_matrix.append(x)\n",
    "print(actual_matrix)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 12, -5]\n"
     ]
    }
   ],
   "source": [
    "# 370. Range Sum Query - Mutable\n",
    "# leetcode.com/problems/range-sum-query-mutable/\n",
    "class NumArray:\n",
    "    def __init__(self,nums):\n",
    "        self.tree = [0]\n",
    "        self.N = 0\n",
    "        self.construct(nums)\n",
    "\n",
    "    def LSB(self,index):\n",
    "        return index & (-index)\n",
    "\n",
    "    def add(self,index,val):\n",
    "        while index <= len(self.tree):\n",
    "            self.tree[index] += val\n",
    "            index = index + self.LSB(index)\n",
    "        return self.tree\n",
    "\n",
    "    def update(self,index,val):\n",
    "        return self.add(index+1,val-self.tree[index])\n",
    "\n",
    "    def prefixSum(self,i):\n",
    "        sum = 0\n",
    "\n",
    "        while i>0:\n",
    "            sum += self.tree[i]\n",
    "            i = i - self.LSB(i)\n",
    "\n",
    "        return sum\n",
    "\n",
    "    def sumRange(self,i,j):\n",
    "        if i == 0:\n",
    "            return self.prefixSum(j)\n",
    "        else:\n",
    "            return self.prefixSum(j) - self.prefixSum(i-1)\n",
    "\n",
    "    def construct(self,values):\n",
    "        self.tree += values.copy()\n",
    "        for i in range(1,len(self.tree)):\n",
    "            j = i + self.LSB(i)\n",
    "            if j < self.N:\n",
    "                self.tree[j] = self.tree[i] + self.tree[j]\n",
    "        return self.tree\n",
    "    def getTree(self):\n",
    "        return self.tree\n",
    "\n",
    "# obj = NumArray([-1])\n",
    "# print(obj.sumRange(0,0))\n",
    "# print(obj.update(0,1))\n",
    "# print(obj.sumRange(0,0))\n",
    "\n",
    "# obj = NumArray([1,3,5])\n",
    "# print(obj.sumRange(0,2))\n",
    "# print(obj.update(1,2))\n",
    "# print(obj.sumRange(0,2))\n",
    "\n",
    "# obj = NumArray([-1])\n",
    "# # print(obj.update(0,3))\n",
    "# print(obj.sumRange(0,0))\n",
    "# print(obj.update(0,1))\n",
    "# print(obj.sumRange(0,0))\n",
    "\n",
    "obj = NumArray([9,-8])\n",
    "print(obj.update(0,3))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "outputs": [
    {
     "data": {
      "text/plain": "0"
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def LSB(index):\n",
    "    return index & (-index)\n",
    "LSB(0)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 5\n",
      "1\n",
      "5 4\n",
      "2\n",
      "4 3\n",
      "3\n",
      "3 1\n",
      "4\n",
      "1 2\n",
      "5\n",
      "2 5\n",
      "6\n",
      "5 4\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "\n",
    "def solve(q):\n",
    "    count = 0\n",
    "    temp = 1\n",
    "    i = 1\n",
    "    step=0\n",
    "    while count<=len(q):\n",
    "        # temp = q[i]\n",
    "        # if temp == q[q[temp]]:\n",
    "        #     count+=1\n",
    "        #     i = temp\n",
    "        # else:\n",
    "        #     i = i + 1\n",
    "        #\n",
    "        if q[i] == i:\n",
    "            i += 1\n",
    "        else:\n",
    "            temp = q[i]\n",
    "            i = temp\n",
    "            step+=1\n",
    "        print(temp,q[i])\n",
    "        count += 1\n",
    "        print(step)\n",
    "q = [0,2,5,1,3,4]\n",
    "# q = [0,2,1,5,3,4]\n",
    "solve(q)"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "outputs": [
    {
     "data": {
      "text/plain": "[[0, 0, 0, 0, 0, 0],\n [0, 0, 0, 0, 0, 0],\n [0, 0, 0, 0, 0, 0],\n [0, 0, 0, 0, 0, 0],\n [0, 0, 0, 0, 0, 0],\n [0, 0, 0, 0, 0, 0]]"
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "array = q = [0,2,5,1,3,4]\n",
    "adjacency_matrix = [[0 for _ in range(len(array))] for _ in range(len(array))]\n",
    "adjacency_matrix"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "outputs": [
    {
     "data": {
      "text/plain": "[[0, 0, 0, 0, 0, 0],\n [0, 0, 1, 0, 0, 0],\n [0, 1, 0, 0, 0, 0],\n [0, 0, 0, 0, 0, 1],\n [0, 0, 0, 1, 0, 0],\n [0, 0, 0, 0, 1, 0]]"
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "array = q = [0,2,1,5,3,4]\n",
    "adjacency_matrix = [[0 for _ in range(len(array))] for _ in range(len(array))]\n",
    "for i in range(1,len(array)):\n",
    "    adjacency_matrix[i][q[i]] = 1\n",
    "adjacency_matrix[:][:]"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "# 729. My Calendar I\n",
    "# leetcode.com/problems/my-calendar-i/\n",
    "\n",
    "class MyCalendar:\n",
    "    def __init__(self):\n",
    "        self.calendar = {}\n",
    "    def book(self,start,end):\n",
    "        for s,e in self.calendar.items():\n",
    "            if start<e and end>s:\n",
    "                return False\n",
    "        self.calendar[start] = end\n",
    "        return True\n",
    "\n",
    "myCalendar = MyCalendar()\n",
    "print(myCalendar.book(10,20))\n",
    "print(myCalendar.book(15,25))\n",
    "print(myCalendar.book(20,30))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hello World\n"
     ]
    }
   ],
   "source": [
    "print(\"Hello World\")"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-1, -1, -1, -1, 4, -1, -1]\n"
     ]
    }
   ],
   "source": [
    "# 1706. Where Will the Ball Fall\n",
    "# leetcode.com/problems/where-will-the-ball-fall/\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.row = 0\n",
    "        self.col = 0\n",
    "        self.output = []\n",
    "\n",
    "    def traverse(self,grid):\n",
    "        # print(self.row,self.col)\n",
    "\n",
    "        if self.col == len(grid[0])-1:\n",
    "            if grid[self.row][self.col] == 1:\n",
    "                return -1\n",
    "\n",
    "        if self.col == 0:\n",
    "            if grid[self.row][self.col] == -1:\n",
    "                return -1\n",
    "\n",
    "        if grid[self.row][self.col] == 0:\n",
    "            # print(\"Reached bottom\")\n",
    "            return self.col\n",
    "\n",
    "\n",
    "\n",
    "        if grid[self.row][self.col] == 1 and grid[self.row][self.col+1] == -1:\n",
    "            # print(\"Checking RV\")\n",
    "            return -1\n",
    "        if grid[self.row][self.col] == -1 and grid[self.row][self.col-1] == 1:\n",
    "            # print(\"Checking LV\")\n",
    "            return -1\n",
    "\n",
    "        if grid[self.row][self.col]== 1 and grid[self.row][self.col+1] == 1:\n",
    "            self.col += 1\n",
    "            self.row += 1\n",
    "            # print(\"Moving BR\")\n",
    "            return self.traverse(grid)\n",
    "\n",
    "        if grid[self.row][self.col]== -1 and grid[self.row][self.col-1] == -1:\n",
    "            self.col -= 1\n",
    "            self.row += 1\n",
    "            # print(\"Moving BL\")\n",
    "            return self.traverse(grid)\n",
    "\n",
    "    def findBall(self,grid):\n",
    "        grid.append([0 for _ in range(len(grid[0]))])\n",
    "        # print(grid)\n",
    "        for col in range(len(grid[0])):\n",
    "            self.col = col\n",
    "            self.row = 0\n",
    "\n",
    "            # if self.col == len(grid[0])-1:\n",
    "            #     if grid[self.row][self.col] == 1:\n",
    "            #         self.output.append(-1)\n",
    "            # else:\n",
    "            self.output.append(self.traverse(grid))\n",
    "\n",
    "            # if self.col == 0:\n",
    "            #     if grid[self.row][self.col] == -1:\n",
    "            #         self.output.append(-1)\n",
    "            # else:\n",
    "            #     self.output.append(self.traverse(grid))\n",
    "\n",
    "        return self.output\n",
    "\n",
    "\n",
    "# grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]\n",
    "# grid = [[-1]]\n",
    "# grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]\n",
    "# grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]\n",
    "# grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]\n",
    "grid = [[-1,1,1,-1,1,1,-1],[-1,-1,1,-1,-1,-1,-1]]\n",
    "obj = Solution()\n",
    "\n",
    "print(obj.findBall(grid))"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 5\n"
     ]
    }
   ],
   "source": [
    "grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[0,0,0,0,0]]\n",
    "print(len(grid),len(grid[0]))\n",
    "# row ,col"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n"
    }
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}