Colab_Codes/Advanced_Search_on_Linear_Data_Structures.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Advanced Search on Linear Data Structures.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "p1AUD30cnI0b",
        "colab_type": "text"
      },
      "source": [
        "# Slow-fast Pointers"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "uxNIaguAv2QT",
        "colab_type": "text"
      },
      "source": [
        "## Array"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Kz8-B6bTed1u",
        "colab_type": "text"
      },
      "source": [
        "### Remove duplicates"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "P6YqRE57ebXz",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "a = [0,0,1,1,1,2,2,3,3,4]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2a-xbM6GesgQ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def removeDuplicates(nums) -> int:\n",
        "    i, j = 0, 0\n",
        "    while j < len(nums):\n",
        "        print('[0, i]:', nums[0:i+1], '[i+1, j]:', nums[i+1:j+1])\n",
        "        if nums[i] != nums[j]:\n",
        "            # Copy j to i+1\n",
        "            i += 1\n",
        "            nums[i] = nums[j]\n",
        "            print('copy value {} at index {} to index {}'.format(nums[j],j, i))\n",
        "        j += 1\n",
        "    return i + 1"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9WPUvQCge_IW",
        "colab_type": "code",
        "outputId": "ea817fac-5cdc-4514-90ea-f709f273cb15",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 293
        }
      },
      "source": [
        "# Test\n",
        "removeDuplicates(a)\n",
        "a"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[0, i]: [0] [i+1, j]: []\n",
            "[0, i]: [0] [i+1, j]: [0]\n",
            "[0, i]: [0] [i+1, j]: [0, 1]\n",
            "copy value 1 at index 2 to index 1\n",
            "[0, i]: [0, 1] [i+1, j]: [1, 1]\n",
            "[0, i]: [0, 1] [i+1, j]: [1, 1, 1]\n",
            "[0, i]: [0, 1] [i+1, j]: [1, 1, 1, 2]\n",
            "copy value 2 at index 5 to index 2\n",
            "[0, i]: [0, 1, 2] [i+1, j]: [1, 1, 2, 2]\n",
            "[0, i]: [0, 1, 2] [i+1, j]: [1, 1, 2, 2, 3]\n",
            "copy value 3 at index 7 to index 3\n",
            "[0, i]: [0, 1, 2, 3] [i+1, j]: [1, 2, 2, 3, 3]\n",
            "[0, i]: [0, 1, 2, 3] [i+1, j]: [1, 2, 2, 3, 3, 4]\n",
            "copy value 4 at index 9 to index 4\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[0, 1, 2, 3, 4, 2, 2, 3, 3, 4]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 32
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WpoPXLowYthf",
        "colab_type": "text"
      },
      "source": [
        "### Minimum Size Subarray Sum"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y_Kq77AwYuCx",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def minSubArrayLen(s: int, nums) -> int:\n",
        "    i, j = 0, 0\n",
        "    acc = 0\n",
        "    ans = float('inf')\n",
        "    while j < len(nums):\n",
        "        acc += nums[j]\n",
        "        # Shrink the window\n",
        "        while acc >= s:\n",
        "            ans = min(ans, j - i + 1)\n",
        "            acc -= nums[i]\n",
        "            i += 1\n",
        "        j += 1\n",
        "        \n",
        "    return ans if ans < float('inf') else 0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9gwIePmuY9ZR",
        "colab_type": "code",
        "outputId": "76fdcc30-1225-4724-d4b4-cb0c3ed4d1e7",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "s = 7\n",
        "nums = [1,4,1,2,4,3]\n",
        "minSubArrayLen(s, nums)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 34
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "7Tvt4n4qHZxP",
        "colab_type": "text"
      },
      "source": [
        "### [Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "JfSUte9NHbF5",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "S = \"ADOBECODEBANC\"\n",
        "T = \"ABC\""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "v2aQ3SfaHrdo",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from collections import Counter\n",
        "def minWindow(s, t):\n",
        "  dict_t = Counter(t)\n",
        "  count = len(dict_t)\n",
        "  i, j = 0, 0\n",
        "  ans = []\n",
        "  minLen = float('inf')\n",
        "  while j < len(s):\n",
        "    c = s[j]\n",
        "    if c in dict_t:\n",
        "      dict_t[c] -= 1\n",
        "      if dict_t[c] == 0:\n",
        "        count -= 1\n",
        "    # Shrink the window\n",
        "    while count == 0 and i < j:\n",
        "      curLen = j - i + 1\n",
        "      if curLen < minLen:\n",
        "        minLen = j - i + 1\n",
        "        ans = [s[i:j+1]]\n",
        "      elif curLen == minLen: \n",
        "        ans.append(s[i:j+1])\n",
        "\n",
        "      c = s[i]\n",
        "      if c in dict_t:\n",
        "        dict_t[c] += 1\n",
        "        if dict_t[c] == 1:\n",
        "          count += 1\n",
        "      i += 1\n",
        "\n",
        "    j += 1\n",
        "  return ans"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SrF6tS5PVT6J",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "1b43cf78-a9fe-4a9a-f410-9f44e45d532a"
      },
      "source": [
        "S = 'AOBECDBANC'\n",
        "minWindow(S, T)"
      ],
      "execution_count": 6,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "['CDBA', 'BANC']"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "PGsA-6rbv0F_",
        "colab_type": "text"
      },
      "source": [
        "## Linked List"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "x1TiIhmgv1WR",
        "colab_type": "text"
      },
      "source": [
        "### Middle of the Linked List"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QBa-8mmewBC6",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def middleNode(head):\n",
        "    slow = fast = head\n",
        "    while fast and fast.next:        \n",
        "        fast = fast.next.next\n",
        "        slow = slow.next     \n",
        "    return slow"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vAGAFdIIwHLf",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from collections import defaultdict\n",
        "class Node:\n",
        "  def __init__(self, val, next = None):\n",
        "    self.val = val\n",
        "    self.next = next\n",
        "\n",
        "def getLinkedList(val_lst):\n",
        "  head = cur = None\n",
        "  # Use a dictionary to track nodes\n",
        "  Nodes = defaultdict(Node)\n",
        "  if val_lst:\n",
        "    head = cur = Node(val_lst[0]) \n",
        "    Nodes[val_lst[0]] = head \n",
        "    if len(val_lst) >= 2:\n",
        "      for i in range(1, len(val_lst)):\n",
        "        if val_lst[i] not in Nodes:\n",
        "          cur.next = Node(val_lst[i])\n",
        "          Nodes[val_lst[i]] = cur.next\n",
        "        else:\n",
        "          cur.next = Nodes[val_lst[i]]\n",
        "        cur = cur.next\n",
        "  return head\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "22Ajd39uwWDE",
        "colab_type": "code",
        "outputId": "bf59fd8d-b303-411c-f257-d546652fc2e2",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "head1 = getLinkedList([1, 2, 3, 4, 5])\n",
        "head2 = getLinkedList([1, 2, 3, 4, 5, 6])\n",
        "print(middleNode(head1).val, middleNode(head2).val)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "3 4\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "2W37Ktyny09T",
        "colab_type": "text"
      },
      "source": [
        "###  Floyd's Cycle Detection"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "RVMKzZD_y4HK",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "head_cycle = getLinkedList([1, 2, 3, 4, 5, 6, 3])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "UEeG5uoxy-ET",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Looping over a cyclic linked list makes the program stuck \n",
        "def iterate(head):\n",
        "  cur = head_cycle\n",
        "  while cur:\n",
        "    print(cur.val)\n",
        "    cur = cur.next"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "N9GnJe54APNW",
        "colab_type": "text"
      },
      "source": [
        "### [Check the existence of cycles](https://leetcode.com/problems/linked-list-cycle/)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EqAIbFI6_5zf",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def hasCycle(head):\n",
        "    slow = fast = head\n",
        "    while fast and fast.next:\n",
        "        slow = slow.next\n",
        "        fast = fast.next.next\n",
        "        if slow == fast:\n",
        "            return True\n",
        "    return False"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AGGujN9M_-ZU",
        "colab_type": "code",
        "outputId": "8231f73c-1d58-4c76-d587-5ee1928e67a3",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "hasCycle(head_cycle), hasCycle(head1)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(True, False)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 41
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BJxOVKPVAUTK",
        "colab_type": "text"
      },
      "source": [
        "### [Check where the cycle starts](https://leetcode.com/problems/linked-list-cycle-ii/)"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lMkK9SxGFtlU",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def detectCycle(head):\n",
        "    slow = fast = head\n",
        "\n",
        "    def getStartNode(slow, fast, head):\n",
        "      # Reset slow pointer      \n",
        "      slow = head\n",
        "      while fast and slow != fast:\n",
        "          slow = slow.next\n",
        "          fast = fast.next\n",
        "      return slow\n",
        "\n",
        "    while fast and fast.next:\n",
        "        slow = slow.next\n",
        "        fast = fast.next.next\n",
        "        # A cycle is detected\n",
        "        if slow == fast: \n",
        "            return getStartNode(slow, fast, head)\n",
        "    \n",
        "    return None\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZlC_JS3zGoAs",
        "colab_type": "code",
        "outputId": "a4f45ccf-bf95-4408-83f5-a7e98ee75c4e",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "detectCycle(head_cycle).val, detectCycle(head1)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(3, None)"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 43
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2Yu3lZROJRd0",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def resetLastNode(slow, fast, head):\n",
        "    slow = head\n",
        "    while fast and slow.next != fast.next:\n",
        "        slow = slow.next\n",
        "        fast = fast.next\n",
        "    fast.next = None"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "klgtZzC8J1p5",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def removeCycle(head):\n",
        "    slow = fast = head\n",
        "\n",
        "    while fast and fast.next:\n",
        "        slow = slow.next\n",
        "        fast = fast.next.next\n",
        "        # A cycle is detected\n",
        "        if slow == fast: \n",
        "            resetLastNode(slow, fast, head)\n",
        "            return  \n",
        "    return "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Hkfwf1ZHJ_ee",
        "colab_type": "code",
        "outputId": "c92543cb-be01-46ed-c8b5-c3cbb9f789d8",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 127
        }
      },
      "source": [
        "removeCycle(head_cycle)\n",
        "iterate(head_cycle)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1\n",
            "2\n",
            "3\n",
            "4\n",
            "5\n",
            "6\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "XRirMOVAnF_P",
        "colab_type": "text"
      },
      "source": [
        "# Opposite-directional Pointers"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sHZyeFkjoSLT",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Reverse a list or string in place\n",
        "def reverse(a):\n",
        "  i, j = 0, len(a) - 1\n",
        "  while i < j:\n",
        "    # Swap items\n",
        "    a[i], a[j] = a[j], a[i]\n",
        "    i += 1\n",
        "    j -= 1"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8Mcrgto4oFhP",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "4732a45f-bd29-4ccb-d6cc-2bd8be5ba731"
      },
      "source": [
        "# Reverse a list\n",
        "a = [1, 2, 3, 4, 5]\n",
        "b = 'abcd'\n",
        "b = list(b)\n",
        "reverse(a), reverse(b)\n",
        "a, b"
      ],
      "execution_count": 5,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "([5, 4, 3, 2, 1], ['d', 'c', 'b', 'a'])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "peRFBx9ToIMH",
        "colab_type": "text"
      },
      "source": [
        "## Two Sum"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "a-VwPo3nnaGU",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def twoSum(a, target):\n",
        "    n = len(a)\n",
        "    i, j  = 0, n-1\n",
        "    while i < j:\n",
        "        temp = a[i] + a[j]\n",
        "        if temp == target:\n",
        "            return [i, j]\n",
        "        elif temp < target:\n",
        "            i += 1\n",
        "        else:\n",
        "            j -= 1\n",
        "    return []"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qE4rNc_yn0ru",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        },
        "outputId": "0e3f7c1d-2f47-487c-f1bf-644255f4214e"
      },
      "source": [
        "a = [2, 5, 7, 11, 15]\n",
        "target = 9\n",
        "twoSum(a, target)"
      ],
      "execution_count": 2,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[0, 2]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 2
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "X0Epx9cJWTPC",
        "colab_type": "text"
      },
      "source": [
        "# Three Pointers"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "M2XkxgxUWWMd",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "a = [1, 0, 1, 0, 1]\n",
        "S = 2"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-wD9AJE9Wa81",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Try two pointers\n",
        "def numSubarraysWithSum(a, S):\n",
        "  i, j = 0, 0\n",
        "  win_sum = 0\n",
        "  ans = 0\n",
        "  while j < len(a):\n",
        "    win_sum += a[j]\n",
        "    while i <j and win_sum > S:\n",
        "      win_sum -= a[i]\n",
        "      i += 1\n",
        "    if win_sum == S:\n",
        "      ans += 1\n",
        "      print('({}, {})'.format(i, j))\n",
        "    j += 1\n",
        "  return ans"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NLKtEwQUXaQD",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 90
        },
        "outputId": "783f296b-4ad1-422e-c927-5e475e573874"
      },
      "source": [
        "numSubarraysWithSum(a, S)"
      ],
      "execution_count": 7,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "(0, 2)\n",
            "(0, 3)\n",
            "(1, 4)\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "3"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DdmOnfQNYP1O",
        "colab_type": "text"
      },
      "source": [
        "We can clearly see that it missed the case $(2, 4)$.  Why? Because we are restricting the subarray sum in range $[i, j]$ to be smaller than or equal to $S$, with the occruence of $0$s that might appear in the front or in the rear of the subarray:\n",
        "* In the process of expanding the subarray, pointer $j$ is moved one at a time. Thus, even though $0$s appear in the rear of the subarray, the counting is correct.\n",
        "* However, in the process of shrinking the subarray while the restriction is violated($sum > S$), we stop right away once $sum \\leq S$. And in the code, we end up only counting it as one occurrence. With $0$s at the beginning of the subarray, such as the subarray $[0, 1, 0, 1]$ with index $1$ and $4$, there count should be two instead of one. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XTTf6yb8hy5f",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def numSubarraysWithSum(a, S):\n",
        "  i, i_h, j = 0, 0, 0\n",
        "  win_sum = 0\n",
        "  ans = 0\n",
        "  while j < len(a):\n",
        "    win_sum += a[j]\n",
        "    while i < j and win_sum > S:\n",
        "      win_sum -= a[i]\n",
        "      i += 1\n",
        "    # Move i_h to count all zeros in the front\n",
        "    i_h = i\n",
        "    while i_h < j and win_sum == S and a[i_h] == 0:\n",
        "      print('({}, {})'.format(i_h, j))\n",
        "      ans += 1\n",
        "      i_h += 1\n",
        "\n",
        "    if win_sum == S:\n",
        "      ans += 1\n",
        "      print('({}, {})'.format(i_h, j))\n",
        "    j += 1\n",
        "  return ans"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "yPmDad-RjCpw",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 109
        },
        "outputId": "9fbe3bf8-8cc9-4dd8-8edc-2b254edce79d"
      },
      "source": [
        "numSubarraysWithSum(a, S)"
      ],
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "(0, 2)\n",
            "(0, 3)\n",
            "(1, 4)\n",
            "(2, 4)\n"
          ],
          "name": "stdout"
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "4"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 9
        }
      ]
    }
  ]
}