Leetcode Problem 1086 - High Five.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Problem Statement.\n",
    "\n",
    "Given a list of the scores of different students, items, where items[i] = [IDi, scorei] represents one score from a student with IDi, calculate each student's top five average.\n",
    "\n",
    "Return the answer as an array of pairs result, where result[j] = [IDj, topFiveAveragej] represents the student with IDj and their top five average. Sort result by IDj in increasing order.\n",
    "\n",
    "A student's top five average is calculated by taking the sum of their top five scores and dividing it by 5 using integer division.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: items = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]\n",
    "Output: [[1,87],[2,88]]\n",
    "Explanation: \n",
    "The student with ID = 1 got scores 91, 92, 60, 65, 87, and 100. Their top five average is (100 + 92 + 91 + 87 + 65) / 5 = 87.\n",
    "The student with ID = 2 got scores 93, 97, 77, 100, and 76. Their top five average is (100 + 97 + 93 + 77 + 76) / 5 = 88.6, but with integer division their average converts to 88.\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]\n",
    "Output: [[1,100],[7,100]]\n",
    "\n",
    " \n",
    "\n",
    "Constraints:\n",
    "\n",
    "    1 <= items.length <= 1000\n",
    "    items[i].length == 2\n",
    "    1 <= IDi <= 1000\n",
    "    0 <= scorei <= 100\n",
    "    For each IDi, there will be at least five scores."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sort - O(N Log N) runtime, O(N) space"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        items = sorted(items, key=lambda x: [x[0], -x[1]])\n",
    "        \n",
    "        result = []\n",
    "        currId = items[0][0]\n",
    "        currScore = 0\n",
    "        currCount = 0\n",
    "        \n",
    "        i, n = 0, len(items)\n",
    "        while i < n:\n",
    "            while i < n and items[i][0] == currId: \n",
    "                currCount += 1\n",
    "                if currCount <= 5: currScore += items[i][1]\n",
    "                i += 1\n",
    "            result.append([currId, currScore // min(currCount, 5)])\n",
    "            \n",
    "            if i < n:    \n",
    "                currId = items[i][0]\n",
    "                currScore = 0\n",
    "                currCount = 0\n",
    "                \n",
    "        return result  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hash table and K Heaps - O(N + K * Log K) runtime, O(K) space"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "from collections import defaultdict\n",
    "from heapq import heappush, heappop\n",
    "\n",
    "class Solution:\n",
    "    def highFive(self, items: List[List[int]]) -> List[List[int]]:\n",
    "        minheaps = defaultdict(list)\n",
    "        \n",
    "        for _id, score in items:\n",
    "            heappush(minheaps[_id], score)\n",
    "            if len(minheaps[_id]) > 5: \n",
    "                heappop(minheaps[_id])\n",
    "                \n",
    "        return [[_id, sum(minheaps[_id]) // len(minheaps[_id])] for _id in sorted(minheaps.keys())] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 87], [2, 88]]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "instance = Solution()\n",
    "instance.highFive( [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]])"
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}