Queue & Stack.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <font color=\"hotpink\"> Queue and Stacks </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Circular Queue\n",
    "A more efficient way is to use a circular queue. Specifically, we may use a fixed-size array and two pointers to indicate the starting position and the ending position. And the goal is to reuse the wasted storage we mentioned previously.\n",
    "\n",
    "Let's take a look at an example to see how a circular queue works. You should pay attention to the strategy we use to enqueue or dequeue an element.\n",
    "\n",
    "<img src=\"https://media.geeksforgeeks.org/wp-content/uploads/Circular-queue_1.png\" alt=\"circular queue\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Design Circular Queue\n",
    "Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called \"Ring Buffer\".\n",
    "\n",
    "One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.\n",
    "\n",
    "Implementation the MyCircularQueue class:\n",
    "* MyCircularQueue(k) Initializes the object with the size of the queue to be k.\n",
    "* int Front() Gets the front item from the queue. If the queue is empty, return -1.\n",
    "* int Rear() Gets the last item from the queue. If the queue is empty, return -1.\n",
    "* boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.\n",
    "* boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful.\n",
    "* boolean isEmpty() Checks whether the circular queue is empty or not.\n",
    "* boolean isFull() Checks whether the circular queue is full or not.\n",
    "* You must solve the problem without using the built-in queue data structure in your programming language. \n",
    "\n",
    " \n",
    "*Example 1:* <br>\n",
    "Input: <br>\n",
    "[\"MyCircularQueue\", \"enQueue\", \"enQueue\", \"enQueue\", \"enQueue\", \"Rear\", \"isFull\", \"deQueue\", \"enQueue\", \"Rear\"] <br>\n",
    "[[3], [1], [2], [3], [4], [], [], [], [4], []] <br>\n",
    "Output: \n",
    "[null, true, true, true, false, 3, true, true, true, 4] <br>\n",
    "Explanation :\n",
    "* MyCircularQueue myCircularQueue = new MyCircularQueue(3);\n",
    "* myCircularQueue.enQueue(1); // return True\n",
    "* myCircularQueue.enQueue(2); // return True\n",
    "* myCircularQueue.enQueue(3); // return True\n",
    "* myCircularQueue.enQueue(4); // return False\n",
    "* myCircularQueue.Rear();     // return 3\n",
    "* myCircularQueue.isFull();   // return True\n",
    "* myCircularQueue.deQueue();  // return True\n",
    "* myCircularQueue.enQueue(4); // return True\n",
    "* myCircularQueue.Rear();     // return 4\n",
    " \n",
    "\n",
    "*Constraints:* <br>\n",
    "* 1 <= k <= 1000\n",
    "* 0 <= value <= 1000\n",
    "* At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True 10 10\n",
      "True 20 10\n",
      "True 40 10\n",
      "[10, 20, 40]\n",
      "False 40 10\n",
      "[10, 20, 40]\n",
      "----------------------------------------------------------------------------------------------------\n",
      "True\n",
      "True 40 20\n",
      "[10, 20, 40]\n",
      "True 40 40\n",
      "True -1 -1\n",
      "[10, 20, 40]\n",
      "False -1 -1\n",
      "[10, 20, 40]\n"
     ]
    }
   ],
   "source": [
    "class MyCircularQueue(object):\n",
    "\n",
    "    def __init__(self, k):\n",
    "        \"\"\"\n",
    "        :type size: int\n",
    "        \"\"\"\n",
    "        self.size = k\n",
    "        self.front = -1\n",
    "        self.rear = -1\n",
    "        self.que = [None] * k\n",
    "        \n",
    "\n",
    "    def enQueue(self, value):\n",
    "        \"\"\"\n",
    "        :type value: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if self.isFull():\n",
    "            return False\n",
    "        elif self.front == -1:\n",
    "            self.front = 0\n",
    "            \n",
    "        self.rear = (self.rear + 1) % self.size\n",
    "        self.que[self.rear] = value\n",
    "        return True\n",
    "            \n",
    "\n",
    "    def deQueue(self):\n",
    "        \"\"\"\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if self.isEmpty():\n",
    "            return False\n",
    "        \n",
    "        if self.front == self.rear:\n",
    "            self.front = self.rear = -1\n",
    "            return True\n",
    "        \n",
    "        self.front = (self.front + 1) % self.size\n",
    "        return True\n",
    "    \n",
    "\n",
    "    def Front(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if self.isEmpty():\n",
    "            return -1\n",
    "        return self.que[self.front]\n",
    "\n",
    "    \n",
    "    def Rear(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if self.isEmpty():\n",
    "            return -1\n",
    "        return self.que[self.rear]\n",
    "    \n",
    "\n",
    "    def isEmpty(self):\n",
    "        \"\"\"\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.front == -1\n",
    "\n",
    "    \n",
    "    def isFull(self):\n",
    "        \"\"\"\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return ((self.rear + 1) % self.size) == self.front\n",
    "            \n",
    "\n",
    "# Your MyCircularQueue object will be instantiated and called as such:\n",
    "obj = MyCircularQueue(3)\n",
    "print(obj.isEmpty())\n",
    "print(obj.enQueue(10), obj.Rear(), obj.Front())\n",
    "print(obj.enQueue(20), obj.Rear(), obj.Front())\n",
    "print(obj.enQueue(40), obj.Rear(), obj.Front())\n",
    "print(obj.que)\n",
    "print(obj.enQueue(50), obj.Rear(), obj.Front())\n",
    "print(obj.que)\n",
    "\n",
    "print('-'*100)\n",
    "print(obj.isFull())\n",
    "print(obj.deQueue(), obj.Rear(), obj.Front())\n",
    "print(obj.que)\n",
    "print(obj.deQueue(), obj.Rear(), obj.Front())\n",
    "print(obj.deQueue(), obj.Rear(), obj.Front())\n",
    "print(obj.que)\n",
    "print(obj.deQueue(), obj.Rear(), obj.Front())\n",
    "print(obj.que)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Number of Islands\n",
    "Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.\n",
    "\n",
    "An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.\n",
    "\n",
    " \n",
    "*Example 1:* <br>\n",
    "Input:\n",
    "`grid = [\n",
    "          [\"1\",\"1\",\"1\",\"1\",\"0\"], \n",
    "          [\"1\",\"1\",\"0\",\"1\",\"0\"], \n",
    "          [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "          [\"0\",\"0\",\"0\",\"0\",\"0\"] \n",
    "            ]`<br>\n",
    "Output: 1\n",
    "\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: \n",
    "`grid = [ \n",
    "          [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "          [\"1\",\"1\",\"0\",\"0\",\"0\"], \n",
    "          [\"0\",\"0\",\"1\",\"0\",\"0\"], \n",
    "          [\"0\",\"0\",\"0\",\"1\",\"1\"] \n",
    "            ]`<br>\n",
    "Output: 3\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* m == grid.length\n",
    "* n == grid[i].length\n",
    "* 1 <= m, n <= 300\n",
    "* grid[i][j] is '0' or '1'.\n",
    "\n",
    "\n",
    "***\n",
    "*Solution:* <br>\n",
    "`\n",
    "In-first iteration all '1' nodes are visited that counts to an island (For Input 1).\n",
    "1->1->1->1  0\n",
    "|  |     |\n",
    "v  v     v\n",
    "1  1  0  1->1\n",
    "|  |  \n",
    "v  v\n",
    "1  1  0  0  0\n",
    "0  0  0  0  0\n",
    "`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):    \n",
    "    def numIslands(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        visited = [[0] * col  for r in range(row)]\n",
    "        \n",
    "        \n",
    "        def bfs(i, j):\n",
    "            \"\"\"\n",
    "            i and j are the row, col respectively of the node\n",
    "            \"\"\"\n",
    "            # If node is already visited\n",
    "            if visited[i][j]:\n",
    "                return 0\n",
    "            \n",
    "            visited[i][j] = 1\n",
    "            que = [(i, j)]\n",
    "            while que:\n",
    "                # remove the node from the rear and then start exploring the neighbouring node\n",
    "                r, c = que.pop() \n",
    "                \n",
    "                for k, l in [(r+1,c), (r,c+1), (r-1, c), (r, c-1)]:\n",
    "                    if (0 <= k < row) and (0 <= l < col) and not visited[k][l] and grid[k][l] == '1':\n",
    "                        visited[k][l] = 1\n",
    "                        que.append((k, l))\n",
    "            return 1\n",
    "        \n",
    "        \n",
    "        res = 0\n",
    "        for r in range(row):\n",
    "            for c in range(col):\n",
    "                if grid[r][c] == '1':\n",
    "                    res += bfs(r, c)\n",
    "        \n",
    "        return res\n",
    "\n",
    "    \n",
    "    \n",
    "if __name__ == '__main__':\n",
    "    grid = [ \n",
    "          [\"1\",\"1\",\"0\",\"0\",\"0\"],\n",
    "          [\"1\",\"1\",\"0\",\"0\",\"0\"], \n",
    "          [\"0\",\"0\",\"1\",\"0\",\"0\"], \n",
    "          [\"0\",\"0\",\"0\",\"1\",\"1\"] \n",
    "            ]\n",
    "    obj = Solution()\n",
    "    print(obj.numIslands(grid))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Perfect Squares\n",
    "Given an integer n, return the least number of perfect square numbers that sum to n.\n",
    "\n",
    "A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.\n",
    "\n",
    " \n",
    "*Example 1:* <br>\n",
    "Input: n = 12 <br>\n",
    "Output: 3 <br>\n",
    "Explanation: 12 = 4 + 4 + 4. <br>\n",
    "\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: n = 13 <br>\n",
    "Output: 2 <br>\n",
    "Explanation: 13 = 4 + 9. <br>\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* $1 <= n <= 10^4$\n",
    "\n",
    "***\n",
    "*Solution:*<br>\n",
    "* Not solved by **me**.\n",
    "* **Decision tree**\n",
    "<img src=\"https://assets.leetcode.com/users/images/4bda9ee4-a4d3-41bc-9180-5f1f931bab23_1633835670.4654868.jpeg\" alt=\"solution\" width=500 />\n",
    "* Using **MEMOIZATION**\n",
    "\n",
    "```\n",
    "def solve(n):\n",
    "    if n==0:\n",
    "        return 0\n",
    "    if n<0:\n",
    "        return float(\"inf\")\n",
    "    if memo[n]!=-1:\n",
    "        return memo[n]\n",
    "    mini = n\n",
    "    i = 1\n",
    "    while i*i<=n:\n",
    "        mini = min(mini, solve(n-(i*i)))\n",
    "        i+=1\n",
    "    memo[n] = mini+1\n",
    "    return memo[n]\n",
    "    \n",
    "memo = [-1]*(n+1)\n",
    "solve(n)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "class Solution(object):\n",
    "    def numSquares(self, n):\n",
    "        \"\"\"\n",
    "        :type n: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # corner case, if n is a perfect sq.\n",
    "        n_sqrt = math.sqrt(n)\n",
    "        if math.floor(n_sqrt) == math.ceil(n_sqrt):\n",
    "            return 1\n",
    "        \n",
    "        range_upto = int(n_sqrt) + 1\n",
    "        squares = [i*i  for i in range(1, range_upto)]\n",
    "        \n",
    "        # using bfs\n",
    "        que = [n]\n",
    "        cnt = 0\n",
    "        \n",
    "        while que:\n",
    "            cnt += 1\n",
    "            \n",
    "            for _ in range(len(que)):\n",
    "                node = que.pop(0)\n",
    "                \n",
    "                for sq in squares:\n",
    "                    if sq == node:\n",
    "                        return cnt\n",
    "                    elif node < sq:\n",
    "                        break\n",
    "                        \n",
    "                    que.append(node - sq)\n",
    "            \n",
    "            # eliminate duplicates to avoid exponential calls\n",
    "            que = list(set(que))\n",
    "        return cnt\n",
    "        \n",
    "        \n",
    "\n",
    "# main\n",
    "obj = Solution()\n",
    "print(obj.numSquares(13))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Min Stack\n",
    "Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.\n",
    "\n",
    "Implement the MinStack class:\n",
    "* MinStack() initializes the stack object.\n",
    "* void push(int val) pushes the element val onto the stack.\n",
    "* void pop() removes the element on the top of the stack.\n",
    "* int top() gets the top element of the stack.\n",
    "* int getMin() retrieves the minimum element in the stack.\n",
    " \n",
    "\n",
    "*Example 1:* <br>\n",
    "Input: <br>\n",
    "[\"MinStack\",\"push\",\"push\",\"push\",\"getMin\",\"pop\",\"top\",\"getMin\"] <br>\n",
    "[[],[-2],[0],[-3],[],[],[],[]] <br>\n",
    "Output: <br>\n",
    "[null,null,null,null,-3,null,0,-2] <br>\n",
    "Explanation: <br>\n",
    "MinStack minStack = new MinStack(); <br>\n",
    "minStack.push(-2); <br>\n",
    "minStack.push(0); <br>\n",
    "minStack.push(-3); <br>\n",
    "minStack.getMin(); // return -3 <br>\n",
    "minStack.pop(); <br>\n",
    "minStack.top();    // return 0 <br>\n",
    "minStack.getMin(); // return -2 <br>\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* $-2^{31} <= val <= 2^{31} - 1$\n",
    "* Methods pop, top and getMin operations will always be called on **non-empty** stacks.\n",
    "* At most $3 * 10^4$ calls will be made to push, pop, top, and getMin.\n",
    "***\n",
    "\n",
    "**Solution:** <br>\n",
    "Each node of stack contains:\n",
    "1. Data field\n",
    "2. Minimum value till encounter, this gives the **time complexity of O(1)** to know the minimum val in stack and **space complexity of O(2n) => O(n)**.\n",
    "\n",
    "```\n",
    "      node\n",
    "     /    \\\n",
    " data      minVal\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[-2, -2], [0, -2], [-3, -3]]\n",
      "-3\n",
      "0\n",
      "[[-2, -2], [0, -2]]\n",
      "-2\n",
      "----------------------------------------------------------------------\n",
      "[[-2, -2]]\n",
      "-2\n",
      "[[-2, -2], [8, -2], [-17, -17]]\n",
      "-17\n"
     ]
    }
   ],
   "source": [
    "class MinStack(object):\n",
    "    def __init__(self):\n",
    "        self.top_ = -1\n",
    "        self.min_val = 2 ** 64   # to keep track of min value in stack\n",
    "        self.data = []\n",
    "        \n",
    "        \n",
    "    def push(self, val):\n",
    "        \"\"\"\n",
    "        :type val: int\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        self.top_ += 1\n",
    "        \n",
    "        # to change minVal if provided val is less than minVal\n",
    "        if self.min_val > val:\n",
    "            self.min_val = val\n",
    "            \n",
    "        # store min_val data with the node itself\n",
    "        self.data.append([val, self.min_val])\n",
    "            \n",
    "        \n",
    "    def pop(self):\n",
    "        \"\"\"\n",
    "        :rtype: None\n",
    "        \"\"\"\n",
    "        # remove last element if list is not empty ie. shrink the list\n",
    "        if self.data:\n",
    "            self.data = self.data[:-1]\n",
    "            \n",
    "        self.top_ -= 1\n",
    "        # if list becomes empty after pop, then make min_val high\n",
    "        if self.top_ == -1:\n",
    "            self.min_val = 2 ** 64\n",
    "        else:\n",
    "            self.min_val = self.data[self.top_][1]\n",
    "            \n",
    "            \n",
    "    def top(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if self.data:\n",
    "            return self.data[self.top_][0]\n",
    "        \n",
    "        \n",
    "    def getMin(self):\n",
    "        \"\"\"\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # return the min_val stored during node construction\n",
    "        if self.data:\n",
    "            return self.data[self.top_][1]\n",
    "\n",
    "\n",
    "    \n",
    "# main\n",
    "stk = MinStack()\n",
    "stk.push(-2)\n",
    "stk.push(0)\n",
    "stk.push(-3)\n",
    "print(stk.data)\n",
    "print(stk.getMin())\n",
    "stk.pop()\n",
    "print(stk.top())\n",
    "print(stk.data)\n",
    "print(stk.getMin())\n",
    "\n",
    "print('-' * 70)\n",
    "# stk.pop()\n",
    "stk.pop()\n",
    "print(stk.data)\n",
    "stk.push(8)\n",
    "print(stk.getMin())\n",
    "stk.push(-17)\n",
    "print(stk.data)\n",
    "print(stk.getMin())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##   Daily Temperatures\n",
    "\n",
    "Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.\n",
    "\n",
    " \n",
    "*Example 1:* <br>\n",
    "Input: temperatures = [73,74,75,71,69,72,76,73] <br>\n",
    "Output: [1,1,4,2,1,1,0,0] \n",
    "\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: temperatures = [30,40,50,60] <br>\n",
    "Output: [1,1,1,0]\n",
    "\n",
    "\n",
    "*Example 3:* <br>\n",
    "Input: temperatures = [30,60,90]\n",
    "Output: [1,1,0]\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* $1 <= temperatures.length <= 10^5$\n",
    "* 30 <= temperatures[i] <= 100\n",
    "\n",
    "\n",
    "***\n",
    "*Solution:* <br>\n",
    "* Using **Monotonic Stack** ( A monotonic stack is simply a stack where the elements are always in sorted order). <br>\n",
    "* Monotonic stacks are a good option when a problem involves comparing the size of numeric elements, with their order being relevant.\n",
    "\n",
    "Algorithm:\n",
    "\n",
    "1. Initialize an array answer with the same length as temperatures and all values initially set to 0. Also, initialize a stack as an empty array.\n",
    "\n",
    "2. Iterate through temperatures. At each index currDay:\n",
    "    * If the stack is not empty, that means there are previous days for which we have not yet seen a warmer day. While the current temperature is warmer than the temperature of prevDay (the index of the day at the top of the stack):\n",
    "        * Set answer[prevDay] equal to the number of days that have passed between prevDay and the current day, that is, answer[prevDay] = currDay - prevDay.\n",
    "    * Push the current index currDay onto the stack.\n",
    "    \n",
    "3. Return answer.\n",
    "\n",
    "**Time and space complexity :** O(N)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def dailyTemperaturesNaive(self, temperatures):\n",
    "        \"\"\"\n",
    "        :type temperatures: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # naive-approach using O(n^2) time complexity, gives TLE\n",
    "        n = len(temperatures)\n",
    "        res = [0] * n\n",
    "        \n",
    "        for day in range(n):\n",
    "            for fut_day in range(day+1, n):\n",
    "                if temperatures[fut_day] > temperatures[day]:\n",
    "                    res[day] = fut_day - day\n",
    "                    break\n",
    "        return res\n",
    "        \n",
    "        \n",
    "    def dailyTemperatures(self, temperatures):\n",
    "        n = len(temperatures)\n",
    "        answer = [0] * n\n",
    "        stack = []\n",
    "        \n",
    "        for curr_day, curr_temp in enumerate(temperatures):\n",
    "            # Pop until the current day's temperature is not\n",
    "            # warmer than the temperature at the top of the stack\n",
    "            while stack and temperatures[stack[-1]] < curr_temp:\n",
    "                prev_day = stack.pop()\n",
    "                answer[prev_day] = curr_day - prev_day\n",
    "            stack.append(curr_day)\n",
    "        \n",
    "        return answer\n",
    "    \n",
    "\n",
    "# main\n",
    "obj = Solution()\n",
    "temp = [73,74,75,71,69,72,76,73]\n",
    "temp = [30,60,90,60]\n",
    "print(obj.dailyTemperatures(temp))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Evaluate Reverse Polish Notation\n",
    "Evaluate the value of an arithmetic expression in Reverse Polish Notation.\n",
    "\n",
    "Valid operators are +, -, *, and /. Each operand may be an integer or another expression.\n",
    "\n",
    "**Note that division between two integers should truncate toward zero.**\n",
    "\n",
    "It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.\n",
    "\n",
    " \n",
    "*Example 1:* <br>\n",
    "Input: tokens = `[\"2\",\"1\",\"+\",\"3\",\"*\"]` <br>\n",
    "Output: 9 <br>\n",
    "Explanation: ((2 + 1) * 3) = 9\n",
    "\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: tokens = `[\"4\",\"13\",\"5\",\"/\",\"+\"]` <br>\n",
    "Output: 6 <br>\n",
    "Explanation: (4 + (13 / 5)) = 6\n",
    "\n",
    "\n",
    "*Example 3:* <br>\n",
    "Input: tokens = `[\"10\",\"6\",\"9\",\"3\",\"+\",\"-11\",\"*\",\"/\",\"*\",\"17\",\"+\",\"5\",\"+\"]` <br>\n",
    "Output: 22 <br>\n",
    "Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 <br>\n",
    "= ((10 * (6 / (12 * -11))) + 17) + 5 <br>\n",
    "= ((10 * (6 / -132)) + 17) + 5 <br>\n",
    "= ((10 * 0) + 17) + 5 <br>\n",
    "= (0 + 17) + 5 <br>\n",
    "= 17 + 5 <br>\n",
    "= 22\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* $1 <= tokens.length <= 10^4$\n",
    "* tokens[i] is either an operator: \"+\", \"-\", \"*\", or \"/\", or an integer in the range [-200, 200].\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "22\n"
     ]
    }
   ],
   "source": [
    "import operator\n",
    "\n",
    "class Solution(object):\n",
    "    def exprEval(self, op1, op2, oprt):\n",
    "        \"\"\"\n",
    "        Helper function to evaluate an expr \n",
    "        \"\"\"\n",
    "        ops = { \"+\": operator.add,\n",
    "               \"-\": operator.sub,\n",
    "               \"*\": operator.mul,\n",
    "               \"/\": operator.truediv\n",
    "              }\n",
    "        \n",
    "        # 6 // -132 gives -1 but we want 0 due to floor round off ie. div of two int truncates towards zero\n",
    "        # that's we use normal div first than obtain the integral part from answer\n",
    "        return int(ops[oprt](op1, op2)) if oprt == '/' else ops[oprt](op1, op2)\n",
    "    \n",
    "        \n",
    "    def evalRPN(self, tokens):\n",
    "        \"\"\"\n",
    "        :type tokens: List[str]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # we can use operator module as well to convert operators string to operator\n",
    "        operators = ['+', '-', '*', '/']\n",
    "        stack = []\n",
    "        \n",
    "        for tok in tokens:\n",
    "            # evaluate stack's top two operands if operator encounters\n",
    "            if tok in operators:\n",
    "                op2 = stack.pop(-1)\n",
    "                op1 = stack.pop(-1)\n",
    "                stack.append(self.exprEval(op1, op2, tok))\n",
    "            else:\n",
    "                stack.append(int(tok))\n",
    "                \n",
    "        return stack.pop()\n",
    "\n",
    "    \n",
    "\n",
    "# main\n",
    "obj = Solution()\n",
    "tok = [\"2\",\"1\",\"+\",\"3\",\"*\"]\n",
    "tok = [\"4\",\"13\",\"5\",\"/\",\"+\"]\n",
    "tok = [\"10\",\"6\",\"9\",\"3\",\"+\",\"-11\",\"*\",\"/\",\"*\",\"17\",\"+\",\"5\",\"+\"]\n",
    "print(obj.evalRPN(tok))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Open the Lock\n",
    "You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot.\n",
    "\n",
    "The lock initially starts at '0000', a string representing the state of the 4 wheels.\n",
    "\n",
    "You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.\n",
    "\n",
    "Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.\n",
    "\n",
    " \n",
    "*Example 1:* <br>\n",
    "Input: deadends = [\"0201\",\"0101\",\"0102\",\"1212\",\"2002\"], target = \"0202\" <br>\n",
    "Output: 6 <br>\n",
    "Explanation: <br>\n",
    "A sequence of valid moves would be \"0000\" -> \"1000\" -> \"1100\" -> \"1200\" -> \"1201\" -> \"1202\" -> \"0202\". <br>\n",
    "Note that a sequence like \"0000\" -> \"0001\" -> \"0002\" -> \"0102\" -> \"0202\" would be invalid, <br>\n",
    "because the wheels of the lock become stuck after the display becomes the dead end \"0102\".\n",
    "\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: deadends = [\"8888\"], target = \"0009\" <br>\n",
    "Output: 1 <br>\n",
    "Explanation: <br>\n",
    "We can turn the last wheel in reverse to move from \"0000\" -> \"0009\".\n",
    "\n",
    "\n",
    "*Example 3:* <br>\n",
    "Input: deadends = [\"8887\",\"8889\",\"8878\",\"8898\",\"8788\",\"8988\",\"7888\",\"9888\"], target = \"8888\" <br>\n",
    "Output: -1 <br>\n",
    "Explanation: <br>\n",
    "We can't reach the target without getting stuck. <br>\n",
    "\n",
    "\n",
    "*Example 4:* <br>\n",
    "Input: deadends = [\"0000\"], target = \"8888\" <br>\n",
    "Output: -1 <br>\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* 1 <= deadends.length <= 500\n",
    "* deadends[i].length == 4\n",
    "* target.length == 4\n",
    "* target will not be in the list deadends.\n",
    "* target and deadends[i] consist of digits only.\n",
    "***\n",
    "**Soltion:** <br>\n",
    "* We can think of this problem as a shortest path problem on a graph: there are `10000` nodes (strings `'0000'` to `'9999'`), and there is an edge between two nodes if they differ in one digit, that digit differs by 1 (wrapping around, so `'0'` and `'9'` differ by 1), and if *both* nodes are not in `deadends`.\n",
    "* Note that from '0000' to '9999' we have __10,000 possibilities__, which quite low for computers to compute, as modern computer can perform $10^9$ operations/sec.\n",
    "<br>\n",
    "\n",
    "```\n",
    "                        '0000'\n",
    "                          |\n",
    "                          v\n",
    "        ['9000', '1000', '0900', '0100', '0090', '0010', '0009', '0001'] #all possibilities for '0000'\n",
    "            |    .......................... similarly\n",
    "            v\n",
    " ['8000', '0000', '9900', '9100', '9090', '9010', '9009', '9001']\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def openLock(self, deadends, target):\n",
    "        \"\"\"\n",
    "        :type deadends: List[str]\n",
    "        :type target: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        #to remove duplicate deadends if there\n",
    "        deadends = set(deadends)\n",
    "        \n",
    "        #corner case\n",
    "        if '0000' in deadends:\n",
    "            return -1\n",
    "        \n",
    "        \n",
    "        def nextStates(s):\n",
    "            \"\"\"\n",
    "            Helper function to make further string nodes\n",
    "            \"\"\"\n",
    "            nodes = []\n",
    "            for i in range(4):\n",
    "                e = int(s[i])\n",
    "                # to generate adjacent num values\n",
    "                # for '0000' -> ['9000', '1000', '0900', '0100', '0090', '0010', '0009', '0001']\n",
    "                for x in [(e-1) % 10, (e+1) % 10]:\n",
    "                    if i == 0:\n",
    "                        nod = str(x) + s[i+1:]\n",
    "                    elif i == 3:\n",
    "                        nod = s[:i] + str(x)\n",
    "                    else:\n",
    "                        nod = s[:i] + str(x) + s[i+1:]\n",
    "                    \n",
    "                    if nod not in deadends and nod not in visited:\n",
    "                        nodes.append(nod)\n",
    "            return nodes\n",
    "            \n",
    "            \n",
    "        que = ['0000']\n",
    "        visited = set('0000')\n",
    "        level = 0\n",
    "        \n",
    "        while que:\n",
    "            for _ in range(len(que)):\n",
    "                curr_state = que.pop(0)\n",
    "                nxt_states = nextStates(curr_state)\n",
    "                \n",
    "                for state in nxt_states:\n",
    "                    if state == target:\n",
    "                        return level +1\n",
    "                    que.append(state)\n",
    "                    visited.add(state)\n",
    "            level += 1\n",
    "        \n",
    "        return -1\n",
    "    \n",
    "            \n",
    "\n",
    "# main\n",
    "obj = Solution()\n",
    "deadends = [\"0201\",\"0101\",\"0102\",\"1212\",\"2002\"]\n",
    "target = \"0202\"\n",
    "# deadends = [\"8887\",\"8889\",\"8878\",\"8898\",\"8788\",\"8988\",\"7888\",\"9888\"]\n",
    "# target = \"8888\"\n",
    "print(obj.openLock(deadends, target))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##   Binary Tree Inorder Traversal\n",
    "\n",
    "Given the root of a binary tree, return the inorder traversal of its nodes' values.\n",
    "\n",
    "*Example 1:* <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg\" alt=\"ex1\" width=100 />\n",
    "Input: root = [1,null,2,3] <br>\n",
    "Output: [1,3,2] \n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: root = [] <br>\n",
    "Output: []\n",
    "\n",
    "*Example 3:* <br>\n",
    "Input: root = [1] <br>\n",
    "Output: [1]\n",
    "\n",
    "*Example 4:* <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2020/09/15/inorder_5.jpg\" alt=\"ex2\" width=100 />\n",
    "Input: root = [1,2]\n",
    "Output: [2,1]\n",
    "\n",
    "*Example 5:*\n",
    "<img src=\"https://assets.leetcode.com/uploads/2020/09/15/inorder_4.jpg\" alt=\"ex2\" width=100 />\n",
    "Input: root = [1,null,2]\n",
    "Output: [1,2]\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* The number of nodes in the tree is in the range [0, 100].\n",
    "* -100 <= Node.val <= 100\n",
    " \n",
    "**Follow up:** Recursive solution is trivial, could you do it iteratively?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Definition for a binary tree node.\n",
    "# class TreeNode(object):\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def inorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        #corner-case\n",
    "        if root is None:\n",
    "            return []\n",
    "        \n",
    "        ans = []\n",
    "        stack = [root]\n",
    "        visited = [root]\n",
    "        \n",
    "        while stack:\n",
    "            curr = stack[-1]\n",
    "            if curr.left and curr.left not in visited:\n",
    "                visited.append(curr.left)\n",
    "                stack.append(curr.left)\n",
    "            else:\n",
    "                stack.pop()\n",
    "                ans.append(curr.val)\n",
    "                \n",
    "                if curr.right and curr.right not in visited:\n",
    "                    stack.append(curr.right)\n",
    "                    visited.append(curr.right)\n",
    "        \n",
    "        return ans   \n",
    "                \n",
    "        \n",
    "                    \n",
    "    def inorderTraversalRecursion(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res = []\n",
    "        \n",
    "        \n",
    "        def helper(root):\n",
    "            \"\"\"\n",
    "            Helper function for traversing inorder traversal\n",
    "            \"\"\"\n",
    "            if root is None:\n",
    "                return\n",
    "            \n",
    "            helper(root.left)\n",
    "            res.append(root.val)\n",
    "            helper(root.right)\n",
    "        \n",
    "        helper(root)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Clone Graph\n",
    "Given a reference of a node in a connected undirected graph.\n",
    "\n",
    "Return a deep copy (clone) of the graph.\n",
    "\n",
    "Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.\n",
    "\n",
    "```\n",
    "class Node {\n",
    "    public int val;\n",
    "    public List<Node> neighbors;\n",
    "}\n",
    "```\n",
    "*Test case format:* <br>\n",
    "For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.\n",
    "\n",
    "An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.\n",
    "\n",
    "The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.\n",
    "\n",
    " \n",
    "\n",
    "*Example 1:* <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2019/11/04/133_clone_graph_question.png\" width=400>\n",
    "Input: adjList = [[2,4],[1,3],[2,4],[1,3]] <br>\n",
    "Output: [[2,4],[1,3],[2,4],[1,3]] <br>\n",
    "Explanation: There are 4 nodes in the graph. <br>\n",
    "1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).<br>\n",
    "2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).<br>\n",
    "3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).<br>\n",
    "4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).\n",
    "\n",
    "*Example 2:* <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2020/01/07/graph.png\" width=200 />\n",
    "Input: adjList = [[]] <br>\n",
    "Output: [[]] <br>\n",
    "Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.\n",
    "\n",
    "*Example 3:* <br>\n",
    "Input: adjList = [] <br>\n",
    "Output: [] <br>\n",
    "Explanation: This an empty graph, it does not have any nodes.\n",
    "\n",
    "*Example 4:* <br>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2020/01/07/graph-1.png\" width=300 />\n",
    "Input: adjList = [[2],[1]] <br>\n",
    "Output: [[2],[1]]\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* The number of nodes in the graph is in the range [0, 100].\n",
    "* 1 <= Node.val <= 100\n",
    "* Node.val is unique for each node.\n",
    "* There are no repeated edges and no self-loops in the graph.\n",
    "* The Graph is connected and all nodes can be visited starting from the given node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def cloneGraph(self, node: 'Node') -> 'Node':\n",
    "        vist= {}\n",
    "        def helper(node):\n",
    "            if node:\n",
    "                cp= Node(node.val)\n",
    "                vist[node]=cp\n",
    "\n",
    "                for neighbor in node.neighbors:      \n",
    "                    if neighbor in vist: # copy of n has been created, just get it \n",
    "                        cp.neighbors.append(vist[neighbor])\n",
    "                    else: #the neighbor need to be created\n",
    "                        cp.neighbors.append(helper(neighbor))\n",
    "                #print(cp.val, [x.val for x in cp.neighbors])\n",
    "                return cp\n",
    "        \n",
    "        rst =  helper(node)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 232. Implement Queue using Stacks\n",
    "Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).\n",
    "\n",
    "Implement the MyQueue class:\n",
    "* *void push(int x)* Pushes element x to the back of the queue.\n",
    "* *int pop()* Removes the element from the front of the queue and returns it.\n",
    "* *int peek()* Returns the element at the front of the queue.\n",
    "* *boolean empty()* Returns true if the queue is empty, false otherwise.\n",
    "\n",
    "**Notes:** <br>\n",
    "* You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.\n",
    "* Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.\n",
    " \n",
    "\n",
    "**Example 1:** <br>\n",
    "*Input:* <br>\n",
    "[\"MyQueue\", \"push\", \"push\", \"peek\", \"pop\", \"empty\"] <br>\n",
    "[[], [1], [2], [], [], []] <br>\n",
    "*Output:* <br>\n",
    "[null, null, null, 1, 1, false] <br>\n",
    "*Explanation:* <br>\n",
    "MyQueue myQueue = new MyQueue(); <br>\n",
    "myQueue.push(1); // queue is: [1] <br>\n",
    "myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) <br>\n",
    "myQueue.peek(); // return 1 <br>\n",
    "myQueue.pop(); // return 1, queue is [2] <br>\n",
    "myQueue.empty(); // return false <br>\n",
    " \n",
    "\n",
    "**Constraints:**\n",
    "* 1 <= x <= 9\n",
    "* At most 100 calls will be made to push, pop, peek, and empty.\n",
    "* All the calls to pop and peek are valid.\n",
    " \n",
    "\n",
    "**Follow-up:** Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.\n",
    "\n",
    "***\n",
    "**Solutions:**\n",
    "* Approach #1 (Two Stacks) Push - O(n) per operation, Pop - O(1) per operation.\n",
    "<img src=\"https://leetcode.com/media/original_images/232_queue_using_stacksBPush.png\" alt=\"sol1\" width=600 />\n",
    "<img src=\"https://leetcode.com/media/original_images/232_queue_using_stacksBPop.png\" alt=\"sol1\" width=600 />\n",
    "\n",
    "* Approach #2 (Two Stacks) Push - O(1) per operation, Pop - Amortized O(1) per operation.\n",
    "<img src=\"https://leetcode.com/media/original_images/232_queue_using_stacksAPush.png\" alt=\"sol1\" width=600 />\n",
    "<img src=\"https://leetcode.com/media/original_images/232_queue_using_stacksAPop.png\" alt=\"sol1\" width=600 />\n",
    "\n",
    "\n",
    "*Amortized Analysis*<br>\n",
    "Amortized analysis gives the average performance (over time) of each operation in the worst case. The basic idea is that a worst case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus amortizing its cost.\n",
    "\n",
    "Consider this example where we start with an empty queue with the following sequence of operations applied:\n",
    "\n",
    "push_1, push_2,......, push_n, pop_1,pop_2,......., pop_n\n",
    "\n",
    "The worst case time complexity of a single pop operation is $O(n)$. Since we have nn pop operations, using the worst-case per operation analysis gives us a total of $O(n^2)$ time.\n",
    "\n",
    "However, in a sequence of operations the worst case does not occur often in each operation - some operations may be cheap, some may be expensive. Therefore, a traditional worst-case per operation analysis can give overly pessimistic bound. For example, in a dynamic array only some inserts take a linear time, though others - a constant time.\n",
    "\n",
    "In the example above, the number of times pop operation can be called is limited by the number of push operations before it. Although a single pop operation could be expensive, it is expensive only once per n times (queue size), when s2 is empty and there is a need for data transfer between s1 and s2. Hence the total time complexity of the sequence is : n (for push operations) + 2*n (for first pop operation) + n - 1 ( for pop operations) which is $O(2*n)$.This gives $O(2n/2n) = O(1)$ average time per operation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Approach 1: push O(n), pop O(1)\n",
    "class MyQueue:\n",
    "    def __init__(self):\n",
    "        self.s1 = []\n",
    "        self.s2 = []\n",
    "\n",
    "    def push(self, x):\n",
    "        while self.s1:\n",
    "            self.s2.append(self.s1.pop())\n",
    "        self.s1.append(x)\n",
    "        while self.s2:\n",
    "            self.s1.append(self.s2.pop())\n",
    "\n",
    "    def pop(self):\n",
    "        return self.s1.pop()\n",
    "\n",
    "    def peek(self):\n",
    "        return self.s1[-1]\n",
    "\n",
    "    def empty(self):\n",
    "        return not self.s1\n",
    "    \n",
    "    \n",
    "    \n",
    "#Approach 2: push O(1), pop amortized O(1)\n",
    "class MyQueue:\n",
    "    def __init__(self):\n",
    "        self.s1 = []\n",
    "        self.s2 = []\n",
    "\n",
    "    def push(self, x):\n",
    "        self.s1.append(x)\n",
    "\n",
    "    def pop(self):\n",
    "        self.peek()\n",
    "        return self.s2.pop()\n",
    "\n",
    "    def peek(self):\n",
    "        if not self.s2:\n",
    "            while self.s1:\n",
    "                self.s2.append(self.s1.pop())\n",
    "        return self.s2[-1]        \n",
    "\n",
    "    def empty(self):\n",
    "        return not self.s1 and not self.s2\n",
    "\n",
    "# Your MyQueue object will be instantiated and called as such:\n",
    "# obj = MyQueue()\n",
    "# obj.push(x)\n",
    "# param_2 = obj.pop()\n",
    "# param_3 = obj.peek()\n",
    "# param_4 = obj.empty()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Target Sum\n",
    "You are given an integer array nums and an integer target.\n",
    "\n",
    "You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.\n",
    "* For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression \"+2-1\".\n",
    "Return the number of different expressions that you can build, which evaluates to target.\n",
    "\n",
    " \n",
    "\n",
    "*Example 1:* <br>\n",
    "Input: nums = [1,1,1,1,1], target = 3 <br>\n",
    "Output: 5 <br>\n",
    "Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3. <br>\n",
    "-1 + 1 + 1 + 1 + 1 = 3 <br>\n",
    "+1 - 1 + 1 + 1 + 1 = 3 <br>\n",
    "+1 + 1 - 1 + 1 + 1 = 3 <br>\n",
    "+1 + 1 + 1 - 1 + 1 = 3 <br>\n",
    "+1 + 1 + 1 + 1 - 1 = 3\n",
    "\n",
    "*Example 2:* <br>\n",
    "Input: nums = [1], target = 1 <br>\n",
    "Output: 1\n",
    " \n",
    "\n",
    "*Constraints:*\n",
    "* 1 <= nums.length <= 20\n",
    "* 0 <= nums[i] <= 1000\n",
    "* 0 <= sum(nums[i]) <= 1000\n",
    "* -1000 <= target <= 1000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Solution:\n",
    "    count = 0\n",
    "    \n",
    "    #Time complexity: O(2^n), but it can't work for n < 21 within time specially for Python\n",
    "    def calculateRecursion(self, sum_up, index, nums, target):\n",
    "        if index == len(nums):\n",
    "            if sum_up == target:\n",
    "                self.count += 1\n",
    "        else:\n",
    "            self.calculateRecursion(sum_up + nums[index], index + 1, nums, target)\n",
    "            self.calculateRecursion(sum_up - nums[index], index + 1, nums, target)\n",
    "            \n",
    "            \n",
    "    def findTargetSumWays(self, nums, target):\n",
    "        self.calculateRecursion(0, 0, nums, target)\n",
    "        return self.count\n",
    "    \n",
    "    \n",
    "    \n",
    "# main\n",
    "obj = Solution()\n",
    "obj.findTargetSumWays([1,2,3,1], 5)"
   ]
  }
 ],
 "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.10.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}