Two Pointers.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Two Pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## <font color=red>16. 3Sum Closest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.\n",
    "\n",
    "    For example, given array S = {-1 2 1 -4}, and target = 1.\n",
    "\n",
    "    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Brutal force O(n^3). We could reduce it to O(n^2) by first sort the array, then we pick up the first number starting from the beginning. Then we use two pointers to find second and third number in the remaining sublist."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "class Solution(object):\n",
    "    def threeSumClosest(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        min_err=sys.maxint\n",
    "        min_sum3=0\n",
    "        for i in range(n-2):\n",
    "            j=i+1\n",
    "            k=n-1\n",
    "            while j<k:\n",
    "                sum3=nums[i]+nums[j]+nums[k]\n",
    "                err=sum3-target\n",
    "                if err>0:\n",
    "                    if abs(err)<min_err:\n",
    "                        min_err=abs(err)\n",
    "                        min_sum3=sum3\n",
    "                    k-=1\n",
    "                elif err<0:\n",
    "                    if abs(err)<min_err:\n",
    "                        min_err=abs(err)\n",
    "                        min_sum3=sum3\n",
    "                    j+=1\n",
    "                else:\n",
    "                    return sum3\n",
    "        return min_sum3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9223372036854775807"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import sys\n",
    "sys.maxint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 28. Implement strStr()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implement strStr().\n",
    "\n",
    "Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The strstr(const char *haystack, const char *needle) function finds the first occurrence of the substring needle in the string haystack. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: Brutal force: do one pass over haystack and check needle. Time complexity O((n-k)*k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def strStr(self, haystack, needle):\n",
    "        \"\"\"\n",
    "        :type haystack: str\n",
    "        :type needle: str\n",
    "        :rtype: int\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There is a more advanced KMP method in solving string match problems which I will try to make sense later."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 80. Remove Duplicates from Sorted Array II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Follow up for \"Remove Duplicates\":\n",
    "What if duplicates are allowed at most twice?\n",
    "\n",
    "For example,\n",
    "Given sorted array nums = [1,1,1,2,2,3],\n",
    "\n",
    "Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: We could use a hashtable to store the counts of each number. Then we use two pointer to keep track of the original index and the index of shrinked list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def removeDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        num_dict={}\n",
    "        n=len(nums)\n",
    "        i=0\n",
    "        j=0\n",
    "        while i<n:\n",
    "            if not num_dict.get(nums[j]):\n",
    "                num_dict[nums[j]]=1\n",
    "            else:\n",
    "                num_dict[nums[j]]+=1\n",
    "                if num_dict[nums[j]]>2:\n",
    "                    nums.pop(j)\n",
    "                    j-=1\n",
    "            i+=1\n",
    "            j+=1\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above solution does not make use of the sorted nature of the array and takes extra memory. Alternatively, we could use a boolean last_equal to keep track of the repeated number of a value in a sorted list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def removeDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        last_equal=False\n",
    "        n=len(nums)\n",
    "        i=1\n",
    "        j=1\n",
    "        while i<n:\n",
    "            if nums[j]==nums[j-1]:\n",
    "                if last_equal:\n",
    "                    nums.pop(j)\n",
    "                    j-=1\n",
    "                else:\n",
    "                    last_equal=True\n",
    "            else:\n",
    "                last_equal=False\n",
    "                \n",
    "            i+=1\n",
    "            j+=1\n",
    "            \n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 167. Two Sum II - Input array is sorted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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",
    "Input: numbers={2, 7, 11, 15}, target=9\n",
    "\n",
    "Output: index1=1, index2=2\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: This problem assumes $a_1<a_2...<a_n$ in the sorted list such that the solution is unique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def twoSum(self, numbers, target):\n",
    "        \"\"\"\n",
    "        :type numbers: List[int]\n",
    "        :type target: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        n=len(numbers)\n",
    "        p1=0\n",
    "        p2=n-1\n",
    "        while p1<p2:\n",
    "            if numbers[p1]+numbers[p2]==target:\n",
    "                break\n",
    "            elif numbers[p1]+numbers[p2]<target:\n",
    "                p1+=1\n",
    "            elif numbers[p1]+numbers[p2]>target:\n",
    "                p2-=1\n",
    "        return [p1+1,p2+1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 287. Find the Duplicate Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.\n",
    "\n",
    "Note:\n",
    "* You must not modify the array (assume the array is read only).\n",
    "* You must use only constant, O(1) extra space.\n",
    "* Your runtime complexity should be less than O(n^2).\n",
    "* There is only one duplicate number in the array, but it could be repeated more than once.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution: The idea is to do as many swaps as necessary to make all the non-duplicate numbers in their correct position. For the duplicate number, it will eventually swap with itself. So here is what I do:\n",
    "\n",
    "1. one pass through the nums from 0 to n\n",
    "2. check if every element is in its right position\n",
    "3. if not, keep on swapping until: a. the right element is in the current position; b. the element swaps with itself, duplicate found"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def findDuplicate(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            while nums[i]!=i+1:\n",
    "                if nums[i]!=nums[nums[i]-1]:\n",
    "                    tmp=nums[i]\n",
    "                    nums[i]=nums[nums[i]-1]\n",
    "                    nums[tmp-1]=tmp\n",
    "                else:\n",
    "                    return nums[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "o=Solution()\n",
    "o.findDuplicate([2,1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}