519_array.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 661. Image Smoother\n",
    "\n",
    "Given a 2D integer matrix M representing the gray scale of an image, you need to design a smoother to make the gray scale of each cell becomes the average gray scale (rounding down) of all the 8 surrounding cells and itself. If a cell has less than 8 surrounding cells, then use as many as you can."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def imageSmoother(self, M):\n",
    "        \"\"\"\n",
    "        :type M: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        r = [[]]\n",
    "        def avg(i, j, M):\n",
    "            k1 = max(i-1, 0)\n",
    "            k2 = min(i+1, len(M)-1)\n",
    "            l1 = max(j-1, 0)\n",
    "            l2 = min(j+1, len(M[0])-1)\n",
    "            s = 0\n",
    "            for k in range(k1, k2+1):\n",
    "                s += sum(M[k][l1:l2+1])\n",
    "            return s/((k2-k1+1)*(l2-l1+1))\n",
    "\n",
    "        for i in range(len(M)):\n",
    "            for j in range(len(M[0])):\n",
    "                r[i].append(int(avg(i, j, M)))\n",
    "            if i < len(M)-1:\n",
    "                r.append([])\n",
    "        return r "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "ename": "IndentationError",
     "evalue": "unexpected indent (<ipython-input-67-e0c31419e123>, line 2)",
     "output_type": "error",
     "traceback": [
      "\u001b[0;36m  File \u001b[0;32m\"<ipython-input-67-e0c31419e123>\"\u001b[0;36m, line \u001b[0;32m2\u001b[0m\n\u001b[0;31m    def imageSmoother(self, M):\u001b[0m\n\u001b[0m    ^\u001b[0m\n\u001b[0;31mIndentationError\u001b[0m\u001b[0;31m:\u001b[0m unexpected indent\n"
     ]
    }
   ],
   "source": [
    "# Advanced version\n",
    "    def imageSmoother(self, M):\n",
    "        \"\"\"\n",
    "        :type M: List[List[int]]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        if not M: return 0\n",
    "        \n",
    "        w, h = len(M[0]), len(M)\n",
    "        output = [[0] * w for _ in range(h)]\n",
    "        \n",
    "        if w < 2 or h < 2:\n",
    "            if w == 1 and h == 1:\n",
    "                return M\n",
    "            if w == 1 and h > 1:\n",
    "                for i in range(h):\n",
    "                    if i == 0:\n",
    "                        output[i][0] = (M[i][0]+M[i+1][0])//2\n",
    "                    elif i == h - 1:\n",
    "                        output[i][0] = (M[i][0]+M[i-1][0])//2\n",
    "                    else:\n",
    "                        output[i][0] = (M[i-1][0]+M[i][0]+M[i+1][0])//3\n",
    "                \n",
    "                return output\n",
    "            if w > 1 and h == 1:\n",
    "                for j in range(w):\n",
    "                    if j == 0:\n",
    "                        output[0][j] = (M[0][j]+M[0][j+1])//2\n",
    "                    elif j == w - 1:\n",
    "                        output[0][j] = (M[0][j]+M[0][j-1])//2\n",
    "                    else:\n",
    "                        output[0][j] = (M[0][j-1]+M[0][j]+M[0][j+1])//3\n",
    "                \n",
    "                return output\n",
    "        \n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                if 0 < i < h - 1 and 0 < j < w - 1:\n",
    "                    output[i][j] = (M[i-1][j-1]+M[i][j-1]+M[i+1][j-1]\\\n",
    "                          +M[i-1][j]+M[i][j]+M[i+1][j]+M[i-1][j+1]\\\n",
    "                          +M[i][j+1]+M[i+1][j+1])//9\n",
    "                elif i == 0 and 0 < j < w - 1:\n",
    "                    output[i][j] = (M[i][j-1]+M[i][j]+M[i][j+1]\\\n",
    "                          +M[i+1][j-1]+M[i+1][j]+M[i+1][j+1])//6\n",
    "                elif i == h - 1 and 0 < j < w - 1:\n",
    "                    output[i][j] = (M[i-1][j-1]+M[i-1][j]+M[i-1][j+1]\\\n",
    "                          +M[i][j-1]+M[i][j]+M[i][j+1])//6\n",
    "                elif 0 < i < h - 1 and j == 0:\n",
    "                    output[i][j] = (M[i-1][j]+M[i][j]+M[i+1][j]\\\n",
    "                          +M[i-1][j+1]+M[i][j+1]+M[i+1][j+1])//6\n",
    "                elif 0 < i < h - 1 and j == w - 1:\n",
    "                    output[i][j] = (M[i-1][j-1]+M[i][j-1]+M[i+1][j-1]\\\n",
    "                          +M[i-1][j]+M[i][j]+M[i+1][j])//6\n",
    "                elif i == 0 and j == 0:\n",
    "                    output[i][j] = (M[i][j]+M[i+1][j]+M[i][j+1]+M[i+1][j+1])//4\n",
    "                elif i == h - 1 and j == 0:\n",
    "                    output[i][j] = (M[i][j]+M[i-1][j]+M[i][j+1]+M[i-1][j+1])//4\n",
    "                elif i == 0 and j == w - 1:\n",
    "                    output[i][j] = (M[i][j]+M[i+1][j]+M[i][j-1]+M[i+1][j-1])//4\n",
    "                elif i == h - 1 and j == w - 1:\n",
    "                    output[i][j] = (M[i][j]+M[i-1][j]+M[i][j-1]+M[i-1][j-1])//4\n",
    "                else:\n",
    "                    continue\n",
    "        return output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 746. Min Cost Climbing Stairs (*)\n",
    "\n",
    "On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).\n",
    "\n",
    "Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    \n",
    "    def minCostClimbingStairs(self, cost):\n",
    "        \"\"\"\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        for i in range(2, len(cost)):\n",
    "            cost[i] = cost[i] + min(cost[i-1], cost[i-2])\n",
    "        return min(cost[len(cost)-1], cost[len(cost)-2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def minCostClimbingStairs(self, cost):\n",
    "        \"\"\"\n",
    "        :type cost: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        f1 = f2 = 0\n",
    "        for x in cost:\n",
    "            f1, f2 = x + min(f1, f2), f1\n",
    "        return min(f1, f2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 119. Pascal's Triangle II\n",
    "Given a non-negative index k where k $\\le$ 33, return the $k^{th}$ index row of the Pascal's triangle.\n",
    "\n",
    "Note that the row index starts from 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def getRow(self, rowIndex):\n",
    "        \"\"\"\n",
    "        :type rowIndex: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        def fac(i, j):\n",
    "            v = 1\n",
    "            for k in range(i, j+1):\n",
    "                v = v * k\n",
    "            return v\n",
    "        r = [1]                \n",
    "        for i in range(1,rowIndex+1):\n",
    "            r.append(int(fac(rowIndex-i+1,rowIndex)/fac(1, i)))\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "### Advanced solution\n",
    "class Solution:\n",
    "    def getRow(self, k):\n",
    "        \"\"\"\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        res = [1]\n",
    "        cur = k\n",
    "        for i in range(k//2):\n",
    "            res += res[-1] * cur // (i+1),\n",
    "            cur -= 1\n",
    "        if k % 2 == 0:\n",
    "            res = res + res[:-1][::-1]\n",
    "        else:\n",
    "            res = res + res[::-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 628. Maximum Product of Three Numbers\n",
    "\n",
    "Given an integer array, find three numbers whose product is maximum and output the maximum product."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def maximumProduct(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        return max(nums[0]*nums[1]*nums[-1], nums[-1]*nums[-2]*nums[-3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "### Advanced Version\n",
    "class Solution:\n",
    "    def maximumProduct(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        import heapq\n",
    "        a, b = heapq.nlargest(3, nums), heapq.nsmallest(2, nums)\n",
    "        return max(a[0]*a[1]*a[2], a[0]*b[0]*b[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 122. Best Time to Buy and Sell Stock II\n",
    "\n",
    "Say you have an array for which the $i^{th}$ element is the price of a given stock on day i.\n",
    "\n",
    "Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [],
   "source": [
    "    def maxProfit(prices):\n",
    "        \"\"\"\n",
    "        :type prices: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(prices)\n",
    "        profit = 0\n",
    "        def find_profit(prices, n, profit):\n",
    "            find = False\n",
    "            for j in range(1, n):\n",
    "                if prices[j]>prices[j-1]:  # buy at j-1\n",
    "                    find = True\n",
    "                    print(\"buy\", j-1)\n",
    "                    break\n",
    "            if not find:   # no transaction any more\n",
    "                return profit\n",
    "            else:   # buy at j-1\n",
    "                for i in range(j, n):\n",
    "                    if prices[i] < prices[i-1]:  # sell at i-1\n",
    "                        print(\"sell\", i-1)\n",
    "                        find = False\n",
    "                        break\n",
    "                if find:   # the largest one is the last one\n",
    "                    profit += (prices[i] - prices[j-1])\n",
    "                    return profit\n",
    "                else: # still exist possible transaction \n",
    "                    profit += (prices[i-1] - prices[j-1])\n",
    "                    return find_profit(prices[i-1:], len(prices[i-1:]), profit)\n",
    "        return find_profit(prices, n, profit)\n",
    "  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "### Advanced Version\n",
    "    def maxProfit(self, prices):\n",
    "        profits = 0 \n",
    "        ln = len(prices)\n",
    "        if not ln:\n",
    "            return 0\n",
    "        elif ln == 2:\n",
    "            return (prices[1]-prices[0]) if prices[1] > prices[0] else 0\n",
    "        lastPrice = prices[0]\n",
    "        for price in prices:\n",
    "            if lastPrice < price:\n",
    "                profits+= (price-lastPrice)\n",
    "            lastPrice = price\n",
    "        return profits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 219. Contains Duplicate II\n",
    "\n",
    "Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [],
   "source": [
    "## not good\n",
    "def containsNearbyDuplicate(nums, k):   \n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        dif = {}\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in dif.keys():\n",
    "                v = min(i -  dif[nums[i]][1], dif[nums[i]][2]) if dif[nums[i]][2] > 0 else i -  dif[nums[i]][1]\n",
    "                dif[nums[i]] = [dif[nums[i]][1], i, v]\n",
    "            else:\n",
    "                dif[nums[i]] = [i, i, 0]\n",
    "        r = sorted(dif.values(), key = lambda x: x[2], reverse=True)[0][2]\n",
    "        return dif, r, r <= k if r != 0 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "({1: [0, 0, 0], 2: [1, 1, 0]}, 0, False)"
      ]
     },
     "execution_count": 155,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "### Advanced Version\n",
    "class Solution:\n",
    "    def containsNearbyDuplicate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        s=set(nums)\n",
    "        if len(s)==len(nums):return False\n",
    "        d=dict()\n",
    "        for num in nums:\n",
    "            d[num]=d.get(num,0)+1\n",
    "        for num in d:\n",
    "            if d[num]>1:\n",
    "                index1=-1\n",
    "                index2=-1\n",
    "                for i in range(len(nums)):\n",
    "                    if nums[i]==num and index1==-1:index1=i\n",
    "                    elif nums[i]==num and index2==-1:index2=i\n",
    "                    elif nums[i]==num and index1!=-1 and index2!=-1:\n",
    "                        index1=index2\n",
    "                        index2=i\n",
    "                    print(index2,index1)\n",
    "                    if index1!=-1 and index2!=-1 and abs(index2-index1)<=k:return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 26. Remove Duplicates from Sorted Array\n",
    "\n",
    "Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.\n",
    "\n",
    "Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def removeDuplicates(nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        j = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] != nums[j]:\n",
    "                j += 1\n",
    "                nums[j] = nums[i]\n",
    "        del nums[j+1:]\n",
    "        return \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 4, 6]"
      ]
     },
     "execution_count": 166,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "### Advanced Version\n",
    "class Solution:\n",
    "    def removeDuplicates(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        nums[:] = sorted(list(set(nums)))\n",
    "        return len(nums)\n",
    "        \n",
    "        \"\"\"\n",
    "        index = 0\n",
    "        while index < len(nums) - 1:\n",
    "            if nums[index] == nums[index+1]:\n",
    "                del nums[index]\n",
    "            else:\n",
    "                index += 1\n",
    "        return len(nums)\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 605. Can Place Flowers\n",
    "\n",
    "Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.\n",
    "\n",
    "Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "## not so good\n",
    "def canPlaceFlowers(flowerbed, n):\n",
    "        \"\"\"\n",
    "        :type flowerbed: List[int]\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        n1 = 0\n",
    "        j = -2\n",
    "        for i in range(len(flowerbed)):\n",
    "            if flowerbed[i] == 1:\n",
    "                n1 += max(0, int((i-j)/2-1))\n",
    "                j = i\n",
    "        n1 += max(0, int((len(flowerbed)+1-j)/2-1))\n",
    "        return n1 > n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Advanced Version\n",
    "class Solution:\n",
    "    def canPlaceFlowers(self, flowerbed, n):\n",
    "        \"\"\"\n",
    "        :type flowerbed: List[int]\n",
    "        :type n: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        p = flowerbed.count(1)\n",
    "        m = int(len(flowerbed) / 2)\n",
    "        if p+n <= m+1:\n",
    "            pos = 0\n",
    "            while pos < len(flowerbed):\n",
    "                if n == 0:\n",
    "                    print(n)\n",
    "                    return True\n",
    "                else:\n",
    "                    if pos+1 < len(flowerbed):\n",
    "                        if flowerbed[pos] == 0 and flowerbed[pos+1] == 0:\n",
    "                            print(pos)\n",
    "                            n-=1\n",
    "                            pos+=2\n",
    "                        elif flowerbed[pos] == 1:\n",
    "                            pos += 2\n",
    "                        else:\n",
    "                            pos +=3\n",
    "                    else:\n",
    "                        if flowerbed[pos] == 0:\n",
    "                            n-=1\n",
    "                            pos+=2\n",
    "            if n == 0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 189. Rotate Array\n",
    "\n",
    "Given an array, rotate the array to the right by k steps, where k is non-negative."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        temp = nums[:]\n",
    "        k = k % len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = temp[i-k]\n",
    "        return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "## Advanced Version\n",
    "class Solution:\n",
    "    def rotate(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        k = k % n\n",
    "        nums[:k], nums[k:] = nums[n-k:], nums[:n-k]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Analysis:\n",
    "    It's better not to copy the initial array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 665. Non-decreasing Array\n",
    "\n",
    "Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.\n",
    "\n",
    "We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def checkPossibility(nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        find = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i-1] > nums[i]:\n",
    "                find -= 1\n",
    "                if i < len(nums)-1:\n",
    "                    for j in range(i+1, len(nums)):\n",
    "                        if nums[j] != nums[i]:\n",
    "                            break\n",
    "                    if nums[j] < nums[i]:\n",
    "                        return False \n",
    "                    elif i > 1 and nums[i] < nums[i-2] and nums[j] < nums[i-1]:\n",
    "                            return False\n",
    "            if find < 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 214,
   "metadata": {},
   "outputs": [],
   "source": [
    "## Advanced Version\n",
    "class Solution:\n",
    "    def checkPossibility(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        possibility_flag = False\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] < nums[i-1]:\n",
    "                if possibility_flag:\n",
    "                    return False\n",
    "                possibility_flag = True\n",
    "                if (i-2 < 0 or i-2 >= 0 and nums[i-2] < nums[i]) or (i+1 >= len(nums) or i+1 < len(nums) and nums[i+1] > nums[i-1]):\n",
    "                    pass\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 532. K-diff Pairs in an Array\n",
    "\n",
    "Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 225,
   "metadata": {},
   "outputs": [],
   "source": [
    "# good but tried many times\n",
    "def findPairs(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        pair = 0\n",
    "        uniq_nums = set(nums)\n",
    "        if k < 0:\n",
    "            return 0\n",
    "        elif k == 0:\n",
    "            c = {}\n",
    "            for num in nums:\n",
    "                if num in c.keys():\n",
    "                    if not c[num]:\n",
    "                        pair += 1\n",
    "                        c[num] = True\n",
    "                else:\n",
    "                    c[num] = False\n",
    "        else:\n",
    "            for v in uniq_nums:\n",
    "                if v + k in uniq_nums:\n",
    "                    pair += 1\n",
    "        return pair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Advanced Version\n",
    "class Solution:\n",
    "    def findPairs(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # import collections\n",
    "        # unique_nums = set(nums)\n",
    "        # count = 0\n",
    "        # new_nums = collections.Counter(nums)\n",
    "        # if k == 0:\n",
    "        #     for i in unique_nums:\n",
    "        #         if new_nums[i] > 1:\n",
    "        #             count +=1\n",
    "        #     return count\n",
    "        # elif k < 0:\n",
    "        #     return 0\n",
    "        # elif k > 0:\n",
    "        #     for i in unique_nums:\n",
    "        #         if i+k in unique_nums:\n",
    "        #             count += 1\n",
    "        #     return count\n",
    "        \n",
    "# 用counter来做\n",
    "        # import collections\n",
    "        # count = 0\n",
    "        # list_nums = set(nums)\n",
    "        # if k == 0:\n",
    "        #     nums = collections.Counter(nums)\n",
    "        #     for each in nums:\n",
    "        #         if nums[each] > 1:\n",
    "        #             count += 1\n",
    "        #     return count\n",
    "        # elif k < 0:\n",
    "        #     return 0\n",
    "        # elif k > 0:\n",
    "        #     for i in list_nums:\n",
    "        #         if i + k in list_nums:\n",
    "        #             count += 1\n",
    "        #     return count\n",
    "        \n",
    "# 用dict来做\n",
    "\n",
    "        count = 0\n",
    "        if k < 0 :\n",
    "            return count\n",
    "        if k == 0:\n",
    "            new_nums = collections.defaultdict(int)\n",
    "            for i in nums:\n",
    "                new_nums[i] +=1\n",
    "            for value in new_nums:\n",
    "                if new_nums[value] > 1:\n",
    "                    count += 1\n",
    "            return count\n",
    "        if k > 0 :\n",
    "            nums = set(nums)\n",
    "            for i in nums:\n",
    "                if i+k in nums:\n",
    "                    count += 1\n",
    "            return count\n",
    "\n",
    "#         if k < 0:\n",
    "#             return 0\n",
    "#         if k == 0:\n",
    "#             dict = collections.defaultdict(int)\n",
    "#             for i in nums:\n",
    "#                 dict[i] += 1\n",
    "#             ans = 0\n",
    "#             for value in dict.values():\n",
    "#                 if value > 1:\n",
    "#                     ans += 1\n",
    "#             return ans\n",
    "#         nums = set(nums)\n",
    "#         ans = 0\n",
    "#         for item in nums:\n",
    "#             if item+k in nums:\n",
    "#                 ans += 1\n",
    "#         return ans"
   ]
  },
  {
   "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}