code/leetcode/blind_75.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 217. Contains Duplicate\n",
    "\n",
    "Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: nums = [1,2,3,1]\n",
    "Output: true\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: nums = [1,2,3,4]\n",
    "Output: false\n",
    "\n",
    "Example 3:\n",
    "\n",
    "Input: nums = [1,1,1,3,3,4,3,2,4,2]\n",
    "Output: true\n",
    "\n",
    "Constraints:\n",
    "\n",
    "    1 <= nums.length <= 105\n",
    "    -109 <= nums[i] <= 109\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        return not (len(set(nums)) == len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class SolutionNeetCode:\n",
    "    def containsDuplicate(self, nums: List[int]) -> bool:\n",
    "        hashset = set()\n",
    "\n",
    "        for n in nums:\n",
    "            if n in hashset:\n",
    "                return True\n",
    "            hashset.add(n)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1, 2, 3, 1]\n",
    "\n",
    "not (len(set(nums)) == len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [1, 2, 3, 1]\n",
    "\n",
    "Solution().containsDuplicate(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 242. Valid Anagram\n",
    "\n",
    "Given two strings s and t, return true if t is an anagram of s, and false otherwise.\n",
    "\n",
    "An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: s = \"anagram\", t = \"nagaram\"\n",
    "Output: true\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: s = \"rat\", t = \"car\"\n",
    "Output: false\n",
    "\n",
    "Constraints:\n",
    "\n",
    "    1 <= s.length, t.length <= 5 * 104\n",
    "    s and t consist of lowercase English letters.\n",
    "\n",
    "Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = \"anagram\"\n",
    "t = \"nagaramdsafhjsadlfhj\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'a': 3, 'n': 1, 'g': 1, 'r': 1, 'm': 1}\n",
      "{'n': 1, 'a': 3, 'g': 1, 'r': 1, 'm': 1}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import zip_longest\n",
    "\n",
    "s = \"anagram\"\n",
    "t = \"nagaram\"\n",
    "\n",
    "s_dict = dict()\n",
    "t_dict = dict()\n",
    "\n",
    "for s_char, t_char in zip_longest(s, t):\n",
    "    s_dict[s_char] = s_dict.get(s_char, 0) + 1\n",
    "    t_dict[t_char] = t_dict.get(t_char, 0) + 1\n",
    "\n",
    "print(s_dict)\n",
    "print(t_dict)\n",
    "\n",
    "s_dict == t_dict"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n"
     ]
    }
   ],
   "source": [
    "print(s_dict.get(None))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'nagaramdsafhjsadlfhj'"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Two Sum\n",
    "\n",
    "Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.\n",
    "\n",
    "You may assume that each input would have exactly one solution, and you may not use the same element twice.\n",
    "\n",
    "You can return the answer in any order.\n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: nums = [2,7,11,15], target = 9\n",
    "Output: [0,1]\n",
    "Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: nums = [3,2,4], target = 6\n",
    "Output: [1,2]\n",
    "\n",
    "Example 3:\n",
    "\n",
    "Input: nums = [3,3], target = 6\n",
    "Output: [0,1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        prevMap = {}  # val -> index\n",
    "\n",
    "        for i, n in enumerate(nums):\n",
    "            diff = target - n\n",
    "            if diff in prevMap:\n",
    "                return [prevMap[diff], i]\n",
    "            prevMap[n] = i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1]"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nums = [2, 7, 11, 5]\n",
    "\n",
    "target = 9\n",
    "\n",
    "Solution().twoSum(nums, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{3: 0, 2: 1, 4: 2}\n",
      "[1, 2]\n"
     ]
    }
   ],
   "source": [
    "nums_2 = [3, 2, 4]\n",
    "target_2 = 6\n",
    "\n",
    "data = {k: v for v, k in enumerate(nums_2)}\n",
    "print(data)\n",
    "\n",
    "\n",
    "def find_two_sum(data, target):\n",
    "    for key, current_index in data.items():\n",
    "        difference = target - key\n",
    "        try:\n",
    "            found_index = data[difference]\n",
    "            if found_index == current_index:\n",
    "                # no match found -- continue looking\n",
    "                continue\n",
    "            return [current_index, found_index]\n",
    "        except KeyError:\n",
    "            # i guess uncessary because we have been told that a solution is guaranteed. \n",
    "            print(\"no index found\")\n",
    "        except Exception as e:\n",
    "            print(\"some other error\")\n",
    "\n",
    "\n",
    "print(find_two_sum(data, target_2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 49. Group Anagrams\n",
    "\n",
    "Given an array of strings strs, group the anagrams together. You can return the answer in any order.\n",
    "\n",
    "An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: strs = [\"eat\",\"tea\",\"tan\",\"ate\",\"nat\",\"bat\"]\n",
    "Output: [[\"bat\"],[\"nat\",\"tan\"],[\"ate\",\"eat\",\"tea\"]]\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: strs = [\"\"]\n",
    "Output: [[\"\"]]\n",
    "\n",
    "Example 3:\n",
    "\n",
    "Input: strs = [\"a\"]\n",
    "Output: [[\"a\"]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['eat'], ['tea'], ['tan'], ['ate'], ['nat'], ['bat']]"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "strs = [\"eat\",\"tea\",\"tan\",\"ate\",\"nat\",\"bat\"]\n",
    "\n",
    "output = []\n",
    "for word in strs:\n",
    "    # check if anagram in output and if so append to that array \n",
    "    for \n",
    "    # can't think of how to do this without doing another double for loop! \n",
    "\n",
    "    # if no anagram found then append\n",
    "    output.append([word])\n",
    "\n",
    "# [\"eat\"] in output\n",
    "output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:\n",
    "        ans = defaultdict(list)\n",
    "\n",
    "        for s in strs:\n",
    "            count = [0] * 26\n",
    "            for c in s:\n",
    "                count[ord(c) - ord(\"a\")] += 1\n",
    "            # this maps the characters to values to check for anagram \n",
    "            ans[tuple(count)].append(s)\n",
    "        return ans.values()\n",
    "\n",
    "Solution().groupAnagrams(strs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 347. Top K Frequent Elements\n",
    "\n",
    "Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: nums = [1,1,1,2,2,3], k = 2\n",
    "Output: [1,2]\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: nums = [1], k = 1\n",
    "Output: [1]\n",
    "\n",
    " \n",
    "\n",
    "Constraints:\n",
    "\n",
    "    1 <= nums.length <= 105\n",
    "    -104 <= nums[i] <= 104\n",
    "    k is in the range [1, the number of unique elements in the array].\n",
    "    It is guaranteed that the answer is unique.\n",
    "\n",
    " \n",
    "\n",
    "Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [],
   "source": [
    "nums = [1,1,1,2,2,3] \n",
    "k = 2\n",
    "\n",
    "from collections import OrderedDict\n",
    "\n",
    "# foo = OrderedDict()\n",
    "foo = {}\n",
    "\n",
    "for number in nums:\n",
    "    foo[number] = foo.get(number, 0) + 1\n",
    "\n",
    "# neetcode says using a heap and popping off the top k elements would be k log(n) time too \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: 3, 2: 2, 3: 1}"
      ]
     },
     "execution_count": 81,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "foo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 238. Product of Array Except Self\n",
    "\n",
    "Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].\n",
    "\n",
    "The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.\n",
    "\n",
    "You must write an algorithm that runs in O(n) time and without using the division operation.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "Input: nums = [1,2,3,4]\n",
    "Output: [24,12,8,6]\n",
    "\n",
    "Example 2:\n",
    "\n",
    "Input: nums = [-1,1,0,-3,3]\n",
    "Output: [0,0,9,0,0]\n",
    "\n",
    " \n",
    "\n",
    "Constraints:\n",
    "\n",
    "    2 <= nums.length <= 105\n",
    "    -30 <= nums[i] <= 30\n",
    "    The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.\n",
    "\n",
    " \n",
    "\n",
    "Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "None\n",
      "None\n",
      "None\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[24, 12, 8, 6]"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math \n",
    "\n",
    "nums = [1,2,3,4]\n",
    "output = [24,12,8,6]\n",
    "\n",
    "math.prod(nums) \n",
    "\n",
    "output_2 = []\n",
    "for value in nums: \n",
    "    print(output_2.append(int(math.prod(nums) * (1.0/value))))\n",
    "\n",
    "output_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 3, 4]"
      ]
     },
     "execution_count": 93,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# could concatenate arrays like this and then add them up? \n",
    "nums[0:1] + nums[2:]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MLE Flashcards problem \n",
    "\n",
    "Solve fib(n) using dynamic programming of memoization and tabulation\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The 5-th Fibonacci number is: 5\n"
     ]
    }
   ],
   "source": [
    "# def fib_memoized(n, memo={}):\n",
    "#     if n == 0 or n == 1:\n",
    "#         return n \n",
    "    \n",
    "#     if n not in memo:\n",
    "#         memo[n] = fib_memoized(n-1, memo) + fib_memoized(n-2, memo)\n",
    "\n",
    "#     return memo\n",
    "    \n",
    "# # memoization = {}\n",
    "# fib_memoized(22)\n",
    "# memoization\n",
    "\n",
    "# this shit is crazyyyy ! \n",
    "def fib_n(n, memo={}):\n",
    "    # Check if the result is already memoized\n",
    "    if n in memo:\n",
    "        return memo[n]\n",
    "    \n",
    "    # Base cases\n",
    "    if n == 0:\n",
    "        result = 0\n",
    "    elif n == 1:\n",
    "        result = 1\n",
    "    else:\n",
    "        # Recursive calls with memoization\n",
    "        result = fib_n(n - 1, memo) + fib_n(n - 2, memo)\n",
    "    \n",
    "    # Memoize the result before returning\n",
    "    memo[n] = result\n",
    "    return result\n",
    "\n",
    "# # Example usage\n",
    "n = 5\n",
    "result = fib_n(n)\n",
    "print(f\"The {n}-th Fibonacci number is: {result}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The 5-th Fibonacci number is: 5\n"
     ]
    }
   ],
   "source": [
    "def fib_n(n):\n",
    "    # Base cases\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    elif n == 1:\n",
    "        return 1\n",
    "    \n",
    "    # Create a table to store Fibonacci numbers\n",
    "    fib_table = [0] * (n + 1)\n",
    "    \n",
    "    # Initialize the base cases\n",
    "    fib_table[0] = 0\n",
    "    fib_table[1] = 1\n",
    "    \n",
    "    # Fill in the table using bottom-up approach\n",
    "    for i in range(2, n + 1):\n",
    "        fib_table[i] = fib_table[i - 1] + fib_table[i - 2]\n",
    "    \n",
    "    # The result is the value at index n\n",
    "    return fib_table[n]\n",
    "\n",
    "# Example usage\n",
    "n = 5\n",
    "result = fib_n(n)\n",
    "print(f\"The {n}-th Fibonacci number is: {result}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "13 is a prime number.\n"
     ]
    }
   ],
   "source": [
    "def is_prime(n):\n",
    "    if n <= 1:\n",
    "        return False\n",
    "    elif n == 2:\n",
    "        return True\n",
    "    elif n % 2 == 0:\n",
    "        return False\n",
    "    else:\n",
    "        # Check for factors up to the square root of n\n",
    "        for i in range(3, int(n**0.5) + 1, 2):\n",
    "            if n % i == 0:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "# Example usage\n",
    "number = 13\n",
    "if is_prime(number):\n",
    "    print(f\"{number} is a prime number.\")\n",
    "else:\n",
    "    print(f\"{number} is not a prime number.\")\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "pytorch_m1",
   "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.8.13"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}