top_k_frequent_number_in_a_list.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Top k frequent numbers in a list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's suppose you are rolling a 6 sided dice and put the result in a list.  \n",
    "ex) [3,2,3,1,2,5,3,6,2,4] is the results when you rolled dice 10 times.  \n",
    "\n",
    "if k=2, we want top 2 frequent numbers in a list, since 3 and 2 are top 2 frequent numbers,  \n",
    "the return value for this example is [2,3].\n",
    "\n",
    "when result has same frequent numbers in top k  \n",
    "such as [1,1,1,2,2,3,3,4,4] when k=3, you can return any same frequent number.  \n",
    "ex) k=3, return can be [1,2,3] or [1,2,4]\n",
    "\n",
    "return list must have item from top frequent number to lower frequent number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def top_k_frequent_number(nums,k):\n",
    "    num_map = {1:0, 2:0,3:0,4:0,5:0,6:0}\n",
    "\n",
    "    for num in nums:\n",
    "        num_map[num] += 1\n",
    "\n",
    "    ret = []\n",
    "    while k > 0:\n",
    "        max_freq = 0\n",
    "        max_key = 0\n",
    "        for key in num_map:\n",
    "            if num_map[key] > max_freq:\n",
    "                max_freq = num_map[key]\n",
    "                max_key = key\n",
    "        ret.append(max_key)\n",
    "        del num_map[max_key]\n",
    "        k -= 1\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 3]\n"
     ]
    }
   ],
   "source": [
    "print(top_k_frequent_number([3,2,3,1,2,5,3,6,2,4],2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3]\n"
     ]
    }
   ],
   "source": [
    "print(top_k_frequent_number([1,1,1,2,2,3,3,4,4],3))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Time Complexity:  O(n + 6k)  = O(n)\n",
    "O(n) from creating dictionary  \n",
    "O(6k) from finding top k frequent number, while k is less than or equal to 6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Space Complexity:  O(6+k+2)\n",
    "6 from creating dictionary, k from returning list, 2 from max_freq, max_key "
   ]
  }
 ],
 "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}