Ch02_Two_Pointers_and_Sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "view-in-github"
   },
   "source": [
    "<a href=\"https://colab.research.google.com/github/lizhicq/Algorithms-Manual/blob/master/Ch02_Two_Pointers_and_Sorting.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "qRgfOvCdz1aE"
   },
   "source": [
    "# Two Pointers & LinkedList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "0YhRJecLmE7Q"
   },
   "source": [
    "## 同向双指针（数组去重，滑动窗口，两数之差，链表中点，带环链表）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "1uDO-KLARZOj"
   },
   "source": [
    "### 1. Two Sum\n",
    "Given an array of integers, return indices of the two numbers such that they add up to a specific target.\n",
    "\n",
    "You may assume that each input would have exactly one solution, and you may not use the same element twice.\n",
    "\n",
    "Example:\n",
    "\n",
    "Given nums = [2, 7, 11, 15], target = 9,\n",
    "\n",
    "Because nums[0] + nums[1] = 2 + 7 = 9,\n",
    "return [0, 1]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "z4FYSSFKRlOo"
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def twoSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        nmap = {}\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            num = nums[i]\n",
    "            import ipdb; ipdb.set_trace()\n",
    "            if target - num in nmap:\n",
    "                return sorted([i, nmap[target - num]])\n",
    "            else:\n",
    "                nmap[num] = i\n",
    "        \n",
    "        return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> \u001b[1;32m<ipython-input-6-9ec2d2f29333>\u001b[0m(13)\u001b[0;36mtwoSum\u001b[1;34m()\u001b[0m\n",
      "\u001b[1;32m     12 \u001b[1;33m            \u001b[1;32mimport\u001b[0m \u001b[0mipdb\u001b[0m\u001b[1;33m;\u001b[0m \u001b[0mipdb\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mset_trace\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[1;32m---> 13 \u001b[1;33m            \u001b[1;32mif\u001b[0m \u001b[0mtarget\u001b[0m \u001b[1;33m-\u001b[0m \u001b[0mnum\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mnmap\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[1;32m     14 \u001b[1;33m                \u001b[1;32mreturn\u001b[0m \u001b[0msorted\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mnmap\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mtarget\u001b[0m \u001b[1;33m-\u001b[0m \u001b[0mnum\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\n"
     ]
    },
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "ipdb>  target\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9\n"
     ]
    },
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "ipdb>  n\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> \u001b[1;32m<ipython-input-6-9ec2d2f29333>\u001b[0m(16)\u001b[0;36mtwoSum\u001b[1;34m()\u001b[0m\n",
      "\u001b[1;32m     15 \u001b[1;33m            \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[1;32m---> 16 \u001b[1;33m                \u001b[0mnmap\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mnum\u001b[0m\u001b[1;33m]\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[1;32m     17 \u001b[1;33m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\n"
     ]
    },
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "ipdb>  n\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> \u001b[1;32m<ipython-input-6-9ec2d2f29333>\u001b[0m(10)\u001b[0;36mtwoSum\u001b[1;34m()\u001b[0m\n",
      "\u001b[1;32m      9 \u001b[1;33m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[1;32m---> 10 \u001b[1;33m        \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnums\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[1;32m     11 \u001b[1;33m            \u001b[0mnum\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mnums\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\n"
     ]
    },
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "ipdb>  n\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> \u001b[1;32m<ipython-input-6-9ec2d2f29333>\u001b[0m(11)\u001b[0;36mtwoSum\u001b[1;34m()\u001b[0m\n",
      "\u001b[1;32m     10 \u001b[1;33m        \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mnums\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[1;32m---> 11 \u001b[1;33m            \u001b[0mnum\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mnums\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[1;32m     12 \u001b[1;33m            \u001b[1;32mimport\u001b[0m \u001b[0mipdb\u001b[0m\u001b[1;33m;\u001b[0m \u001b[0mipdb\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mset_trace\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\n"
     ]
    },
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "ipdb>  n\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> \u001b[1;32m<ipython-input-6-9ec2d2f29333>\u001b[0m(12)\u001b[0;36mtwoSum\u001b[1;34m()\u001b[0m\n",
      "\u001b[1;32m     11 \u001b[1;33m            \u001b[0mnum\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mnums\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[1;32m---> 12 \u001b[1;33m            \u001b[1;32mimport\u001b[0m \u001b[0mipdb\u001b[0m\u001b[1;33m;\u001b[0m \u001b[0mipdb\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mset_trace\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[1;32m     13 \u001b[1;33m            \u001b[1;32mif\u001b[0m \u001b[0mtarget\u001b[0m \u001b[1;33m-\u001b[0m \u001b[0mnum\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mnmap\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\n"
     ]
    },
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "ipdb>  n\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "> \u001b[1;32m<ipython-input-6-9ec2d2f29333>\u001b[0m(13)\u001b[0;36mtwoSum\u001b[1;34m()\u001b[0m\n",
      "\u001b[1;32m     12 \u001b[1;33m            \u001b[1;32mimport\u001b[0m \u001b[0mipdb\u001b[0m\u001b[1;33m;\u001b[0m \u001b[0mipdb\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mset_trace\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[1;32m---> 13 \u001b[1;33m            \u001b[1;32mif\u001b[0m \u001b[0mtarget\u001b[0m \u001b[1;33m-\u001b[0m \u001b[0mnum\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mnmap\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\u001b[1;32m     14 \u001b[1;33m                \u001b[1;32mreturn\u001b[0m \u001b[0msorted\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mnmap\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mtarget\u001b[0m \u001b[1;33m-\u001b[0m \u001b[0mnum\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[0m\n"
     ]
    }
   ],
   "source": [
    "Solution().twoSum([2,7,11,15], target=9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "c2s3o-XWSI24"
   },
   "source": [
    "You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.\n",
    "\n",
    "You may assume the two numbers do not contain any leading zero, except the number 0 itself.\n",
    "```\n",
    "Example:\n",
    "\n",
    "Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)\n",
    "Output: 7 -> 0 -> 8\n",
    "Explanation: 342 + 465 = 807.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "_vjPBho4SLhR"
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def addTwoNumbers(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        l3 = head = ListNode(-1)\n",
    "        res = 0\n",
    "        while l1 and l2:\n",
    "            val = l1.val + l2.val + res\n",
    "            res = 0\n",
    "            if val >= 10:\n",
    "                res = 1\n",
    "                val -= 10\n",
    "            l3.next = ListNode(val)\n",
    "            l1 = l1.next\n",
    "            l2 = l2.next\n",
    "            l3 = l3.next\n",
    "\n",
    "        while l1:\n",
    "            val = l1.val + res\n",
    "            res = 0\n",
    "            if val >= 10:\n",
    "                res = 1\n",
    "                val -= 10\n",
    "            l3.next = ListNode(val)\n",
    "            l1 = l1.next\n",
    "            l3 = l3.next\n",
    "        \n",
    "        while l2:\n",
    "            val = l2.val + res\n",
    "            res = 0\n",
    "            if val >= 10:\n",
    "                res = 1\n",
    "                val -= 10\n",
    "            l3.next = ListNode(val)\n",
    "            l2 = l2.next\n",
    "            l3 = l3.next\n",
    "\n",
    "        \n",
    "        if res:\n",
    "            l3.next = ListNode(res)\n",
    "            res = 0 \n",
    "            l3 = l3.next\n",
    "        \n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "GAJTOZc_HSNN"
   },
   "source": [
    "### 228. Middle of Linked List\n",
    "Description\n",
    "Find the middle node of a linked list.\n",
    "\n",
    "Have you met this question in a real interview?  \n",
    "```\n",
    "Example\n",
    "Given 1->2->3, return the node with value 2.\n",
    "\n",
    "Given 1->2, return the node with value 1.\n",
    "\n",
    "Challenge\n",
    "If the linked list is in a data stream, can you find the middle without iterating the linked list again?\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "729mg0sEI8_N"
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    # @ head: the head of linked list.\n",
    "    # @ return: a middle node of the linked list\n",
    "    def middleNode(self, head):\n",
    "        if head is None:\n",
    "            return None\n",
    "        slow = head\n",
    "        fast = slow.next\n",
    "        while fast is not None and fast.next is not None:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "\n",
    "        return slow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "7kFwcxhmHSqE"
   },
   "source": [
    "### 539. Move Zeroes\n",
    "\n",
    "Description\n",
    "Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.\n",
    "\n",
    "You must do this in-place without making a copy of the array.\n",
    "Minimize the total number of operations.\n",
    "Have you met this question in a real interview?  \n",
    "```\n",
    "Example\n",
    "Given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "W8I_EajoKIB7",
    "outputId": "49088211-f07b-4c03-d4ba-4e7c9e30fed3"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 3, 12, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    # @{int[]} nums an integer array\n",
    "    # @return nothing, do this in-place\n",
    "    def moveZeroes(self, nums):\n",
    "        left = right = 0\n",
    "        while right < len(nums):\n",
    "            if nums[right] != 0:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return nums\n",
    "      \n",
    "if __name__ == \"__main__\":\n",
    "    print Solution().moveZeroes([0, 1, 0, 3, 12])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "5-JSiUxbHSJL"
   },
   "source": [
    "### 521. Remove Duplicate Numbers in Array\n",
    "\n",
    "Description\n",
    "Given an array of integers, remove the duplicate numbers in it.\n",
    "\n",
    "You should:\n",
    "\n",
    "Do it in place in the array.\n",
    "Move the unique numbers to the front of the array.\n",
    "Return the total number of the unique numbers.\n",
    "You don't need to keep the original order of the integers.\n",
    "\n",
    "Have you met this question in a real interview?  \n",
    "\n",
    "```\n",
    "Example\n",
    "Given nums = [1,3,1,4,4,2], you should:\n",
    "\n",
    "Move duplicate integers to the tail of nums => nums = [1,3,4,2,?,?].\n",
    "Return the number of unique integers in nums => 4.\n",
    "Actually we don't care about what you place in ?, we only care about the part which has no duplicate integers.\n",
    "\n",
    "Challenge\n",
    "Do it in O(n) time complexity.\n",
    "Do it in O(nlogn) time without extra space.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "IMzlFyQ6K_qs",
    "outputId": "1da968e5-7e79-471a-c828-c0a4a40049fb"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    # @{int[]} nums an array of integers\n",
    "    # @return {int} the number of unique integers\n",
    "    def deduplication(self, nums):\n",
    "        return len(set(nums)) \n",
    "    \n",
    "    def deduplication2(self, nums):\n",
    "        nums.sort()\n",
    "        pvt = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] != nums[pvt]:\n",
    "                pvt += 1\n",
    "                nums[pvt] = nums[i]\n",
    "        return pvt + 1\n",
    "      \n",
    "if __name__ == \"__main__\":\n",
    "    print(Solution().deduplication2([1,2,3,4,5,1,3,2]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "QusJcqafmUdP"
   },
   "source": [
    "### 610. Two Sum - Difference equals to target\n",
    "\n",
    "610. Two Sum - Difference equals to target\n",
    "Given an array of integers, find two numbers that their difference equals to a target value.\n",
    "where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.\n",
    "\n",
    "Example\n",
    "Given nums = [2, 7, 15, 24], target = 5\n",
    "return [1, 2] (7 - 2 = 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "oRR4dtmPqmDu",
    "outputId": "09dd49e9-608b-45f3-8573-21e60f5dc0a1"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 2)\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param nums {int[]} n array of Integer\n",
    "    @param target {int} an integer\n",
    "    @return {int[]} [index1 + 1, index2 + 1] (index1 < index2)\n",
    "    \"\"\"\n",
    "\n",
    "    def twoSum7(self, nums, target):\n",
    "        # Write your code here\n",
    "        dct = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] - target in dct:\n",
    "                return (dct[nums[i] - target] + 1, i + 1)\n",
    "            if nums[i] + target in dct:\n",
    "                return (dct[nums[i] + target] + 1, i + 1)\n",
    "            dct[nums[i]] = i ## 5+5 = 10?\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    print Solution().twoSum7([2, 7, 15, 24], 5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "DLTBKQBet-fH"
   },
   "source": [
    "### 380. Intersection of Two Linked Lists\n",
    "Write a program to find the node at which the intersection of two singly linked lists begins.\n",
    "```\n",
    "Example\n",
    "The following two linked lists:\n",
    "\n",
    "A:          a1 → a2\n",
    "                   ↘\n",
    "                     c1 → c2 → c3\n",
    "                   ↗            \n",
    "B:     b1 → b2 → b3\n",
    "begin to intersect at node c1.\n",
    "```\n",
    "Challenge\n",
    "Your code should preferably run in O(n) time and use only O(1) memory.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "x1btOrLXt-i7",
    "outputId": "f791e671-0916-429a-8bad-9832e3533755"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "     def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # param headA: the first list\n",
    "    # param headB: the second list\n",
    "    # @return: a ListNode\n",
    "    def getIntersectionNode(self, headA, headB):\n",
    "        # Write your code here\n",
    "        lenA, lenB = 0, 0\n",
    "        node1, node2 = headA, headB\n",
    "        while node1 is not None:\n",
    "            lenA += 1\n",
    "            node1 = node1.next\n",
    "        while node2 is not None:\n",
    "            lenB += 1\n",
    "            node2 = node2.next\n",
    "\n",
    "        node1, node2 = headA, headB\n",
    "        while lenA > lenB:\n",
    "            node1 = node1.next\n",
    "            lenA -= 1\n",
    "        while lenB > lenA:\n",
    "            node2 = node2.next\n",
    "            lenB -= 1\n",
    "        while node1 is not node2:\n",
    "            node1 = node1.next\n",
    "            node2 = node2.next\n",
    "        return node1\n",
    "\n",
    "\n",
    "print Solution().getIntersectionNode(None, None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "ZgIlhz3_xbvE"
   },
   "source": [
    "### 102. Linked List Cycle\n",
    "Given a linked list, determine if it has a cycle in it.\n",
    "\n",
    "\n",
    "```\n",
    "Example\n",
    "Given -21->10->4->5, tail connects to node index 1, return true\n",
    "\n",
    "Challenge\n",
    "Follow up:\n",
    "Can you solve it without using extra space?\n",
    "```\n",
    "这题要问的是，会不会永远不相遇，绝对不会，因为fast同奇偶，slow变奇偶，所以一定有相遇的时候。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "2Iq8qvfZxbzG",
    "outputId": "2e211f12-4d2b-4dab-d527-c16071a745c8"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "class ListNode:\n",
    "     def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param head: The first node of the linked list.\n",
    "    @return: True if it has a cycle, or false\n",
    "    \"\"\"\n",
    "    def hasCycle(self, head):\n",
    "        # write your code here\n",
    "        if head is None:\n",
    "            return False\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while fast.next is not None:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast is None:\n",
    "                return False\n",
    "            elif fast == slow:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "print Solution().hasCycle(None)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "2LyK4vzQLnDH"
   },
   "source": [
    "### 103. Linked List Cycle II\n",
    "Given a linked list, return the node where the cycle begins.\n",
    "\n",
    "If there is no cycle, return null.\n",
    "```\n",
    "Example\n",
    "Given -21->10->4->5, tail connects to node index 1，return 10\n",
    "\n",
    "Challenge\n",
    "Follow up:\n",
    "\n",
    "Can you solve it without using extra space?\n",
    "\n",
    "    a            b\n",
    "A ------ B --------+\n",
    "         |         |\n",
    "       c |         |\n",
    "         +-------- C\n",
    "\n",
    "\n",
    "\n",
    "* A: 起始点\n",
    "* B: Cycle Begins\n",
    "* C: 1st 快慢指针相遇点\n",
    "\n",
    "\n",
    "* A->B: a\n",
    "* B->C: b\n",
    "* C->B: c\n",
    "* 环的长度 (b+c) 为 R\n",
    "\n",
    "第一次相遇时，慢指针所走步数为\n",
    "a + b + mR\n",
    "快指针走的步数为\n",
    "a + b + nR\n",
    "我们知道快指针是慢指针速度的2倍，因此\n",
    "2(a + b + mR) = a + b + nR\n",
    "那么\n",
    "a + b = (n-2m)R\n",
    "同时\n",
    "b + c = R\n",
    "所以\n",
    "a = (n - 2m - 1)R + c;\n",
    "也就是说，从A点和C点同时出发，以相同的速度前进，那么下一次相遇的位置将是B。\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "3KACQWwtLnK3",
    "outputId": "20ed8e02-c5a6-4b5d-bac0-4fcd2d7de7bc"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "21\n"
     ]
    }
   ],
   "source": [
    "class ListNode(object):\n",
    "    def __init__(self, val, next=None):\n",
    "        self.val = val\n",
    "        self.next =Vnext\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param: head: The first node of linked list.\n",
    "    @return: The node where the cycle begins. if there is no cycle, return null\n",
    "    \"\"\"\n",
    "    def detectCycle(self, head):\n",
    "        if head is None:\n",
    "            return False\n",
    "        fast = head\n",
    "        slow = head\n",
    "        while fast.next is not None:\n",
    "            fast = fast.next.next\n",
    "            slow = slow.next\n",
    "            if fast is None:\n",
    "                return False\n",
    "            elif fast == slow:\n",
    "                fast = head\n",
    "                while fast != slow:\n",
    "                    fast = fast.next\n",
    "                    slow = slow.next\n",
    "                return fast\n",
    "        return False\n",
    "      \n",
    "if __name__ == \"__main__\":\n",
    "    #21->10->4->5\n",
    "\n",
    "    root = ListNode(21)\n",
    "    root.next = ListNode(10)\n",
    "    root.next.next = ListNode(4)\n",
    "    root.next.next.next = ListNode(5)\n",
    "    root.next.next.next.next = root\n",
    "    print Solution().detectCycle(root).val"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "aYgSHjiOVkXO"
   },
   "source": [
    "###406. Minimum Size Subarray Sum\n",
    "Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return -1 instead.\n",
    "```\n",
    "Example\n",
    "Given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.\n",
    "\n",
    "Challenge\n",
    "If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "0UHZK_MTVxJd",
    "outputId": "ccf2add2-9707-4c7d-c31d-c6508e798bcc"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param nums: an array of integers\n",
    "    @param s: An integer\n",
    "    @return: an integer representing the minimum size of subarray\n",
    "    \"\"\"\n",
    "    def minimumSize1(self, nums, s): # 34.40%\n",
    "        n = len(nums)\n",
    "        if n == 0 or sum(nums) < s:\n",
    "            return -1\n",
    "        start, end = 1, n\n",
    "        cum = [0]\n",
    "        for i in range(1, n+1):\n",
    "            cum.append(nums[i-1] + cum[i-1])\n",
    "        def check(k):  # k is large enough\n",
    "            for i in range(len(nums) - k + 1):\n",
    "                if cum[i+k] - cum[i] >= s:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        while start + 1 < end:\n",
    "            mid = start + (end - start) // 2\n",
    "            if check(mid):\n",
    "                end = mid\n",
    "            else:\n",
    "                start = mid\n",
    "\n",
    "        if check(start):\n",
    "            return start\n",
    "        if check(end):\n",
    "            return end\n",
    "        return -1\n",
    "\n",
    "    def minimumSize(self, nums, s): # 34.40%\n",
    "        from sys import maxsize\n",
    "        i = j = 0\n",
    "        cum = 0\n",
    "        ans = maxsize\n",
    "        for i in range(len(nums)):\n",
    "            while j < len(nums) and cum < s:\n",
    "                cum += nums[j]\n",
    "                j += 1\n",
    "            if cum >= s:\n",
    "                ans = min(ans, j-i)\n",
    "            cum -= nums[i]\n",
    "\n",
    "        return ans if ans != maxsize else -1\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums = [100,50,99,50,100,50,99,50,100,50]\n",
    "    s = 250\n",
    "    print Solution().minimumSize(nums, s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "wyQFcNc0mj7T"
   },
   "source": [
    "### 362. Sliding Window Maximum\n",
    "Given an array of n integer with duplicate number, and a moving window(size k), move the window at each iteration from the start of the array, find the maximum number inside the window at each moving.\n",
    "```\n",
    "Example\n",
    "For array [1, 2, 7, 7, 8], moving window size k = 3. return [7, 7, 8]\n",
    "\n",
    "At first the window is at the start of the array like this\n",
    "\n",
    "[|1, 2, 7| ,7, 8] , return the maximum 7;\n",
    "\n",
    "then the window move one step forward.\n",
    "\n",
    "[1, |2, 7 ,7|, 8], return the maximum 7;\n",
    "\n",
    "then the window move one step forward again.\n",
    "\n",
    "[1, 2, |7, 7, 8|], return the maximum 8;\n",
    "\n",
    "Challenge\n",
    "o(n) time and O(k) memory.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "X9187ikvmntS"
   },
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param nums: A list of integers.\n",
    "    @return: The maximum number inside the window at each moving.\n",
    "    \"\"\"\n",
    "    def maxSlidingWindow(self, nums, k):\n",
    "        # write your code here\n",
    "        q = deque()\n",
    "        result = []\n",
    "        if len(nums) < k or k == 0:\n",
    "            return []\n",
    "\n",
    "        n = len(nums)\n",
    "        for i in xrange(n):\n",
    "            while len(q) and nums[q[-1]] < nums[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "\n",
    "            if i < k - 1:                        \n",
    "                continue\n",
    "\n",
    "            while len(q) and q[0] <= i - k:\n",
    "                q.popleft()\n",
    "            \n",
    "            result.append(nums[q[0]])\n",
    "\n",
    "        return result;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "lpW2GTuaVqLM"
   },
   "source": [
    "### 384. Longest Substring Without Repeating Characters\n",
    "Given a string, find the length of the longest substring without repeating characters.\n",
    "```\n",
    "Example\n",
    "For example, the longest substring without repeating letters for \"abcabcbb\" is \"abc\", which the length is 3.\n",
    "\n",
    "For \"bbbbb\" the longest substring is \"b\", with the length of 1.\n",
    "\n",
    "Challenge\n",
    "O(n) time\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "2BpXqFI3Y-o3",
    "outputId": "15f27fe7-32b3-41ac-a646-a990b4f781c1"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param s: a string\n",
    "    @return: an integer\n",
    "    \"\"\"\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        i = j = 0\n",
    "        ch_set = set()\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            while j < len(s) and s[j] not in ch_set:\n",
    "                ch_set.add(s[j])\n",
    "                j += 1\n",
    "            ans = max(ans, j-i)\n",
    "            ch_set.remove(s[i])\n",
    "        return ans\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = \"abcabcbb\"\n",
    "    print Solution().lengthOfLongestSubstring(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "4RIoigj8SnVl",
    "outputId": "7105978a-c35d-401c-f80f-975325b7d1ec"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def lengthOfLongestSubstring(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        maxlen = 0 \n",
    "        ch_dict = {}\n",
    "        i = 0 \n",
    "        \n",
    "        for j, ch in enumerate(s):    \n",
    "            if ch in ch_dict:\n",
    "                i = max(ch_dict[ch], i)\n",
    "            maxlen = max(maxlen, j - i)\n",
    "            ch_dict[ch] = j\n",
    "        \n",
    "        #print(ch_dict)\n",
    "        return maxlen\n",
    "if __name__ == \"__main__\":\n",
    "    s = \"abcabcbb\"\n",
    "    print Solution().lengthOfLongestSubstring(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "WNFiFll1ZBu-"
   },
   "source": [
    "###386. Longest Substring with At Most K Distinct Characters\n",
    "Given a string s, find the length of the longest substring T that contains at most k distinct characters.\n",
    "```\n",
    "Example\n",
    "For example, Given s = \"eceba\", k = 3,\n",
    "\n",
    "T is \"eceb\" which its length is 4.\n",
    "\n",
    "Challenge\n",
    "O(n), n is the size of the string s.\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "zQCUOonXZB51",
    "outputId": "03fb9efe-8c0f-4812-ce79-74a42e639c61"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param s: A string\n",
    "    @param k: An integer\n",
    "    @return: An integer\n",
    "    \"\"\"\n",
    "    def lengthOfLongestSubstringKDistinct(self, s, k):\n",
    "        j = 0\n",
    "        ch_dic = {}\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            while j < len(s):\n",
    "                if s[j] in ch_dic:\n",
    "                    ch_dic[s[j]] += 1\n",
    "                else:\n",
    "                    if len(ch_dic) == k:\n",
    "                        break\n",
    "                    ch_dic[s[j]] = 1\n",
    "                j += 1\n",
    "\n",
    "            ans = max(ans, j-i)\n",
    "            if s[i] in ch_dic:\n",
    "                if ch_dic[s[i]] > 1:\n",
    "                    ch_dic[s[i]] -= 1\n",
    "                else:\n",
    "                    ch_dic.pop(s[i])\n",
    "        return ans\n",
    "\n",
    "if __name__ ==\"__main__\":\n",
    "    s = \"eqgkcwGFvjjmxutystqdfhuMblWbylgjxsxgnoh\"\n",
    "    k = 16\n",
    "    print Solution().lengthOfLongestSubstringKDistinct(s, k)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "e0vnSqvMS5vu"
   },
   "source": [
    "### 5. Longest Palindromic Substring\n",
    "Medium\n",
    "Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.\n",
    "```\n",
    "Example 1:\n",
    "\n",
    "Input: \"babad\"\n",
    "Output: \"bab\"\n",
    "Note: \"aba\" is also a valid answer.\n",
    "Example 2:\n",
    "\n",
    "Input: \"cbbd\"\n",
    "Output: \"bb\"\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "KQvLZxyeTGP0"
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def longestPalindrome(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        maxlen = 0\n",
    "        ans = ''\n",
    "        \n",
    "        for i in range(n):            \n",
    "            # odd\n",
    "            start, end = i, i\n",
    "            while start >= 0 and end < n and s[start] == s[end]:\n",
    "                    start -= 1\n",
    "                    end += 1 \n",
    "            if end - start - 1 > maxlen:\n",
    "                \n",
    "                ans = s[start+1:end]\n",
    "                maxlen = end - start - 1 \n",
    "                \n",
    "            # even\n",
    "            start, end = i, i+1\n",
    "            while start >= 0 and end < n and s[start] == s[end]:\n",
    "                    start -= 1\n",
    "                    end += 1 \n",
    "            if end - start - 1 > maxlen:\n",
    "                ans = s[start+1:end]\n",
    "                maxlen = end - start - 1 \n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "cqGsKQKaTn_i"
   },
   "source": [
    "### 76. Minimum Window Substring\n",
    "Hard\n",
    "Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).\n",
    "```\n",
    "Example:\n",
    "\n",
    "Input: S = \"ADOBECODEBANC\", T = \"ABC\"\n",
    "Output: \"BANC\"\n",
    "Note:\n",
    "\n",
    "If there is no such window in S that covers all characters in T, return the empty string \"\".\n",
    "If there is such window, you are guaranteed that there will always be only one unique minimum window in S.\n",
    "Accepted\n",
    "210,710\n",
    "Submissions\n",
    "707,191\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "HV3Uxjs6TtP1"
   },
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minWindow(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        mapt = Counter(t)\n",
    "        count = len(t)\n",
    "        head = left = right = 0\n",
    "        dis = 2**32 \n",
    "        \n",
    "        while right < len(s):\n",
    "            if mapt[s[right]] > 0:\n",
    "                count -= 1\n",
    "            mapt[s[right]] -= 1\n",
    "            right += 1\n",
    "                \n",
    "            while count == 0:\n",
    "                if right - left < dis:\n",
    "                    dis = right - left\n",
    "                    head = left\n",
    "                \n",
    "                if mapt[s[left]] == 0:\n",
    "                    count += 1\n",
    "                \n",
    "                mapt[s[left]] += 1\n",
    "                left += 1\n",
    "\n",
    "        return \"\" if dis == 2 ** 32 else s[head:head+dis]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NwxnnextlXnI"
   },
   "source": [
    "## 相向双指针（两数之和,  判断回文串）\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "-24yfHjfHSFy"
   },
   "source": [
    "### 608. Two Sum II - Input array is sorted\n",
    "Description\n",
    "Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.\n",
    "\n",
    "The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.\n",
    "\n",
    "You may assume that each input would have exactly one solution.\n",
    "\n",
    "```\n",
    "Example\n",
    "Given nums = [2, 7, 11, 15], target = 9\n",
    "return [1, 2]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "eyuutwY1Fq__"
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param nums: an array of Integer\n",
    "    @param target: target = nums[index1] + nums[index2]\n",
    "    @return: [index1 + 1, index2 + 1] (index1 < index2)\n",
    "    \"\"\"\n",
    "    def twoSum(self, nums, target):\n",
    "        start, end = 0, len(nums) - 1\n",
    "        while start < end :\n",
    "            csum = nums[start] + nums[end]\n",
    "            if csum == target:\n",
    "                return [start+1, end+1]\n",
    "            elif csum < target:\n",
    "                start += 1\n",
    "            else:\n",
    "                end -=1\n",
    "        return []"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "b700s9htdFsY"
   },
   "source": [
    "### 607. Two Sum III - Data structure design\n",
    "\n",
    "Description\n",
    "Design and implement a TwoSum class. It should support the following operations: add and find.\n",
    "\n",
    "add - Add the number to an internal data structure.\n",
    "find - Find if there exists any pair of numbers which sum is equal to the value.\n",
    "```\n",
    "Have you met this question in a real interview?  \n",
    "Example\n",
    "add(1); add(3); add(5);\n",
    "find(4) // return true\n",
    "find(7) // return false\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Z231__usdOvU"
   },
   "outputs": [],
   "source": [
    "class TwoSum(object):\n",
    "\n",
    "    def __init__(self):\n",
    "        # initialize your data structure here\n",
    "        self.count = {}\n",
    "\n",
    "    # Add the number to an internal data structure.\n",
    "    # @number {int}\n",
    "    # @return nothing\n",
    "    def add(self, number):\n",
    "        # Write your code here\n",
    "        if number in self.count:\n",
    "            self.count[number] += 1\n",
    "        else:\n",
    "            self.count[number] = 1\n",
    "            \n",
    "    # Find if there exists any pair of numbers which sum is equal to the value.\n",
    "    # @value {int}\n",
    "    # @return true if can be found or false\n",
    "    def find(self, value):\n",
    "        # Write your code here\n",
    "        for num in self.count:\n",
    "            if (value - num in self.count and \n",
    "                value - num != num or self.count[num] > 1):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "JMKPNByxob3g"
   },
   "source": [
    "### 609. Two Sum - Less than or equal to target\n",
    "Given an array of integers, find how many pairs in the array such that their sum is less than or equal to a specific target number. Please return the number of pairs.\n",
    "```\n",
    "Example\n",
    "Given nums = [2, 7, 11, 15], target = 24.\n",
    "Return 5.\n",
    "2 + 7 < 24\n",
    "2 + 11 < 24\n",
    "2 + 15 < 24\n",
    "7 + 11 < 24\n",
    "7 + 15 < 25\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 50
    },
    "colab_type": "code",
    "id": "Z4Kmu1sSohwI",
    "outputId": "ef552b0c-e8db-465e-c579-e17bf0c90cd1"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.00830793380737\n",
      "0.0209789276123\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param nums: an array of integer\n",
    "    @param target: an integer\n",
    "    @return: an integer\n",
    "    \"\"\"\n",
    "    def twoSum5_method1(self, nums, target):\n",
    "        n = len(nums)\n",
    "        if n <= 0:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        count = 0\n",
    "        for i in range(n):\n",
    "            for j in range(n-1, i, -1):\n",
    "                if nums[i] + nums[j] > target:\n",
    "                    continue\n",
    "                count += j - i\n",
    "                break\n",
    "        return count\n",
    "\n",
    "    def twoSum5(self, nums, target):\n",
    "        # Write your code here\n",
    "    v     l, r = 0, len(nums) - 1\n",
    "        cnt = 0\n",
    "        nums.sort()\n",
    "        while l < r:\n",
    "            value = nums[l] + nums[r]\n",
    "            if value > target:\n",
    "                r -= 1\n",
    "            else:\n",
    "                cnt += r - l\n",
    "                l += 1\n",
    "        return cnt\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums = [2,7,11,15]\n",
    "    target = 24\n",
    "    from timeit import timeit\n",
    "    print timeit(\"Solution().twoSum5(nums, target)\", \n",
    "           setup=\"from __main__ import Solution, nums, target\", number=10000)\n",
    "    print timeit(\"Solution().twoSum5_method1(nums, target)\", \n",
    "           setup=\"from __main__ import Solution, nums, target\", number=10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "1KR5TAcjdV4R"
   },
   "source": [
    "### 587. Two Sum - Unique pairs\n",
    "Given an array of integers, find how many unique pairs in the array such that their sum is equal to a specific target number. Please return the number of pairs.\n",
    "```\n",
    "Example\n",
    "Given nums = [1,1,2,45,46,46], target = 47\n",
    "return 2\n",
    "\n",
    "1 + 46 = 47\n",
    "2 + 45 = 47\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 68
    },
    "colab_type": "code",
    "id": "IvsTHJlagk2S",
    "outputId": "ac609359-4c2c-452c-8012-4f45607cad51"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "0.0146870613098\n",
      "0.0122129917145\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param nums: an array of integer\n",
    "    @param target: An integer\n",
    "    @return: An integer\n",
    "    \"\"\"\n",
    "    def twoSum6_method1(self, nums, target):\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) - 1\n",
    "        count = 0\n",
    "        while left < right:\n",
    "            value = nums[left] + nums[right]\n",
    "            if value < target:\n",
    "                left += 1\n",
    "            elif value == target:\n",
    "                if left == 0 or nums[left-1] != nums[left]:\n",
    "                    count += 1\n",
    "                left += 1\n",
    "            else: # value > target\n",
    "                right -= 1\n",
    "        return count\n",
    "    def twoSum6(self, nums, target):\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) - 1\n",
    "        count = 0\n",
    "        while left < right:\n",
    "            value = nums[left] + nums[right]\n",
    "            if value < target:\n",
    "                left += 1\n",
    "            elif value == target:\n",
    "                count += 1\n",
    "                left += 1\n",
    "                right -= 1\n",
    "                while left < right and nums[right] == nums[right+1]:\n",
    "                    right -= 1\n",
    "                while left < right and nums[left] == nums[left-1]:\n",
    "                    left += 1\n",
    "            else: # value > target\n",
    "                right -= 1\n",
    "        return count\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums, k = [1,1,2,45,46,46], 47\n",
    "    print Solution().twoSum6(nums, k)\n",
    "    from timeit import timeit\n",
    "    print timeit(\"Solution().twoSum6_method1(nums, k)\",\n",
    "                 setup=\"from __main__ import nums, k, Solution\", number=10000)\n",
    "    print timeit(\"Solution().twoSum6(nums, k)\",\n",
    "                 setup=\"from __main__ import nums, k, Solution\", number=10000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "OmpzOWI3dWBp"
   },
   "source": [
    "### 533. Two Sum - Closest to target\n",
    "Given an array nums of n integers, find two integers in nums such that the sum is closest to a given number, target.\n",
    "\n",
    "Return the difference between the sum of the two integers and the target.\n",
    "```\n",
    "Example\n",
    "Given array nums = [-1, 2, 1, -4], and target = 4.\n",
    "\n",
    "The minimum difference is 1. (4 - (2 + 1) = 1).\n",
    "\n",
    "Challenge\n",
    "Do it in O(nlogn) time complexity.\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "cxVvEKwCjDL6",
    "outputId": "f554ab30-f28f-4e26-c42e-795abfc72a36"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param nums: an integer array\n",
    "    @param target: An integer\n",
    "    @return: the difference between the sum and the target\n",
    "    \"\"\"\n",
    "    def twoSumClosest(self, nums, target):\n",
    "        if len(nums) < 2:\n",
    "            return -1 \n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) - 1\n",
    "        min_diff = 65535 # MAX_INT\n",
    "        while left < right:\n",
    "            value = nums[left] + nums[right]\n",
    "            if value < target:\n",
    "                min_diff = min(min_diff, target-value)\n",
    "                left += 1\n",
    "            elif value == target:\n",
    "                return 0\n",
    "            else: # value >  target\n",
    "                min_diff = min(min_diff, value-target)\n",
    "                right -= 1\n",
    "        return min_diff\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums, target = [-1,2,1,-4], 4\n",
    "    print Solution().twoSumClosest(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "QsiK49IsdWJx"
   },
   "source": [
    "### 443. Two Sum - Greater than target\n",
    "Given an array of integers, find how many pairs in the array such that their sum is bigger than a specific target number. Please return the number of pairs.\n",
    "```\n",
    "Example\n",
    "Given numbers = [2, 7, 11, 15], target = 24. Return 1. (11 + 15 is the only pair)\n",
    "\n",
    "Challenge\n",
    "Do it in O(1) extra space and O(nlogn) time.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "6aGFy4XRmDOw",
    "outputId": "2de09e93-6cef-4550-a002-f4e37937cd0f"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param nums: an array of integer\n",
    "    @param target: An integer\n",
    "    @return: an integer\n",
    "    \"\"\"\n",
    "    def twoSum2(self, nums, target):\n",
    "        if len(nums) < 2:\n",
    "            return -1\n",
    "        nums.sort()\n",
    "        left, right = 0, len(nums) - 1\n",
    "        count = 0\n",
    "        while left < right:\n",
    "            value = nums[left] + nums[right]\n",
    "            if value <= target:\n",
    "                left += 1\n",
    "            else:\n",
    "                count += right - left\n",
    "                right -= 1\n",
    "        return count\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums, target = [2,7,11,15], 24\n",
    "    print Solution().twoSum2(nums, target)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "QH3CkLZ_HR-F"
   },
   "source": [
    "### 57. 3Sum\n",
    "Description\n",
    "Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.\n",
    "\n",
    "Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)\n",
    "\n",
    "The solution set must not contain duplicate triplets.\n",
    "```\n",
    "Example\n",
    "For example, given array S = {-1 0 1 2 -1 -4}, A solution set is:\n",
    "\n",
    "(-1, 0, 1)\n",
    "(-1, -1, 2)\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 33
    },
    "colab_type": "code",
    "id": "jWLw_p3fgKW-",
    "outputId": "cf1f608b-5ad5-422b-b7aa-1d7ef6d5fa72"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(-11, 4, 7), (-7, 2, 5), (-7, 3, 4), (-5, 1, 4), (-5, 2, 3), (-4, 1, 3)]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param numbers: Give an array numbers of n integer\n",
    "    @return: Find all unique triplets in the array which gives the sum of zero.\n",
    "    \"\"\"\n",
    "    def threeSum(self, numbers):\n",
    "        res = []\n",
    "        numbers.sort()\n",
    "        self.dfs([], 0, res, numbers)\n",
    "        return res\n",
    "\n",
    "    def dfs(self, tmp, start_index, res, S):\n",
    "        #print tmp, start_index\n",
    "        if len(tmp) == 3:\n",
    "            if sum(tmp) == 0:\n",
    "                #print tmp, start_index\n",
    "                res.append(tuple(tmp))\n",
    "            #print 'return'\n",
    "            return\n",
    "        for i in range(start_index, len(S)):\n",
    "            if i == start_index or S[i-1] != S[i]: # duplicate or not ?\n",
    "                self.dfs(tmp + [S[i]], i+1, res, S)\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums = [-11, -7, -5, -4, 3, 1, 2, 3, 4, 5, 5, 7]\n",
    "    print Solution().threeSum(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "0o6LYV2YUKXb"
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def threeSum(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        for i in range(0, len(nums)):\n",
    "            if i > 0 and nums[i] == nums[i-1]:\n",
    "                continue\n",
    "            if nums[i] > 0:\n",
    "                break\n",
    "            \n",
    "            lo = i + 1 \n",
    "            hi = len(nums) - 1 \n",
    "            \n",
    "            while lo < hi:\n",
    "                target = nums[i] + nums[lo] + nums[hi]\n",
    "                if target > 0:\n",
    "                    hi -= 1\n",
    "                elif target < 0:\n",
    "                    lo += 1\n",
    "                else:\n",
    "                    ans.append([nums[i], nums[lo], nums[hi]])\n",
    "                    lo += 1\n",
    "                    \n",
    "                    while lo < len(nums) and nums[i] + nums[lo] + nums[hi] == 0:\n",
    "                        lo += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "K1OmKDy1UN6s"
   },
   "source": [
    "### 18. 4Sum\n",
    "Medium\n",
    "\n",
    "```\n",
    "Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.\n",
    "\n",
    "Note:\n",
    "\n",
    "The solution set must not contain duplicate quadruplets.\n",
    "\n",
    "Example:\n",
    "\n",
    "Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.\n",
    "\n",
    "A solution set is:\n",
    "[\n",
    "  [-1,  0, 0, 1],\n",
    "  [-2, -1, 1, 2],\n",
    "  [-2,  0, 0, 2]\n",
    "]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "jkYP_vb9UjJO"
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def fourSum(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        \n",
    "        def findNSum(nums, target, N, tmp, res):\n",
    "            \n",
    "            if N < 2 or len(nums) < N or target > N * nums[-1] or target < N * nums[0]:\n",
    "                return # early termination\n",
    "            \n",
    "            elif N == 2:\n",
    "                left, right = 0, len(nums) - 1 \n",
    "                while left < right:\n",
    "                    s = nums[left] + nums[right]\n",
    "                    if s == target:\n",
    "                        res.append(tmp + [nums[left], nums[right]])\n",
    "                        left += 1\n",
    "                        while left < right and nums[left] == nums[left-1]:\n",
    "                            left += 1 \n",
    "                    \n",
    "                    elif s < target:\n",
    "                        left += 1\n",
    "                    else:\n",
    "                        right -= 1\n",
    "            \n",
    "            else:\n",
    "                for i in range(len(nums)-N+1):\n",
    "                    if i == 0 or (nums[i-1] != nums[i]):\n",
    "                        findNSum(nums[i+1:], target - nums[i], N-1, tmp + [nums[i]], res)\n",
    "        nums.sort()\n",
    "        res = [] \n",
    "        findNSum(nums, target, 4, [], res)\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "dQaFDifSv7WE"
   },
   "source": [
    "### 382. Triangle Count\n",
    "Given an array of integers, how many three numbers can be found in the array, so that we can build an triangle whose three edges length is the three numbers that we find?\n",
    "```\n",
    "Example\n",
    "Given array S = [3,4,6,7], return 3. They are:\n",
    "\n",
    "[3,4,6]\n",
    "[3,6,7]\n",
    "[4,6,7]\n",
    "Given array S = [4,4,4,4], return 4. They are:\n",
    "\n",
    "[4(1),4(2),4(3)]\n",
    "[4(1),4(2),4(4)]\n",
    "[4(1),4(3),4(4)]\n",
    "[4(2),4(3),4(4)]\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "k3R9ib36v-eO",
    "outputId": "690106c5-ea7c-43bc-c3a6-592794b5d216"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param S: A list of integers\n",
    "    @return: An integer\n",
    "    \"\"\"\n",
    "    def triangleCount(self, S):\n",
    "        S.sort()\n",
    "        left, right = 0, len(S) - 1\n",
    "        ans = 0\n",
    "        for i in range(len(S)):\n",
    "            left, right = 0, i-1\n",
    "            while left < right:\n",
    "                if S[left] + S[right] > S[i]:\n",
    "                    ans += right - left\n",
    "                    right -= 1\n",
    "                else:\n",
    "                    left += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums = [1, 2, 3, 4, 5, 5, 7]\n",
    "    print Solution().triangleCount(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "QSO8ZHXRl0lr"
   },
   "source": [
    "## 经典排序算法，快速选择"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "u2zcpuCUmGoa"
   },
   "source": [
    "### 461. Kth Smallest Numbers in Unsorted Array\n",
    "Find the kth smallest numbers in an unsorted integer array.\n",
    "\n",
    "```\n",
    "Example\n",
    "Given [3, 4, 1, 2, 5], k = 3, the 3rd smallest numbers are [1, 2, 3].\n",
    "\n",
    "Challenge\n",
    "An O(nlogn) algorithm is acceptable, if you can do it in O(n), that would be great.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 34
    },
    "colab_type": "code",
    "id": "A5JG5vlPdVLw",
    "outputId": "88f70958-301f-47d7-ece2-14c61c2f9997"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param k: An integer\n",
    "    @param nums: An integer array\n",
    "    @return: kth smallest element\n",
    "    \"\"\"\n",
    "    def kthSmallest(self, k, nums):\n",
    "        return self.quickselect(k-1, nums)\n",
    "\n",
    "    def quickselect(self, k, nums, lo=None, hi=None):\n",
    "        lo = 0 if lo is None else lo\n",
    "        hi = len(nums) - 1 if hi is None else hi\n",
    "        while True:\n",
    "            if lo == hi:\n",
    "                return nums[lo]\n",
    "            pvt = self.partition(nums, lo, hi)\n",
    "            if k == pvt:\n",
    "                return nums[k]\n",
    "            elif k < pvt:\n",
    "                hi = pvt - 1\n",
    "            else:\n",
    "                lo = pvt + 1\n",
    "\n",
    "    def partition(self, nums, lo=None, hi=None):\n",
    "        lo = 0 if lo is None else lo\n",
    "        hi = len(nums) - 1 if hi is None else hi\n",
    "        pvt = lo\n",
    "        for i in range(lo, hi):\n",
    "            if nums[i] < nums[hi]:\n",
    "                nums[i], nums[pvt] = nums[pvt], nums[i]\n",
    "                pvt += 1\n",
    "        nums[hi], nums[pvt] = nums[pvt], nums[hi]\n",
    "        return pvt\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    k, nums = 3, [2,3,4,8,9]\n",
    "    print Solution().kthSmallest(k, nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "rj0OHnQ7caEI"
   },
   "source": [
    "### 464. Sort Integers II (Quick, Merge, Heap)\n",
    "\n",
    "Description\n",
    "Given an integer array, sort it in ascending order. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.\n",
    "```\n",
    "Example\n",
    "Given [3, 2, 1, 4, 5], return [1, 2, 3, 4, 5].\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 85
    },
    "colab_type": "code",
    "id": "bmumzlo58DdQ",
    "outputId": "948a3905-414d-4eb7-f1f2-e436e852e99f"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "[1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 5, 12]\n",
      "[1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 5, 12]\n",
      "[1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 5, 12]\n"
     ]
    }
   ],
   "source": [
    "# quick sort \n",
    "# Your submission beats 67.20% Submissions!\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param A: an integer array\n",
    "    @return: nothing\n",
    "    \"\"\"\n",
    "    def quicksort(self, nums, lo=None, hi=None):\n",
    "        lo = 0 if lo is None else lo\n",
    "        hi = len(nums) - 1 if hi is None else hi\n",
    "        if lo < hi:\n",
    "            p = self.partition(nums, lo, hi)\n",
    "            self.quicksort(nums, lo, p-1)\n",
    "            self.quicksort(nums, p+1, hi)\n",
    "\n",
    "    def quickselect(self, nums, k, lo=None, hi=None):\n",
    "        lo = 0 if lo is None else lo\n",
    "        hi = len(nums) - 1 if hi is None else hi\n",
    "        while True:\n",
    "            if lo == hi:\n",
    "                return nums[lo]\n",
    "            pvt = self.partition(nums, lo, hi)\n",
    "            if k == pvt:\n",
    "                return nums[k]\n",
    "            elif k < pvt:\n",
    "                hi = pvt - 1\n",
    "            else:\n",
    "                lo = pvt + 1\n",
    "\n",
    "    def partition(self, nums, lo=None, hi=None):\n",
    "        lo = 0 if lo is None else lo\n",
    "        hi = len(nums) - 1 if hi is None else hi\n",
    "        pvt = lo\n",
    "        for i in range(lo, hi):\n",
    "            if nums[i] < nums[hi]:\n",
    "                nums[i], nums[pvt] = nums[pvt], nums[i]\n",
    "                pvt += 1\n",
    "        nums[pvt], nums[hi] = nums[hi], nums[pvt]\n",
    "        return pvt\n",
    "    \n",
    "    # Merge sort \n",
    "    # Your submission beats 33.00% Submissions!\n",
    "    def mergesort(self, nums, lo=None, hi=None):\n",
    "        lo = 0 if lo is None else lo\n",
    "        hi = len(nums) - 1 if hi is None else hi\n",
    "        if lo == hi:\n",
    "            return [nums[lo]]\n",
    "        mid = (lo + hi) // 2\n",
    "        left = self.mergesort(nums, lo, mid)\n",
    "        right = self.mergesort(nums, mid+1, hi)\n",
    "        return self.merge(left, right)\n",
    "\n",
    "    def merge(self, left, right): # merge two sorted list\n",
    "        res = []\n",
    "        i = j = 0\n",
    "        while i < len(left) and j < len(right):\n",
    "                res.append(left[i])\n",
    "                i += 1\n",
    "            else:\n",
    "                res.append(right[j])\n",
    "                j += 1\n",
    "        while i < len(left):\n",
    "            res.append(left[i])\n",
    "            i += 1\n",
    "        while j < len(right):\n",
    "            res.append(right[j])\n",
    "            j += 1\n",
    "        return res\n",
    "    \n",
    "    # Heap sort \n",
    "    # Your submission beats 16.40% Submissions!\n",
    "    def heapsort(self, nums, lo=None, hi=None):\n",
    "        lo = 0 if lo is None else lo\n",
    "        hi = len(nums) - 1 if hi is None else hi\n",
    "\n",
    "        # 1. build the heap\n",
    "        for i in range(hi//2, lo-1, -1):\n",
    "            self.maxheapify(nums, i, hi)\n",
    "        # 2. delete top\n",
    "        for i in range(hi, lo, -1):\n",
    "            nums[lo], nums[i] = nums[i], nums[lo]\n",
    "            # after each iteration, largest goes to ith, next end at i-1\n",
    "            self.maxheapify(nums, lo, i-1)\n",
    "\n",
    "    def maxheapify(self, nums, lo=None, hi=None):\n",
    "        lo = 0 if lo is None else lo\n",
    "        hi = len(nums) - 1 if hi is None else hi\n",
    "        parent = lo\n",
    "        while parent <= hi:\n",
    "            left = parent * 2 + 1\n",
    "            right = parent * 2 + 2\n",
    "            child = -1\n",
    "\n",
    "            if left <= hi and right <= hi:\n",
    "                child = left if nums[left] > nums[right] else right\n",
    "            elif left <= hi:\n",
    "                child = left\n",
    "            else:\n",
    "                return\n",
    "            # max heap root >= left and root >= right\n",
    "            if nums[parent] >= nums[child]:\n",
    "                return\n",
    "            nums[parent], nums[child] = nums[child], nums[parent]\n",
    "            parent = child\n",
    "\n",
    "            \n",
    "if __name__ == \"__main__\":\n",
    "    \n",
    "    nums = [1,5,4,2,1,3,2,1,4,2,12,3,2,2,2]\n",
    "    print Solution().quickselect(nums, 10)\n",
    "    Solution().quicksort(nums)\n",
    "    print nums\n",
    "    \n",
    "    nums = [1, 5, 4, 2, 1, 3, 2, 1, 4, 2, 12, 3, 2, 2, 2]\n",
    "    print Solution().mergesort(nums)\n",
    "\n",
    "    nums = [1,5,4,2,1,3,2,1,4,2,12,3,2,2,2]\n",
    "    # build maxheap\n",
    "    s = Solution()\n",
    "    s.heapsort(nums)\n",
    "    print nums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "_fXiQvyaHSB2"
   },
   "source": [
    "### 143. Sort Colors II (计数排序）\n",
    "Description\n",
    "Given an array of n objects with k different colors (numbered from 1 to k), sort them so that objects of the same color are adjacent, with the colors in the order 1, 2, ... k.\n",
    "```\n",
    "Example\n",
    "Given colors=[3, 2, 2, 1, 4], k=4, your code should sort colors in-place to [1, 2, 2, 3, 4].\n",
    "\n",
    "Challenge\n",
    "A rather straight forward solution is a two-pass algorithm using counting sort. That will cost O(k) extra memory. Can you do it without using extra memory?\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "2vhuUsYwXavd",
    "outputId": "1d97d79b-7fe6-4d5f-81ff-fe093ac555d5"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 1, 2, 2, 2]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param colors: A list of integer\n",
    "    @param k: An integer\n",
    "    @return: nothing\n",
    "    \"\"\"\n",
    "    def sortColors2(self, colors, k):\n",
    "        count = [0 for _ in range(k)]\n",
    "        for color in colors:\n",
    "            count[color - 1] += 1\n",
    "        i = 0\n",
    "        for j in range(len(count)):\n",
    "            while count[j] > 0:\n",
    "                colors[i] = j + 1\n",
    "                i += 1\n",
    "                count[j] -= 1\n",
    "        print colors\n",
    "        \n",
    "if __name__ == \"__main__\":\n",
    "    colors = [2,1,1,2,2]\n",
    "    k = 2\n",
    "    Solution().sortColors2(colors, k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "BUlLbDFoHR5o"
   },
   "source": [
    "### 31. Partition Array\n",
    "Description\n",
    "Given an array nums of integers and an int k, partition the array (i.e move the elements in \"nums\") such that:\n",
    "\n",
    "All elements < k are moved to the left\n",
    "All elements >= k are moved to the right\n",
    "Return the partitioning index, i.e the first index i nums[i] >= k.\n",
    "```\n",
    "Example\n",
    "If nums = [3,2,2,1] and k=2, a valid answer is 1.\n",
    "\n",
    "Challenge\n",
    "Can you partition the array in-place and in O(n)?\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "9dGr2O3e9Bwi",
    "outputId": "ea314f9d-4b3c-484f-860e-4cb6bb6b5127"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param nums: The integer array you should partition\n",
    "    @param k: An integer\n",
    "    @return: The index after partition\n",
    "    \"\"\"\n",
    "    def partitionArray(self, nums, k):\n",
    "        if len(nums) == 0:\n",
    "            return 0 \n",
    "        pvt = 0\n",
    "        while pvt < len(nums):\n",
    "            if nums[pvt] == k: # find the element = k, O(n) as it is not sorted\n",
    "                break\n",
    "            pvt += 1\n",
    "        if pvt == len(nums):\n",
    "            return pvt if k > max(nums) else 0 \n",
    "        nums[pvt], nums[-1] = nums[-1], nums[pvt]\n",
    "        pvt = self.partition(nums, 0, len(nums)-1)\n",
    "        return pvt \n",
    "\n",
    "    def partition(self, nums, lo, hi):\n",
    "        pvt = lo\n",
    "        for i in range(lo, hi):\n",
    "            if nums[i] < nums[hi]:\n",
    "                nums[i], nums[pvt] = nums[pvt], nums[i]\n",
    "                pvt += 1\n",
    "        nums[pvt], nums[hi] = nums[hi], nums[pvt]\n",
    "        return pvt\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums = [9,9,9,8,9,8,7,9,8,8,8,9,8,9,8,8,6,9]\n",
    "    print Solution().partitionArray(nums, 9)\n",
    "    #print Solution().partition([3, 1, 3, 3, 2, 2], 0, 5)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "8C0ePY_OW_2o"
   },
   "source": [
    "### 625. Partition Array II\n",
    "Partition an unsorted integer array into three parts:\n",
    "\n",
    "The front part < low\n",
    "The middle part >= low & <= high\n",
    "The tail part > high\n",
    "Return any of the possible solutions.\n",
    "```\n",
    "Example\n",
    "Given [4,3,4,1,2,3,1,2], and low = 2 and high = 3.\n",
    "\n",
    "Change to [1,1,2,3,2,3,4,4].\n",
    "\n",
    "([1,1,2,2,3,3,4,4] is also a correct answer, but [1,2,1,2,3,3,4,4] is not)\n",
    "\n",
    "Challenge\n",
    "Do it in place.\n",
    "Do it in one pass (one loop).\n",
    "\n",
    "```\n",
    "注意这道题，没有要求low 和high要在该在的位置上，即便要求了， 也先这样做，把前后排好了，去中间找low, high 这也效率要高很多。算法也不容易错。用这道题也可以做 彩虹排序1， 只有三种颜色的情况 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Qd2rNJ19XAPB"
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param: nums: an integer array\n",
    "    @param: low: An integer\n",
    "    @param: high: An integer\n",
    "    @return:\n",
    "    \"\"\"\n",
    "    def partition2(self, nums, low, high):\n",
    "        left, right = 0, len(nums) - 1\n",
    "        i = 0\n",
    "        while i < right:\n",
    "            if nums[i] < low:\n",
    "                nums[i], nums[left] = nums[left], nums[i]\n",
    "                i += 1\n",
    "                left += 1\n",
    "            elif nums[i] > high:\n",
    "                nums[i], nums[right] = nums[right], nums[i]\n",
    "                right -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return nums\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums, low, high = [4,3,4,1,2,3,1,2], 2, 3\n",
    "    print Solution().partition2(nums, low, high)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "NjeLqoHWZthv"
   },
   "source": [
    "### 894. Pancake Sorting\n",
    "Given an an unsorted array, sort the given array. You are allowed to do only following operation on array.\n",
    "\n",
    "flip(arr, i): Reverse array from 0 to i \n",
    "Unlike a traditional sorting algorithm, which attempts to sort with the fewest comparisons possible, the goal is to sort the sequence in as few reversals as possible.\n",
    "```\n",
    "Example\n",
    "Given array = [6, 7, 10, 11, 12, 20, 23]\n",
    "Use flip(arr, i) function to sort the array.\n",
    "```\n",
    "找到最大值的index，翻转到头，再翻转到最尾，尾巴-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "DsAxGA5iZtmd"
   },
   "outputs": [],
   "source": [
    "class FlipTool:\n",
    "    @classmethod\n",
    "    def flip(cls, arr, i):\n",
    "        left, right = 0, i\n",
    "        while left < right:\n",
    "            arr[left], arr[right] = arr[right], arr[left]\n",
    "            left += 1\n",
    "            right -=1\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    @param array: an integer array\n",
    "    @return: nothing\n",
    "    \"\"\"\n",
    "    def pancakeSort(self, arr):\n",
    "        cur_size = len(arr) - 1\n",
    "        while cur_size > 0:\n",
    "            mi = self.findMax(arr, cur_size)\n",
    "            FlipTool.flip(arr, mi)\n",
    "            FlipTool.flip(arr, cur_size)\n",
    "            cur_size -= 1\n",
    "        return arr\n",
    "\n",
    "    def findMax(self, arr, n):\n",
    "        mi = 0\n",
    "        for i in range(n+1):\n",
    "            mi = i if arr[i] > arr[mi] else mi\n",
    "        return mi\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums = [1,2,3]\n",
    "    print Solution().pancakeSort(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "dX6MXc3SSoBk"
   },
   "source": [
    "### 5. Kth Largest Element\n",
    "Find K-th largest element in an array.\n",
    "```\n",
    "Example\n",
    "In array [9,3,2,4,8], the 3rd largest element is 4.\n",
    "\n",
    "In array [1,2,3,4,5], the 1st largest element is 5, 2nd largest element is 4, 3rd largest element is 3 and etc.\n",
    "\n",
    "Challenge\n",
    "O(n) time, O(1) extra memory.\n",
    "```\n",
    "快速选择算法非常容易写错，要记忆模板，和模板写的一模一样，基于模板改。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 33
    },
    "colab_type": "code",
    "id": "pbLEqqmxStNh",
    "outputId": "5a3f5384-1cc8-454b-bfef-8e4000c41f37"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    # k & A a integer and an array\n",
    "    # ans a integer\n",
    "    def kthLargestElement(self, k, A):\n",
    "        # method 1\n",
    "        # return self.quickselect(A, len(A)-k)\n",
    "        # method 2 \n",
    "        import heapq\n",
    "        heapq.heapify(A)\n",
    "        return heapq.nlargest(k, A)[-1]\n",
    "\n",
    "    def quickselect(self, nums, k, lo=None, hi=None):\n",
    "        lo = 0 if lo is None else lo\n",
    "        hi = len(nums) - 1 if hi is None else hi\n",
    "        while True:\n",
    "            if lo == hi:\n",
    "                return nums[lo]\n",
    "            pvt = self.partition(nums, lo, hi)\n",
    "            if k == pvt:\n",
    "                return nums[k]\n",
    "            elif k < pvt:\n",
    "                hi = pvt - 1\n",
    "            else:\n",
    "                lo = pvt + 1\n",
    "\n",
    "    def partition(self, nums, lo=None, hi=None):\n",
    "        if lo >= hi: return lo\n",
    "        lo = 0 if lo is None else lo\n",
    "        hi = len(nums) - 1 if hi is None else hi\n",
    "        pvt = lo\n",
    "        for i in range(lo, hi):\n",
    "            if nums[i] < nums[hi]:\n",
    "                nums[i], nums[pvt] = nums[pvt], nums[i]\n",
    "                pvt += 1\n",
    "        nums[hi], nums[pvt] = nums[pvt], nums[hi]\n",
    "        return pvt\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    k = 10\n",
    "    A = [1,2,3,4,5,6,8,9,10,7]\n",
    "    print Solution().kthLargestElement(k, A)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "fk1pA0kOOCes"
   },
   "source": [
    "## String topics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "BM6sVvUWOCet"
   },
   "source": [
    "### 6. ZigZag Conversion\n",
    "The string \"PAYPALISHIRING\" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)\n",
    "\n",
    "```\n",
    "P   A   H   N\n",
    "A P L S I I G\n",
    "Y   I   R\n",
    "\n",
    "\n",
    "\n",
    "And then read line by line: \"PAHNAPLSIIGYIR\"\n",
    "\n",
    "Write the code that will take a string and make this conversion given a number of rows:\n",
    "\n",
    "string convert(string s, int numRows);\n",
    "Example 1:\n",
    "\n",
    "Input: s = \"PAYPALISHIRING\", numRows = 3\n",
    "Output: \"PAHNAPLSIIGYIR\"\n",
    "Example 2:\n",
    "\n",
    "Input: s = \"PAYPALISHIRING\", numRows = 4\n",
    "Output: \"PINALSIGYAHRPI\"\n",
    "Explanation:\n",
    "\n",
    "P     I    N\n",
    "A   L S  I G\n",
    "Y A   H R\n",
    "P     I\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "P-JOBC0sOCeu",
    "outputId": "5cf06c1e-b947-4308-a615-79af6bd9e254"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['P'], [], [], []]\n",
      "[['P'], ['A'], [], []]\n",
      "[['P'], ['A'], ['Y'], []]\n",
      "[['P'], ['A'], ['Y'], ['P']]\n",
      "2 [['P'], ['A'], ['Y', 'A'], ['P']]\n",
      "1 [['P'], ['A', 'L'], ['Y', 'A'], ['P']]\n",
      "[['P', 'I'], ['A', 'L'], ['Y', 'A'], ['P']]\n",
      "[['P', 'I'], ['A', 'L', 'S'], ['Y', 'A'], ['P']]\n",
      "[['P', 'I'], ['A', 'L', 'S'], ['Y', 'A', 'H'], ['P']]\n",
      "[['P', 'I'], ['A', 'L', 'S'], ['Y', 'A', 'H'], ['P', 'I']]\n",
      "2 [['P', 'I'], ['A', 'L', 'S'], ['Y', 'A', 'H', 'R'], ['P', 'I']]\n",
      "1 [['P', 'I'], ['A', 'L', 'S', 'I'], ['Y', 'A', 'H', 'R'], ['P', 'I']]\n",
      "[['P', 'I', 'N'], ['A', 'L', 'S', 'I'], ['Y', 'A', 'H', 'R'], ['P', 'I']]\n",
      "[['P', 'I', 'N'], ['A', 'L', 'S', 'I', 'G'], ['Y', 'A', 'H', 'R'], ['P', 'I']]\n",
      "[['P', 'I', 'N'], ['A', 'L', 'S', 'I', 'G'], ['Y', 'A', 'H', 'R'], ['P', 'I']]\n"
     ]
    }
   ],
   "source": [
    "class Solution:\n",
    "    def convert(self, s, numRows):\n",
    "        result =[[] for _ in range(numRows)]\n",
    "        res = \"\"\n",
    "        i = 0 \n",
    "        flag = 0\n",
    "        \n",
    "        while i < len(s):\n",
    "            if flag == 0:\n",
    "                for j in range(len(result)):\n",
    "                    if i < len(s):\n",
    "                        result[j].append(s[i])\n",
    "                        print(result)\n",
    "                        i += 1\n",
    "                \n",
    "                flag = 1 \n",
    "            else:\n",
    "                for j in range(len(result)-2, 0, -1):\n",
    "                    if i < len(s):\n",
    "                        result[j].append(s[i])\n",
    "                        print(j, result)\n",
    "                        i += 1\n",
    "                flag = 0\n",
    "        \n",
    "        for words in result:\n",
    "            for word in words:\n",
    "                res += word\n",
    "        \n",
    "        print(result)\n",
    "        return res\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    s = Solution()\n",
    "    s.convert('PAYPALISHIRING', 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "ZFCDhjhwOCe2"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "9qXcRi9nOCe6"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "jh4EVGkPOCe8"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Bxmz9i7cOCe-"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Egh5S0b3OCfB"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "iqa89ts1OCfE"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "Hv-rmEnUOCfH"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "F8NAK9-hOCfK"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "q27iYG4dOCfP"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "HunQX8JQOCfR"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "TetzD9eMOCfT"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "bhRq0E0sOCfX"
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "VeM11MN3OCfZ"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "accelerator": "GPU",
  "colab": {
   "collapsed_sections": [
    "JF1PH6BYyFqc",
    "8-veu44AzpHb",
    "oTcS_Evw6hRs"
   ],
   "include_colab_link": true,
   "name": "Ch02 Two Pointers and Sorting",
   "provenance": [],
   "toc_visible": true,
   "version": "0.3.2"
  },
  "kernelspec": {
   "display_name": "py37",
   "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.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}