stacks_LB.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyM2D6HwjBeFGdnj17C5VSIe",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/pranjal-tiwarigithub/CampusX/blob/main/stacks_LB.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "X-6us2CHTUqQ",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b72939dc-bea2-425c-c3e1-aebe2c5a11d5"
      },
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2"
            ]
          },
          "metadata": {},
          "execution_count": 19
        }
      ],
      "source": [
        "4//2"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Remove middle of stack"
      ],
      "metadata": {
        "id": "cWHILuSPIcvl"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def remove_middle(arr,count,size):\n",
        "  print(str(count) + str(arr))\n",
        "  if count == size//2:  ### N=5 remove 2th , N=4 remove 2th\n",
        "    arr.pop(0)\n",
        "    return\n",
        "\n",
        "  last_element = arr.pop(0)\n",
        "  remove_middle(arr,count + 1 , size)\n",
        "  ## on retrun\n",
        "  arr.insert(0,last_element)"
      ],
      "metadata": {
        "id": "enxbOqBoIbmk"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "myarr = [1,2,3,4]\n",
        "remove_middle(myarr,0,len(myarr))\n",
        "print(myarr)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "nBzju5QyJaB3",
        "outputId": "25e2274d-a575-498d-b857-867eba49aad1"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0[1, 2, 3, 4]\n",
            "1[2, 3, 4]\n",
            "2[3, 4]\n",
            "[1, 2, 4]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### insert at bottom"
      ],
      "metadata": {
        "id": "ULjcOTwByn00"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "Less than before an element\n",
        "\n",
        "striver"
      ],
      "metadata": {
        "id": "-bbad16Fyl43",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 130
        },
        "outputId": "c743ac75-7c1e-46ff-86c7-88340427d054"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "error",
          "ename": "SyntaxError",
          "evalue": "ignored",
          "traceback": [
            "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-1-fa7608324648>\"\u001b[0;36m, line \u001b[0;32m1\u001b[0m\n\u001b[0;31m    Less than before an element\u001b[0m\n\u001b[0m         ^\u001b[0m\n\u001b[0;31mSyntaxError\u001b[0m\u001b[0;31m:\u001b[0m invalid syntax\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "from os import *\n",
        "from sys import *\n",
        "from collections import *\n",
        "from math import *\n",
        "\n",
        "def findSpans(price):\n",
        "\n",
        "    stack = []\n",
        "    n = len(price)\n",
        "    answer = [1] * n\n",
        "\n",
        "    for i in range(0 , n):\n",
        "\n",
        "        count = 1\n",
        "\n",
        "        for j in range(len(stack) -1, -1 ,-1):\n",
        "\n",
        "            if price[i] < stack[j]:\n",
        "                break\n",
        "\n",
        "            count =  count + 1\n",
        "\n",
        "        ## now insert such that smallest number is at top of stack\n",
        "        answer[i] = count\n",
        "        sort_stack(price[i] , stack , len(stack))\n",
        "        print(\"stack:\" + str(stack))\n",
        "\n",
        "    return answer\n",
        "\n",
        "\n",
        "def sort_stack(val , stack , length):\n",
        "\n",
        "    if length == 0 or val <= stack[-1]:\n",
        "        stack.append(val)\n",
        "        return\n",
        "\n",
        "    last_element =  stack.pop()\n",
        "    sort_stack(val , stack , len(stack))\n",
        "    stack.append(last_element)\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\n"
      ],
      "metadata": {
        "id": "uv8-nDKNoDF6"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Minimum Cost To Make String Valid\n"
      ],
      "metadata": {
        "id": "HyzVye7w0ZVv"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from os import *\n",
        "from sys import *\n",
        "from collections import *\n",
        "from math import *\n",
        "\n",
        "def findMinimumCost(STR):\n",
        "\t# Write your code here.\n",
        "\n",
        "\t## if odd then balancing not possible\n",
        "\n",
        "\tif len(STR) % 2 == 1:\n",
        "\t\treturn -1\n",
        "\n",
        "\t### remove all balanced brackets\n",
        "\n",
        "\tstack = []\n",
        "\tfor i in range(0,len(STR)):\n",
        "\t\tif STR[i] == '{':\n",
        "\t\t\tstack.append(\"{\")\n",
        "\t\telif STR[i] == \"}\" and len(stack) !=0 and stack[-1] == \"{\" :\n",
        "\t\t\tstack.pop()\n",
        "\t\telse:\n",
        "\t\t\tstack.append(\"}\")\n",
        "\n",
        "\t## STACK now has only imbalanced brackets\n",
        "\n",
        "\ta = 0  ## len of {\n",
        "\tb = 0  ## len of }\n",
        "\n",
        "\tfor i in range(0,len(stack)):\n",
        "\t\tif stack[i] == \"{\":\n",
        "\t\t\ta = a + 1\n",
        "\t\telse:\n",
        "\t\t\tb = b + 1\n",
        "\n",
        "\treturn ((a+1) // 2 + (b+1) // 2)\n",
        "\n"
      ],
      "metadata": {
        "id": "w4z1dEez0Z_D"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Largest rectangle in a histogram\n"
      ],
      "metadata": {
        "id": "pUUPYBfPAreb"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "\n",
        "### to get next smaller number index\n",
        "\n",
        "def next_smaller_number_index(arr , n):\n",
        "\n",
        "    answer = [n] * n\n",
        "    stack = []\n",
        "\n",
        "    ## stack stores index of smallest number on right\n",
        "    ## i is index\n",
        "\n",
        "\n",
        "    # start from rightmost end\n",
        "    for i in range(n -  1  , -1 , -1):\n",
        "\n",
        "        ## remove elements from stacks if they bigger than arr element\n",
        "        ## we want index of array element just smaller than our arr element\n",
        "\n",
        "        while len(stack) != 0 and arr[stack[-1]] >= arr[i]:\n",
        "            stack.pop()\n",
        "\n",
        "        if len(stack) != 0:\n",
        "            answer[i] = stack[-1]\n",
        "\n",
        "        stack.append(i)\n",
        "\n",
        "    ## return -1 as index of rightmost shortest element makes no sense as we are measuring breadth\n",
        "    ## -1 means there is no shorter element on the right\n",
        "    ## hence replace -1 by n i.e last elements's postion\n",
        "\n",
        "\n",
        "    return answer\n",
        "\n",
        "def smallest_element_onLeft_index(arr , n):\n",
        "\n",
        "    answer = [-1] *  n\n",
        "    stack = []\n",
        "\n",
        "    for i in range(0,n,1):\n",
        "\n",
        "        while len(stack) != 0  and arr[stack[-1]] >= arr[i]:\n",
        "            ## keep popping bigger numbers\n",
        "            stack.pop()\n",
        "\n",
        "        ## stop now at top we have index of number which is just shorter than arr element\n",
        "\n",
        "        if len(stack) != 0:\n",
        "            answer[i] = stack[-1]\n",
        "\n",
        "        stack.append(i)\n",
        "\n",
        "    return answer\n",
        "\n",
        "\n",
        "\n",
        "def largestRectangle(arr):\n",
        "    # Write your code here\n",
        "    next_smaller = next_smaller_number_index(arr , len(arr))\n",
        "    prev  = smallest_element_onLeft_index(arr ,len(arr))\n",
        "\n",
        "    area  = 0\n",
        "\n",
        "    for i in range(0,len(arr)):\n",
        "        height = arr[i]\n",
        "        breadth = next_smaller[i] - prev[i] -1\n",
        "        new_area = height * breadth\n",
        "\n",
        "        area =  max(area , new_area)\n",
        "\n",
        "    return area\n",
        "\n"
      ],
      "metadata": {
        "id": "tSxDHSu1Arrk"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "circular queue"
      ],
      "metadata": {
        "id": "-pOPXglnhUY0"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from os import *\n",
        "from sys import *\n",
        "from collections import *\n",
        "from math import *\n",
        "\n",
        "class CircularQueue:\n",
        "\n",
        "    def __init__ (self, n):\n",
        "        # Initialize your data structure.\n",
        "\n",
        "        self.queue = [-1 for i in range(n)]\n",
        "        self.front = -1\n",
        "        self.rear =  -1\n",
        "        self.size = n\n",
        "\n",
        "    # Enqueues 'X' into the queue. Returns true if it gets pushed into the queue, and false otherwise.\n",
        "    def enqueue(self, value):\n",
        "        # Write your code here.\n",
        "\n",
        "\n",
        "        if (self.rear + 1) % self.size == self.front:\n",
        "            return False\n",
        "\n",
        "        elif self.rear == -1 :\n",
        "             self.front = 0 ## ek enqueue hogaya hai\n",
        "\n",
        "        self.rear = (self.rear + 1) % self.size\n",
        "        self.queue[self.rear] = value\n",
        "\n",
        "        return True\n",
        "\n",
        "\n",
        "    # Dequeues pop element from queue. Returns -1 if the queue is empty, otherwise returns the popped element.\n",
        "    def dequeue(self):\n",
        "        # Write your code here.\n",
        "\n",
        "        if self.front == -1:\n",
        "            return -1\n",
        "\n",
        "        elif self.rear == self.front:\n",
        "            answer = self.queue[self.rear]\n",
        "            self.front = self.rear = -1\n",
        "            return answer\n",
        "\n",
        "        answer = self.queue[self.front]\n",
        "        self.front = (self.front + 1) % self.size\n",
        "        return answer\n",
        "\n"
      ],
      "metadata": {
        "id": "hEn-7srIhV01"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}