Algorithms_Methodology.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# <font color=\"hotpink\"> Algorithms or Methodology </font>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "## <font color=\"#fe7401\"> Binary Search </font>\n",
    "***\n",
    "\n",
    "+ Don't write mid = (low + high) / 2, as this can lead to overflow.\n",
    "    + Write mid = low + (high - low) / 2, this will give desired results.\n",
    "    + When we add two signed 32-bit integers, we always run the risk of overflow. We can try it yourself with low = 1 and high = Integer.MAX_VALUE. We'll notice however that the second way stops this overflow from occurring, and you get your expected result.\n",
    "+ Examples for it's usage:  <a href = \"https://leetcode.com/problems/first-bad-version/discuss/769685/Python-Clear-explanation-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems\" alt=\"LeetCode Post\"> link </a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "## <font color=\"#fe7401\"> Rotate Array </font>\n",
    "***\n",
    "\n",
    "Input: nums = [1,2,3,4,5,6,7], k = 3 <br>\n",
    "Output: [5,6,7,1,2,3,4] <br>\n",
    "+ In-place solution:\n",
    "```    N = len(nums)\n",
    "    k = k % N   //to prevent out-of bound exception\n",
    "    reverse(nums, 0, N-k-1)     //Reverse first N-k half\n",
    "    reverse(nums, N-k, N-1)     //Reverse last k half\n",
    "    reverse(nums, 0, N-1)       //Reverse the full\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "## <font color=\"#fe7401\"> Move Zeroes </font>\n",
    "***\n",
    "\n",
    "Move Zeroes to the right, maintaing the relative order of elements<br>\n",
    "Input: nums = [0,1,0,3,12]<br>\n",
    "Output: [1,3,12,0,0]<br>\n",
    "+ In-place solution:\n",
    "        pos = 0\n",
    "        for i in range(len(nums)):      //move all non-zero elements to the left\n",
    "            if nums[i] != 0:\n",
    "                nums[pos] = nums[i]\n",
    "                pos += 1\n",
    "        for i in range(pos, len(nums)):     //fill the rest position with 0\n",
    "            nums[i] = 0 \n",
    "+ Eg.\n",
    "            [0,1,0,3,12]    //initial state\n",
    "            [0,1,0,3,12]    //itr 0, as nums[i] == 0: do nothing\n",
    "            [1,1,0,3,12]    //itr 1\n",
    "            [1,1,0,3,12]    //itr 2, as nums[i] == 0: do nothing\n",
    "            [1,3,0,3,12]    //itr 3\n",
    "            [1,3,12,3,12]   //itr 4\n",
    "            [1,3,12,0,0]    // now, fill rest with zero"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "## <font color=\"#fe7401\"> Two pointer applications </font>\n",
    "***\n",
    "\n",
    "+ Slow & fast pointer approach\n",
    "    * Also known as Floyd's slow & fast pointer approach.\n",
    "    * Algorithm:\n",
    "        * Each time, slow ptr go 1 steps while fast ptr go 2 steps.\n",
    "        * When fast ptr arrives at the end, slow ptr will arrive right in the middle (used to find mid-point in linked list)\n",
    "    * Can be used to :\n",
    "        1. To detect cycle in linked list, as both pointer pointers meet at some state.\n",
    "        2. To find the mid-point of linked list\n",
    "<br><br>\n",
    "+ Remove Nth node from the End of the list\n",
    "    * A one pass solution can be done using pointers. \n",
    "```\n",
    "        public ListNode removeNthFromEnd(ListNode head, int n) {\n",
    "            ListNode fast, slow;\n",
    "            fast = slow = head;\n",
    "\n",
    "            for(int i = 1; i <= n; i++)     //move fast pointer n+1 node forward\n",
    "                fast = fast.next;\n",
    "\n",
    "            if(fast == null)        //if n == size of list, remove first node\n",
    "                return head.next;\n",
    "\n",
    "            while(fast.next != null) {\n",
    "                slow = slow.next;\n",
    "                fast = fast.next;\n",
    "            }\n",
    "            slow.next = slow.next.next;\n",
    "            return head;\n",
    "        }\n",
    "```\n",
    "<img src=\"https://leetcode.com/explore/learn/card/fun-with-arrays/523/conclusion/Figures/Array_Explore/Array_Basics_Conclusion_1.png\" width=500>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "## <font color=\"#fe7401\"> Graph concepts </font>\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Depth First Search (DFS)\n",
    "\n",
    "* A connected acyclic graph is called a tree, means tree is a subset of graph.\n",
    "* Depth-first search is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking. So the basic idea is to start from the root or any arbitrary node and mark the node and move to the adjacent unmarked node and continue this loop until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them. Finally, print the nodes in the path.\n",
    "* Depth-first search is used in:\n",
    "     * <a href=\"#TopologicalSorting\">Topological sorting</a>\n",
    "     * scheduling problems \n",
    "     * cycle detection in graphs\n",
    "     * solving puzzles with only one solution, such as a maze or a sudoku puzzle.\n",
    "<img src=\"http://www.crazyforcode.com/wp-content/uploads/2016/04/DFS.png\" alt=\"dfs\" width=800 />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Topological sorting  <a name=\"TopologicalSorting\"> . </a>\n",
    "\n",
    "* Topological sort or topological ordering of a *directed graph* is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.\n",
    "* The Applications of Topological Sort are -\n",
    "    * Course Schedule problem.\n",
    "    * Finding cycle in a graph.\n",
    "    * Operation System deadlock detection.\n",
    "    * Dependency resolution.\n",
    "    * Sentence Ordering.\n",
    "    * Critical Path Analysis.\n",
    "    * Other applications like manufacturing workflows, data serialization and context-free grammar.\n",
    "* Algorithms used in Topological Sorting are -\n",
    "    1. <a href = \"https://www.youtube.com/watch?v=cIBFEhD77b4\" alt=\"Kahn_Algo\"> Kahn's algorithm </a>\n",
    "    2. <a href = \"https://www.youtube.com/watch?v=eL-KzMXSXXI\" alt=\"dfs_algo\"> DFS </a>"
   ]
  }
 ],
 "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
}