22_01_SlidingWindow.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "run_control": {
     "frozen": false,
     "read_only": false
    }
   },
   "source": [
    "# Sliding Window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "run_control": {
     "frozen": false,
     "read_only": false
    }
   },
   "source": [
    "Sliding Window technique shows how a nested for loop in few problems can be converted to single for loop and hence reducing the time complexity.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a id='Ex1'> Ex.1 Remove Duplicates from Sorted Array \n",
    "\n",
    "Given a sorted array, remove the duplicates such that each element appear only once and return the new length."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def removeDuplicates(alist):\n",
    "    if not alist:\n",
    "        return 0\n",
    "\n",
    "    tail = 0\n",
    "\n",
    "    for j in range(1, len(alist)):\n",
    "        if alist[j] != alist[tail]:\n",
    "            tail += 1\n",
    "            alist[tail] = alist[j]\n",
    "\n",
    "    return tail + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alist = [1,1,2]\n",
    "removeDuplicates(alist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alist = [0,0,1,1,1,2,2,3,3,4]\n",
    "removeDuplicates(alist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def removeDuplicates(alist):\n",
    "    i = 0\n",
    "    for n in alist:\n",
    "        if i == 0 or n > alist[i - 1]:\n",
    "            alist[i] = n\n",
    "            i += 1\n",
    "    return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alist = [1,1,2]\n",
    "removeDuplicates(alist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alist = [0,0,1,1,1,2,2,3,3,4]\n",
    "removeDuplicates(alist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### <a id='Ex2'> Ex.2 Remove Duplicates from Sorted Array II \n",
    "\n",
    "What if duplicates are allowed at most twice?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def removeDuplicates(nums):\n",
    "    if len(nums) <= 2: return len(nums)\n",
    "    prev, curr = 1, 2\n",
    "    while curr < len(nums):\n",
    "        if nums[curr] == nums[prev] and  nums[curr] == nums[prev - 1]:\n",
    "            curr += 1\n",
    "        else:\n",
    "            prev += 1\n",
    "            nums[prev] = nums[curr]\n",
    "            curr += 1\n",
    "    return prev + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def removeDuplicates2(nums):\n",
    "    count = 0\n",
    "    for i in range(len(nums)):\n",
    "        if count < 2 or nums[count - 2] != nums[i]:\n",
    "            nums[count] = nums[i]\n",
    "            count += 1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a id='Ex3'> Ex.3 Remove Element\n",
    "\n",
    "Given an array nums and a value val, remove all instances of that value in-place and return the new length."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def removeElement(nums, val):\n",
    "    i = 0\n",
    "    for j in range(len(nums)):\n",
    "        if nums[j] != val:\n",
    "            nums[i] = nums[j]\n",
    "            i += 1\n",
    "    return i        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [ 3, 2, 2, 3 ]\n",
    "removeElement(nums, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [ 0, 1, 2, 2, 3, 0, 4, 2 ]\n",
    "removeElement(nums, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def removeElement(nums, val):\n",
    "    start, end = 0, len(nums) - 1\n",
    "    while start <= end:\n",
    "        if nums[start] == val:\n",
    "            nums[start], end = nums[end], end - 1\n",
    "        else:\n",
    "            start +=1\n",
    "    return start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [ 3, 2, 2, 3 ]\n",
    "removeElement(nums, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [ 0, 1, 2, 2, 3, 0, 4, 2 ]\n",
    "removeElement(nums, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a id='Ex4'> Ex.4 Maximum Average Subarray \n",
    "\n",
    "Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value \n",
    "\n",
    "Assume 1 <= k <= n \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def findMaxnumsverage(nums, K):\n",
    "    P = [0]\n",
    "    for x in nums:\n",
    "        P.append(P[-1] + x)\n",
    "\n",
    "    moving_sum = max(P[i+K] - P[i] \n",
    "             for i in range(len(nums) - K + 1))\n",
    "    return moving_sum / float(K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12.75"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [ 1, 12, -5, -6, 50, 3 ]\n",
    "findMaxnumsverage(nums, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def findMaxnumsverage(nums, K):\n",
    "    moving_sum = 0.0\n",
    "    for i in range(K):\n",
    "        moving_sum += nums[i]\n",
    "    res = moving_sum\n",
    "    for i in range(K, len(nums)):\n",
    "        moving_sum += nums[i] - nums[i - K]\n",
    "        res = max(res, moving_sum)\n",
    "    return res / K"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12.75"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [ 1, 12, -5, -6, 50, 3 ]\n",
    "findMaxnumsverage(nums, 4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a id='Ex5'> Ex.5 Longest Continuous Increasing Subsequence\n",
    "\n",
    "Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def findLengthOfLCIS(nums):\n",
    "    result, count = 0, 0\n",
    "    for i in range(len(nums)):\n",
    "        if i == 0 or nums[i-1] < nums[i]:\n",
    "            count += 1\n",
    "            result = max(result, count)\n",
    "        else:\n",
    "            count = 1\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1,3,5,4,7]\n",
    "findLengthOfLCIS(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2,2,2,2,2]\n",
    "findLengthOfLCIS(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a id='Ex6'> Ex.6 Minimum Size Subarray Sum \n",
    "\n",
    "Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead\n",
    "\n",
    "Given the array [2,3,1,2,4,3] and s = 7\n",
    "\n",
    "the subarray [4,3] has the minimal length under the problem constraint \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def minsubarray(alist, target):\n",
    "    if len(alist) == 0:\n",
    "        return 0\n",
    "    \n",
    "    i = j = sums = 0\n",
    "    minimum = sys.maxsize\n",
    "    \n",
    "    while j < len(alist):\n",
    "        sums += alist[j]\n",
    "        j += 1\n",
    "        while sums >= target:\n",
    "            minimum = min(minimum, j - i)\n",
    "            sums -= alist[i]\n",
    "            i += 1\n",
    "    return 0 if min == sys.maxsize else minimum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a id='Ex7'> Ex.7 Implement strStr()\n",
    "\n",
    "Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def strStr(haystack, needle):\n",
    "    if len(haystack) < len(needle): \n",
    "        return None\n",
    "    i = 0\n",
    "    while i < len(haystack) - len(needle) + 1:\n",
    "        j = 0\n",
    "        k = i\n",
    "        while j < len(needle):\n",
    "            if haystack[k] == needle[j]:\n",
    "                j+=1; k+=1\n",
    "            else:\n",
    "                break\n",
    "        if j == len(needle):\n",
    "            break\n",
    "        else:\n",
    "            i+=1\n",
    "    if i == len(haystack)-len(needle)+1:\n",
    "        return None\n",
    "    else:\n",
    "        return haystack[i:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def strStr(haystack, needle):\n",
    "    if len(haystack) < len(needle): \n",
    "        return None\n",
    "    l1 = len(haystack)\n",
    "    l2 = len(needle)\n",
    "    for i in range(l1 - l2 + 1):\n",
    "        count = 0\n",
    "        while count < l2 and haystack[i + count] == needle[count]:\n",
    "            count += 1\n",
    "        if count == l2:\n",
    "            return i\n",
    "    return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### <a id='Ex8'> Ex.8 Subarray Product Less Than K\n",
    "\n",
    "Your are given an array of positive integers nums\n",
    "\n",
    "Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def bruteforce(nums, k):\n",
    "    count = 0\n",
    "    for i in range(len(nums)):\n",
    "        product = 1\n",
    "        for j in range(i, len(nums)):\n",
    "            product *= nums[j]\n",
    "            if (product >= k): break\n",
    "            count += 1\n",
    "    return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "19\n"
     ]
    }
   ],
   "source": [
    "nums = [10, 5, 2, 6]\n",
    "k = bruteforce(nums, 100)\n",
    "print(k)\n",
    "\n",
    "nums = [1,5,4,3,6,2,7]\n",
    "k = bruteforce(nums, 100)\n",
    "print(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "'''\n",
    "10, 5, 2, 6\n",
    "10            Y\n",
    "10, 5         Y\n",
    "10, 5, 2      X\n",
    "    5, 2      Y\n",
    "    5, 2, 6   Y\n",
    "'''\n",
    "def numSubarrayProductLessThanK(nums, k):\n",
    "    product = 1\n",
    "    i = 0\n",
    "    ans = 0\n",
    "    for j, num in enumerate(nums):\n",
    "        product *= num\n",
    "        while product >= k:\n",
    "            product /= nums[i]\n",
    "            i += 1\n",
    "        ans += (j - i + 1)\n",
    "    \n",
    "    return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "19\n"
     ]
    }
   ],
   "source": [
    "nums = [10, 5, 2, 6]\n",
    "k = numSubarrayProductLessThanK(nums, 100)\n",
    "print(k)\n",
    "\n",
    "nums = [1,5,4,3,6,2,7]\n",
    "k = numSubarrayProductLessThanK(nums, 100)\n",
    "print(k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}