{ "cells": [ { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 0]" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "from typing import List\n", "# best solution according to LEETCODE\n", "class Solution:\n", " def twoSum(self, nums: List[int], target: int) -> List[int]:\n", " hashmap = {}\n", " for i in range(len(nums)):\n", " complement = target - nums[i]\n", " if complement in hashmap:\n", " return [i, hashmap[complement]]\n", " hashmap[nums[i]] = i\n", " \n", "Solution().twoSum(case_1, 9)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 0]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "case_1 = [2,7,11,15]\n", "\n", "Solution().twoSum(case_1, 9)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0, 1]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Solution:\n", " def twoSum(self, nums: List[int], target: int) -> List[int]:\n", " for i in range(len(nums)):\n", " for j in range(i + 1, len(nums)):\n", " if nums[j] == target - nums[i]:\n", " return [i, j]\n", "\n", "\n", "Solution().twoSum(case_1, 9)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[2, 7, 11, 15]\n", "7\n", "2\n" ] }, { "data": { "text/plain": [ "[0, 1]" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Solution:\n", " def twoSum(self, nums, target):\n", " \"\"\"\n", " :type nums: List[int]\n", " :type target: int\n", " :rtype: List[int]\n", " \"\"\"\n", " print(nums)\n", " hashmap = {}\n", " for i, num in enumerate(nums):\n", " n = target - num\n", " print(n)\n", " if n not in hashmap:\n", " hashmap[num] = i\n", " else:\n", " return [hashmap[n], i]\n", "\n", "Solution().twoSum(case_1, 9)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " 1\n", " 1 1\n", " 1 2 1\n", " 1 3 3 1\n", " 1 4 6 4 1\n", " 1 6 1 0 5 1\n" ] } ], "source": [ "# Print Pascal's Triangle in Python\n", "\n", "# input n\n", "n = 6\n", "\n", "# iterarte upto n\n", "for i in range(n):\n", "\t# adjust space\n", "\tprint(' '*(n-i), end='')\n", "\n", "\t# compute power of 11\n", "\tprint(' '.join(map(str, str(11**i))))\n" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1, 5, 10, 10, 5, 1" ] } ], "source": [ "# Python3 program to implement the above approach\n", "\n", "# Print the N-th row of the\n", "# Pascal's Triangle\n", "def generateNthRow (N):\n", "\n", "\t# nC0 = 1\n", "\tprev = 1\n", "\tprint(prev, end = '')\n", "\n", "\tfor i in range(1, N + 1):\n", "\n", "\t\t# nCr = (nCr-1 * (n - r + 1))/r\n", "\t\tcurr = (prev * (N - i + 1)) // i\n", "\t\tprint(\",\", curr, end = '')\n", "\t\tprev = curr\n", "\n", "# Driver code\n", "N = 5\n", "\n", "# Function calling\n", "generateNthRow(N)\n", "\n", "# This code is contributed by himanshu77\n" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "22" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "\"foo\".__hash__()\n", "\n", "bar = 22.0\n", "\n", "bar.__hash__()" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[][][][][][][][][][][][][][][][][][][][][][][][][][('gfg@example.com', 'some value')][][][][][][][][][][][][][][][][][][][][][][][][]\n", "\n", "[][][][][][][][][][][][][][][][][][('portal@example.com', 'some other value')][][][][][][][][('gfg@example.com', 'some value')][][][][][][][][][][][][][][][][][][][][][][][][]\n", "\n", "some other value\n", "\n", "[][][][][][][][][][][][][][][][][][][][][][][][][][('gfg@example.com', 'some value')][][][][][][][][][][][][][][][][][][][][][][][][]\n" ] } ], "source": [ "class HashTable:\n", "\n", "\t# Create empty bucket list of given size\n", "\tdef __init__(self, size):\n", "\t\tself.size = size\n", "\t\tself.hash_table = self.create_buckets()\n", "\n", "\tdef create_buckets(self):\n", "\t\treturn [[] for _ in range(self.size)]\n", "\n", "\t# Insert values into hash map\n", "\tdef set_val(self, key, val):\n", "\t\t\n", "\t\t# Get the index from the key\n", "\t\t# using hash function\n", "\t\thashed_key = hash(key) % self.size\n", "\t\t\n", "\t\t# Get the bucket corresponding to index\n", "\t\tbucket = self.hash_table[hashed_key]\n", "\n", "\t\tfound_key = False\n", "\t\tfor index, record in enumerate(bucket):\n", "\t\t\trecord_key, record_val = record\n", "\t\t\t\n", "\t\t\t# check if the bucket has same key as\n", "\t\t\t# the key to be inserted\n", "\t\t\tif record_key == key:\n", "\t\t\t\tfound_key = True\n", "\t\t\t\tbreak\n", "\n", "\t\t# If the bucket has same key as the key to be inserted,\n", "\t\t# Update the key value\n", "\t\t# Otherwise append the new key-value pair to the bucket\n", "\t\tif found_key:\n", "\t\t\tbucket[index] = (key, val)\n", "\t\telse:\n", "\t\t\tbucket.append((key, val))\n", "\n", "\t# Return searched value with specific key\n", "\tdef get_val(self, key):\n", "\t\t\n", "\t\t# Get the index from the key using\n", "\t\t# hash function\n", "\t\thashed_key = hash(key) % self.size\n", "\t\t\n", "\t\t# Get the bucket corresponding to index\n", "\t\tbucket = self.hash_table[hashed_key]\n", "\n", "\t\tfound_key = False\n", "\t\tfor index, record in enumerate(bucket):\n", "\t\t\trecord_key, record_val = record\n", "\t\t\t\n", "\t\t\t# check if the bucket has same key as\n", "\t\t\t# the key being searched\n", "\t\t\tif record_key == key:\n", "\t\t\t\tfound_key = True\n", "\t\t\t\tbreak\n", "\n", "\t\t# If the bucket has same key as the key being searched,\n", "\t\t# Return the value found\n", "\t\t# Otherwise indicate there was no record found\n", "\t\tif found_key:\n", "\t\t\treturn record_val\n", "\t\telse:\n", "\t\t\treturn \"No record found\"\n", "\n", "\t# Remove a value with specific key\n", "\tdef delete_val(self, key):\n", "\t\t\n", "\t\t# Get the index from the key using\n", "\t\t# hash function\n", "\t\thashed_key = hash(key) % self.size\n", "\t\t\n", "\t\t# Get the bucket corresponding to index\n", "\t\tbucket = self.hash_table[hashed_key]\n", "\n", "\t\tfound_key = False\n", "\t\tfor index, record in enumerate(bucket):\n", "\t\t\trecord_key, record_val = record\n", "\t\t\t\n", "\t\t\t# check if the bucket has same key as\n", "\t\t\t# the key to be deleted\n", "\t\t\tif record_key == key:\n", "\t\t\t\tfound_key = True\n", "\t\t\t\tbreak\n", "\t\tif found_key:\n", "\t\t\tbucket.pop(index)\n", "\t\treturn\n", "\n", "\t# To print the items of hash map\n", "\tdef __str__(self):\n", "\t\treturn \"\".join(str(item) for item in self.hash_table)\n", "\n", "\n", "hash_table = HashTable(50)\n", "\n", "# insert some values\n", "hash_table.set_val('gfg@example.com', 'some value')\n", "print(hash_table)\n", "print()\n", "\n", "hash_table.set_val('portal@example.com', 'some other value')\n", "print(hash_table)\n", "print()\n", "\n", "# search/access a record with key\n", "print(hash_table.get_val('portal@example.com'))\n", "print()\n", "\n", "# delete or remove a value\n", "hash_table.delete_val('portal@example.com')\n", "print(hash_table)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Longest Substring Without Repeating Characters (medium) -- blind 75 \n", "\n", "Given a string s, find the length of the longest\n", "substring\n", "without repeating characters.\n", "\n", "Input: s = \"abcabcbb\"\n", "Output: 3\n", "Explanation: The answer is \"abc\", with the length of 3." ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Solution:\n", " def lengthOfLongestSubstring(self, s: str) -> int:\n", " def check(start, end):\n", " chars = set()\n", " for i in range(start, end + 1):\n", " c = s[i]\n", " if c in chars:\n", " return False\n", " chars.add(c)\n", " return True\n", "\n", " n = len(s)\n", "\n", " res = 0\n", " for i in range(n):\n", " for j in range(i, n):\n", " if check(i, j):\n", " res = max(res, j - i + 1)\n", " return res\n", "\n", "s = \"abcabcbb\"\n", "\n", "Solution().lengthOfLongestSubstring(s)" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Solution:\n", " def lengthOfLongestSubstring(self, s: str) -> int:\n", " n = len(s)\n", " ans = 0\n", " # mp stores the current index of a character\n", " mp = {}\n", "\n", " i = 0\n", " # try to extend the range [i, j]\n", " for j in range(n):\n", " if s[j] in mp:\n", " i = max(mp[s[j]], i)\n", "\n", " ans = max(ans, j - i + 1)\n", " mp[s[j]] = j + 1\n", "\n", " return ans\n", "\n", "s = \"abcabcbb\"\n", "\n", "Solution().lengthOfLongestSubstring(s)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 5. Longest Palindromic Substring\n", "\n", "Given a string s, return the longest palindromic substring in s.\n", "\n", "Input: s = \"babad\"\n", "Output: \"bab\"\n", "Explanation: \"aba\" is also a valid answer." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class Solution:\n", " def longestPalindrome(self, s: str) -> str:\n", " m = '' # Memory to remember a palindrome\n", " for i in range(len(s)): # i = start, O = n\n", " for j in range(len(s), i, -1): # j = end, O = n^2\n", " if len(m) >= j-i: # To reduce time\n", " break\n", " elif s[i:j] == s[i:j][::-1]:\n", " m = s[i:j]\n", " break\n", " return m" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 11. Container With Most Water \n", "\n", "You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).\n", "\n", "Find two lines that together with the x-axis form a container, such that the container contains the most water.\n", "\n", "Return the maximum amount of water a container can store.\n", "\n", "Notice that you may not slant the container.\n" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "49" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Solution:\n", " def maxArea(self, height: List[int]) -> int:\n", " maxarea = 0\n", " left = 0\n", " right = len(height) - 1\n", " \n", " while left < right:\n", " width = right - left\n", " maxarea = max(maxarea, min(height[left], height[right]) * width)\n", " if height[left] <= height[right]:\n", " left += 1\n", " else:\n", " right -= 1\n", " \n", " return maxarea\n", "\n", "height = [1,8,6,2,5,4,8,3,7]\n", "\n", "Solution().maxArea(height)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 15. 3Sum \n", "\n", "Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.\n", "\n", "Notice that the solution set must not contain duplicate triplets.\n" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(-1, -1, 2), (-1, 0, 1)]" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Solution:\n", " def threeSum(self, nums):\n", " res = []\n", " nums.sort()\n", " for i in range(len(nums)-2):\n", " if i > 0 and nums[i] == nums[i-1]:\n", " continue\n", " l, r = i+1, len(nums)-1\n", " while l < r:\n", " s = nums[i] + nums[l] + nums[r]\n", " if s < 0:\n", " l +=1 \n", " elif s > 0:\n", " r -= 1\n", " else:\n", " res.append((nums[i], nums[l], nums[r]))\n", " while l < r and nums[l] == nums[l+1]:\n", " l += 1\n", " while l < r and nums[r] == nums[r-1]:\n", " r -= 1\n", " l += 1; r -= 1\n", " return res\n", "\n", "nums = [-1,0,1,2,-1,-4]\n", "\n", "Solution().threeSum(nums)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 20. Valid Parenthesis \n", "\n", "Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.\n", "\n", "An input string is valid if:\n", "\n", " Open brackets must be closed by the same type of brackets.\n", " Open brackets must be closed in the correct order.\n", " Every close bracket has a corresponding open bracket of the same type.\n" ] }, { "cell_type": "code", "execution_count": 118, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 118, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Solution:\n", " # @return a boolean\n", " def isValid(self, s):\n", " stack = []\n", " dict = {\"]\":\"[\", \"}\":\"{\", \")\":\"(\"}\n", " for char in s:\n", " if char in dict.values():\n", " stack.append(char)\n", " elif char in dict.keys():\n", " if stack == [] or dict[char] != stack.pop():\n", " return False\n", " else:\n", " return False\n", " return stack == []\n", "\n", "\n", "s = \"()[]{}\"\n", "s = \"()[]{}\"\n", "Solution().isValid(s)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 21. Merge Two Sorted List \n", "\n", "You are given the heads of two sorted linked lists list1 and list2.\n", "\n", "Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.\n", "\n", "Return the head of the merged linked list." ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [], "source": [ "from typing import Optional\n", "\n", "class ListNode(object):\n", " def __init__(self, x):\n", " self.val = x\n", " self.next = None\n", "\n", "\n", "class Solution:\n", " def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:\n", " cur = dummy = ListNode()\n", " while list1 and list2: \n", " if list1.val < list2.val:\n", " cur.next = list1\n", " list1, cur = list1.next, list1\n", " else:\n", " cur.next = list2\n", " list2, cur = list2.next, list2\n", " \n", " if list1 or list2:\n", " cur.next = list1 if list1 else list2\n", " \n", " return dummy.next" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 23. Merge k Sorted Lists (hard)\n", "\n", "You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.\n", "\n", "Merge all the linked-lists into one sorted linked-list and return it.\n" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [], "source": [ "# brute force \n", "\n", "class Solution(object):\n", " def mergeKLists(self, lists):\n", " \"\"\"\n", " :type lists: List[ListNode]\n", " :rtype: ListNode\n", " \"\"\"\n", " self.nodes = []\n", " head = point = ListNode(0)\n", " for l in lists:\n", " while l:\n", " self.nodes.append(l.val)\n", " l = l.next\n", " for x in sorted(self.nodes):\n", " point.next = ListNode(x)\n", " point = point.next\n", " return head.next" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "ename": "ModuleNotFoundError", "evalue": "No module named 'Queue'", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mModuleNotFoundError\u001b[0m Traceback (most recent call last)", "Cell \u001b[0;32mIn[38], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m \u001b[39mfrom\u001b[39;00m \u001b[39mQueue\u001b[39;00m \u001b[39mimport\u001b[39;00m PriorityQueue\n\u001b[1;32m 3\u001b[0m \u001b[39mclass\u001b[39;00m \u001b[39mSolution\u001b[39;00m(\u001b[39mobject\u001b[39m):\n\u001b[1;32m 4\u001b[0m \u001b[39mdef\u001b[39;00m \u001b[39mmergeKLists\u001b[39m(\u001b[39mself\u001b[39m, lists):\n", "\u001b[0;31mModuleNotFoundError\u001b[0m: No module named 'Queue'" ] } ], "source": [ "from Queue import PriorityQueue\n", "\n", "class Solution(object):\n", " def mergeKLists(self, lists):\n", " \"\"\"\n", " :type lists: List[ListNode]\n", " :rtype: ListNode\n", " \"\"\"\n", " head = point = ListNode(0)\n", " q = PriorityQueue()\n", " for l in lists:\n", " if l:\n", " q.put((l.val, l))\n", " while not q.empty():\n", " val, node = q.get()\n", " point.next = ListNode(val)\n", " point = point.next\n", " node = node.next\n", " if node:\n", " q.put((node.val, node))\n", " return head.next\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 33. Search in Rotated Sorted Array (medium)\n", "\n", "There is an integer array nums sorted in ascending order (with distinct values).\n", "\n", "Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].\n", "\n", "Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.\n", "\n", "You must write an algorithm with O(log n) runtime complexity." ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4" ] }, "execution_count": 41, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Solution:\n", " def search(self, A: List[int], target: int) -> int:\n", " n = len(A)\n", " left, right = 0, n - 1\n", " if n == 0: return -1\n", " \n", " while left <= right:\n", " mid = left + (right - left) // 2\n", " if A[mid] == target: return mid\n", " \n", " # inflection point to the right. Left is strictly increasing\n", " if A[mid] >= A[left]:\n", " if A[left] <= target < A[mid]:\n", " right = mid - 1\n", " else:\n", " left = mid + 1\n", " \n", " # inflection point to the left of me. Right is strictly increasing\n", " else:\n", " if A[mid] < target <= A[right]:\n", " left = mid + 1\n", " else:\n", " right = mid - 1\n", " \n", " return -1\n", "\n", "A = [4,5,6,7,0,1,2]\n", "target = 0 \n", "\n", "# return index of pivot \n", "Solution().search(A, target)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 39. Combination Sum (medium)\n", "\n", "Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.\n", "\n", "The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the\n", "frequency\n", "of at least one of the chosen numbers is different.\n", "\n", "The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.\n" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[2, 2, 3], [7]]" ] }, "execution_count": 42, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Solution(object):\n", " def combinationSum(self, candidates, target):\n", " ret = []\n", " self.dfs(candidates, target, [], ret)\n", " return ret\n", " \n", " def dfs(self, nums, target, path, ret):\n", " if target < 0:\n", " return \n", " if target == 0:\n", " ret.append(path)\n", " return \n", " for i in range(len(nums)):\n", " self.dfs(nums[i:], target-nums[i], path+[nums[i]], ret)\n", "\n", "candidates = [2,3,6,7]\n", "targets = 7 \n", "\n", "Solution().combinationSum(candidates, targets)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 48. Rotate Image (medium)\n", "\n", "You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).\n", "\n", "You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.\n", "\n", "\n", "\n", "**Bonus Question:** If you're not too confident with matrices and linear algebra, get some more practice by also coding a method that transposes the matrix on the other diagonal, and another that reflects from top to bottom. You can test your functions by printing out the matrix before and after each operation. Finally, use your functions to find three more solutions to this problem. Each solution uses two matrix operations.\n", "\n", "\n", "**Interview Tip:** Terrified of being asked this question in an interview? Many people are: it can be intimidating due to the fiddly logic. Unfortunately, if you do a lot of interviewing, the probability of seeing it at least once is high, and some people have claimed to have seen it multiple times! This is one of the few questions where I recommend practicing until you can confidently code it and explain it without thinking too much.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "class Solution:\n", " def rotate(self, matrix: List[List[int]]) -> None:\n", " self.transpose(matrix)\n", " self.reflect(matrix)\n", " \n", " def transpose(self, matrix):\n", " n = len(matrix)\n", " for i in range(n):\n", " for j in range(i + 1, n):\n", " matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i]\n", "\n", " def reflect(self, matrix):\n", " n = len(matrix)\n", " for i in range(n):\n", " for j in range(n // 2):\n", " matrix[i][j], matrix[i][-j - 1] = matrix[i][-j - 1], matrix[i][j]\n", "\n", "matrix = [[1,2,3],[4,5,6],[7,8,9]]\n", "\n" ] }, { "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" ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])" ] }, "execution_count": 45, "metadata": {}, "output_type": "execute_result" } ], "source": [ "import collections\n", "\n", "class Solution:\n", " def groupAnagrams(self, strs):\n", " ans = collections.defaultdict(list)\n", " for s in strs:\n", " count = [0] * 26\n", " for c in s:\n", " count[ord(c) - ord('a')] += 1\n", " ans[tuple(count)].append(s)\n", " return ans.values()\n", "\n", "strs = [\"eat\",\"tea\",\"tan\",\"ate\",\"nat\",\"bat\"]\n", "\n", "Solution().groupAnagrams(strs)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 53. Maximum Subarray \n", "iven an integer array nums, find the\n", "subarray\n", "which has the largest sum and return its sum.\n", "\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# kadane algo \n", "for i in range(1, len(nums)):\n", " if nums[i-1] > 0:\n", " nums[i] += nums[i-1]\n", " return max(nums)\n", "\n", "\n", "from itertools import accumulate\n", "\n", "return max(accumulate(nums, lambda x, y: x+y if x > 0 else y))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# spiral matrix\n", "\n", "Given an m x n matrix, return all elements of the matrix in spiral order.\n", "\n", "matrix = [[1,2,3],[4,5,6],[7,8,9]]\n", "output [1,2,3,6,9,8,7,4,5]\n" ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [], "source": [ "class Solution:\n", " def spiralOrder(self, matrix: List[List[int]]) -> List[int]:\n", " res = []\n", " if len(matrix) == 0:\n", " return res\n", " row_begin = 0\n", " col_begin = 0\n", " row_end = len(matrix)-1 \n", " col_end = len(matrix[0])-1\n", " while (row_begin <= row_end and col_begin <= col_end):\n", " for i in range(col_begin,col_end+1):\n", " res.append(matrix[row_begin][i])\n", " row_begin += 1\n", " for i in range(row_begin,row_end+1):\n", " res.append(matrix[i][col_end])\n", " col_end -= 1\n", " if (row_begin <= row_end):\n", " for i in range(col_end,col_begin-1,-1):\n", " res.append(matrix[row_end][i])\n", " row_end -= 1\n", " if (col_begin <= col_end):\n", " for i in range(row_end,row_begin-1,-1):\n", " res.append(matrix[i][col_begin])\n", " col_begin += 1\n", " return res\n", " \n", " \n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Jump Game (medium) \n", "\n", "You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.\n", "\n", "Return true if you can reach the last index, or false otherwise." ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "execution_count": 50, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Solution:\n", " def canJump(self, nums: List[int]) -> bool:\n", " m = 0\n", " for i, n in enumerate(nums):\n", " if i > m:\n", " return False\n", " m = max(m, i+n)\n", " return True\n", "\n", "nums = [2,3,1,1,4]\n", "\n", "nums = [3,2,1,0,4]\n", "\n", "Solution().canJump(nums)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 56. Merge Intervals\n", "\n", "Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.\n" ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[1, 6], [8, 10], [15, 18]]" ] }, "execution_count": 54, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# time complexity analysis O(n log n )\n", "class Solution:\n", " def merge(self, intervals: List[List[int]]) -> List[List[int]]:\n", "\n", " intervals.sort(key=lambda x: x[0])\n", "\n", " merged = []\n", " for interval in intervals:\n", " # if the list of merged intervals is empty or if the current\n", " # interval does not overlap with the previous, simply append it.\n", " if not merged or merged[-1][1] < interval[0]:\n", " merged.append(interval)\n", " else:\n", " # otherwise, there is overlap, so we merge the current and previous\n", " # intervals.\n", " merged[-1][1] = max(merged[-1][1], interval[1])\n", "\n", " return merged\n", "\n", "intervals = [[1,3],[2,6],[8,10],[15,18]]\n", "\n", "Solution().merge(intervals)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 57. Insert Interval\n", "\n", "You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.\n", "\n", "Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).\n", "\n", "Return intervals after the insertion." ] }, { "cell_type": "code", "execution_count": 59, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[[1, 5], [6, 9]]" ] }, "execution_count": 59, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# class Solution:\n", "# def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n", "# # s, e = newInterval.start, newInterval.end\n", "# s, e = newInterval[0], newInterval[1]\n", "# left = [i for i in intervals if i.end < s]\n", "# right = [i for i in intervals if i.start > e]\n", "# if left + right != intervals:\n", "# s = min(s, intervals[len(left)].start)\n", "# e = max(e, intervals[~len(right)].end)\n", "# return left + [Interval(s, e)] + right\n", "\n", "\n", "class Solution:\n", " def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n", " s, e = newInterval[0], newInterval[1]\n", " left, right = [], []\n", " for i in intervals:\n", " if i[1] < s:\n", " left += i,\n", " elif i[0] > e:\n", " right += i,\n", " else:\n", " s = min(s, i[0])\n", " e = max(e, i[1])\n", " return left + [[s, e]] + right\n", "\n", "intervals = [[1,3],[6,9]]\n", "newInterval = [2,5]\n", "\n", "Solution().insert(intervals, newInterval)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 70. Climbing Stairs\n", "\n", "You are climbing a staircase. It takes n steps to reach the top.\n", "\n", "Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?" ] }, { "cell_type": "code", "execution_count": 60, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 60, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Solution:\n", " def climbStairs(self, n: int) -> int:\n", " a = b = 1\n", " for _ in range(n):\n", " a, b = b, a + b\n", " return a\n", "\n", "n = 2\n", "Solution().climbStairs(n)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 73. Set Matrix Zeros \n", "\n", "Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.\n", "\n", "You must do it in place." ] }, { "cell_type": "code", "execution_count": 63, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[1, 0, 1], [0, 0, 0], [1, 0, 1]]\n" ] } ], "source": [ "class Solution(object):\n", " def setZeroes(self, matrix):\n", " \"\"\"\n", " :type matrix: List[List[int]]\n", " :rtype: void Do not return anything, modify matrix in-place instead.\n", " \"\"\"\n", " is_col = False\n", " R = len(matrix)\n", " C = len(matrix[0])\n", " for i in range(R):\n", " # Since first cell for both first row and first column is the same i.e. matrix[0][0]\n", " # We can use an additional variable for either the first row/column.\n", " # For this solution we are using an additional variable for the first column\n", " # and using matrix[0][0] for the first row.\n", " if matrix[i][0] == 0:\n", " is_col = True\n", " for j in range(1, C):\n", " # If an element is zero, we set the first element of the corresponding row and column to 0\n", " if matrix[i][j] == 0:\n", " matrix[0][j] = 0\n", " matrix[i][0] = 0\n", "\n", " # Iterate over the array once again and using the first row and first column, update the elements.\n", " for i in range(1, R):\n", " for j in range(1, C):\n", " if not matrix[i][0] or not matrix[0][j]:\n", " matrix[i][j] = 0\n", "\n", " # See if the first row needs to be set to zero as well\n", " if matrix[0][0] == 0:\n", " for j in range(C):\n", " matrix[0][j] = 0\n", "\n", " # See if the first column needs to be set to zero as well \n", " if is_col:\n", " for i in range(R):\n", " matrix[i][0] = 0\n", "\n", "matrix = [[1,1,1],[1,0,1],[1,1,1]]\n", "\n", "Solution().setZeroes(matrix)\n", "print(matrix)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 76. Minimum Window Substring (hard)\n", "\n", "Given two strings s and t of lengths m and n respectively, return the minimum window\n", "substring\n", "of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string \"\".\n", "\n", "The testcases will be generated such that the answer is unique.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# solution from leetcode \n", "\n", "def minWindow(self, s, t):\n", " \"\"\"\n", " :type s: str\n", " :type t: str\n", " :rtype: str\n", " \"\"\"\n", "\n", " if not t or not s:\n", " return \"\"\n", "\n", " # Dictionary which keeps a count of all the unique characters in t.\n", " dict_t = Counter(t)\n", "\n", " # Number of unique characters in t, which need to be present in the desired window.\n", " required = len(dict_t)\n", "\n", " # left and right pointer\n", " l, r = 0, 0\n", "\n", " # formed is used to keep track of how many unique characters in t are present in the current window in its desired frequency.\n", " # e.g. if t is \"AABC\" then the window must have two A's, one B and one C. Thus formed would be = 3 when all these conditions are met.\n", " formed = 0\n", "\n", " # Dictionary which keeps a count of all the unique characters in the current window.\n", " window_counts = {}\n", "\n", " # ans tuple of the form (window length, left, right)\n", " ans = float(\"inf\"), None, None\n", "\n", " while r < len(s):\n", "\n", " # Add one character from the right to the window\n", " character = s[r]\n", " window_counts[character] = window_counts.get(character, 0) + 1\n", "\n", " # If the frequency of the current character added equals to the desired count in t then increment the formed count by 1.\n", " if character in dict_t and window_counts[character] == dict_t[character]:\n", " formed += 1\n", "\n", " # Try and contract the window till the point where it ceases to be 'desirable'.\n", " while l <= r and formed == required:\n", " character = s[l]\n", "\n", " # Save the smallest window until now.\n", " if r - l + 1 < ans[0]:\n", " ans = (r - l + 1, l, r)\n", "\n", " # The character at the position pointed by the `left` pointer is no longer a part of the window.\n", " window_counts[character] -= 1\n", " if character in dict_t and window_counts[character] < dict_t[character]:\n", " formed -= 1\n", "\n", " # Move the left pointer ahead, this would help to look for a new window.\n", " l += 1 \n", "\n", " # Keep expanding the window once we are done contracting.\n", " r += 1 \n", " return \"\" if ans[0] == float(\"inf\") else s[ans[1] : ans[2] + 1]\n", "\n", "s = \"ADOBECODEBANC\", t = \"ABC\"" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# soltuion from comments \n", "\n", "class Solution:\n", " def minWindow(s, t):\n", " need = collections.Counter(t) #hash table to store char frequency\n", " missing = len(t) #total number of chars we care\n", " start, end = 0, 0\n", " i = 0\n", " for j, char in enumerate(s, 1): #index j from 1\n", " if need[char] > 0:\n", " missing -= 1\n", " need[char] -= 1\n", " if missing == 0: #match all chars\n", " while i < j and need[s[i]] < 0: #remove chars to find the real start\n", " need[s[i]] += 1\n", " i += 1\n", " need[s[i]] += 1 #make sure the first appearing char satisfies need[char]>0\n", " missing += 1 #we missed this first char, so add missing by 1\n", " if end == 0 or j-i < end-start: #update window\n", " start, end = i, j\n", " i += 1 #update i to start+1 for next window\n", " return s[start:end]\n", "\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 79. Word Search\n", "\n", "Given an m x n grid of characters board and a string word, return true if word exists in the grid.\n", "\n", "The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once." ] }, { "cell_type": "code", "execution_count": 64, "metadata": {}, "outputs": [], "source": [ "# depth first search \n", "\n", "\n", "def exist(self, board, word):\n", " if not board:\n", " return False\n", " for i in xrange(len(board)):\n", " for j in xrange(len(board[0])):\n", " if self.dfs(board, i, j, word):\n", " return True\n", " return False\n", "\n", "# check whether can find word, start at (i,j) position \n", "def dfs(self, board, i, j, word):\n", " if len(word) == 0: # all the characters are checked\n", " return True\n", " if i<0 or i>=len(board) or j<0 or j>=len(board[0]) or word[0]!=board[i][j]:\n", " return False\n", " tmp = board[i][j] # first character is found, check the remaining part\n", " board[i][j] = \"#\" # avoid visit agian \n", " # check whether can find \"word\" along one direction\n", " res = self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) \\\n", " or self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:])\n", " board[i][j] = tmp\n", " return res\n", "\n", "board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]]\n", "word = \"ABCCED\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 98. Validate Binary Search Tree\n", "\n", "Given the root of a binary tree, determine if it is a valid binary search tree (BST).\n", "\n", "A valid BST is defined as follows:\n", "\n", "The left\n", "subtree\n", "of a node contains only nodes with keys less than the node's key.\n", "The right subtree of a node contains only nodes with keys greater than the node's key.\n", "Both the left and right subtrees must also be binary search trees.\n" ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [ { "ename": "AttributeError", "evalue": "'list' object has no attribute 'val'", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mAttributeError\u001b[0m Traceback (most recent call last)", "Cell \u001b[0;32mIn[69], line 19\u001b[0m\n\u001b[1;32m 15\u001b[0m \u001b[39mreturn\u001b[39;00m \u001b[39mself\u001b[39m\u001b[39m.\u001b[39misValidBST(root\u001b[39m.\u001b[39mleft, floor, root\u001b[39m.\u001b[39mval) \u001b[39mand\u001b[39;00m \u001b[39mself\u001b[39m\u001b[39m.\u001b[39misValidBST(root\u001b[39m.\u001b[39mright, root\u001b[39m.\u001b[39mval, ceiling)\n\u001b[1;32m 17\u001b[0m root \u001b[39m=\u001b[39m [\u001b[39m2\u001b[39m,\u001b[39m1\u001b[39m,\u001b[39m3\u001b[39m]\n\u001b[0;32m---> 19\u001b[0m Solution()\u001b[39m.\u001b[39;49misValidBST(root)\n", "Cell \u001b[0;32mIn[69], line 12\u001b[0m, in \u001b[0;36mSolution.isValidBST\u001b[0;34m(self, root, floor, ceiling)\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[39mif\u001b[39;00m \u001b[39mnot\u001b[39;00m root: \n\u001b[1;32m 11\u001b[0m \u001b[39mreturn\u001b[39;00m \u001b[39mTrue\u001b[39;00m\n\u001b[0;32m---> 12\u001b[0m \u001b[39mif\u001b[39;00m root\u001b[39m.\u001b[39;49mval \u001b[39m<\u001b[39m\u001b[39m=\u001b[39m floor \u001b[39mor\u001b[39;00m root\u001b[39m.\u001b[39mval \u001b[39m>\u001b[39m\u001b[39m=\u001b[39m ceiling:\n\u001b[1;32m 13\u001b[0m \u001b[39mreturn\u001b[39;00m \u001b[39mFalse\u001b[39;00m\n\u001b[1;32m 14\u001b[0m \u001b[39m# in the left branch, root is the new ceiling; contrarily root is the new floor in right branch\u001b[39;00m\n", "\u001b[0;31mAttributeError\u001b[0m: 'list' object has no attribute 'val'" ] } ], "source": [ "# Definition for a binary tree node.\n", "# class TreeNode:\n", "# def __init__(self, val=0, left=None, right=None):\n", "# self.val = val\n", "# self.left = left\n", "# self.right = right\n", "\n", "class Solution:\n", " def isValidBST(self, root, floor=float('-inf'), ceiling=float('inf')):\n", " if not root: \n", " return True\n", " if root.val <= floor or root.val >= ceiling:\n", " return False\n", " # in the left branch, root is the new ceiling; contrarily root is the new floor in right branch\n", " return self.isValidBST(root.left, floor, root.val) and self.isValidBST(root.right, root.val, ceiling)\n", "\n", "root = [2,1,3]\n", "\n", "Solution().isValidBST(root)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 100. Same Tree\n", "\n", "Given the roots of two binary trees p and q, write a function to check if they are the same or not.\n", "\n", "Two binary trees are considered the same if they are structurally identical, and the nodes have the same value." ] }, { "cell_type": "code", "execution_count": 70, "metadata": {}, "outputs": [], "source": [ "from collections import deque\n", "class Solution:\n", " def isSameTree(self, p, q):\n", " \"\"\"\n", " :type p: TreeNode\n", " :type q: TreeNode\n", " :rtype: bool\n", " \"\"\" \n", " def check(p, q):\n", " # if both are None\n", " if not p and not q:\n", " return True\n", " # one of p and q is None\n", " if not q or not p:\n", " return False\n", " if p.val != q.val:\n", " return False\n", " return True\n", " \n", " deq = deque([(p, q),])\n", " while deq:\n", " p, q = deq.popleft()\n", " if not check(p, q):\n", " return False\n", " \n", " if p:\n", " deq.append((p.left, q.left))\n", " deq.append((p.right, q.right))\n", " \n", " return True\n", "\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 102. Binary Tree Level Order Traversal\n", "\n", "Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level)." ] }, { "cell_type": "code", "execution_count": 71, "metadata": {}, "outputs": [ { "ename": "NameError", "evalue": "name 'null' is not defined", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)", "Cell \u001b[0;32mIn[71], line 1\u001b[0m\n\u001b[0;32m----> 1\u001b[0m root \u001b[39m=\u001b[39m [\u001b[39m3\u001b[39m,\u001b[39m9\u001b[39m,\u001b[39m20\u001b[39m,null,null,\u001b[39m15\u001b[39m,\u001b[39m7\u001b[39m]\n", "\u001b[0;31mNameError\u001b[0m: name 'null' is not defined" ] } ], "source": [ "def levelOrder(self, root):\n", " ans, level = [], [root]\n", " while root and level:\n", " ans.append([node.val for node in level])\n", " LRpair = [(node.left, node.right) for node in level]\n", " level = [leaf for LR in LRpair for leaf in LR if leaf]\n", " return ans\n", "\n", "root = [3,9,20,null,null,15,7]" ] }, { "cell_type": "code", "execution_count": 72, "metadata": {}, "outputs": [], "source": [ "from collections import deque\n", "def levelOrder(self, root):\n", " # traverse in order level, keeping track of (row number, current node)\n", " queue = deque([(0, root)])\n", " # keep track of the nodes in each row\n", " d = {}\n", "\n", " while queue:\n", " row, node = queue.popleft()\n", " if node:\n", " d[row] = d.get(row, []) + [node.val]\n", " queue += (row+1, node.left), (row+1, node.right)\n", "\n", " # return a list of lists containing node values in increasing order with respect to the row number\n", " return [d[row] for row in sorted(d.keys())]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 104. Maximum Depth of Binary Tree\n", "\n", "Given the root of a binary tree, return its maximum depth.\n", "\n", "A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node." ] }, { "cell_type": "code", "execution_count": 76, "metadata": {}, "outputs": [ { "ename": "NameError", "evalue": "name 'null' is not defined", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)", "Cell \u001b[0;32mIn[76], line 17\u001b[0m\n\u001b[1;32m 12\u001b[0m \u001b[39mreturn\u001b[39;00m \u001b[39mmax\u001b[39m(dfs(root\u001b[39m.\u001b[39mleft, depth \u001b[39m+\u001b[39m \u001b[39m1\u001b[39m), dfs(root\u001b[39m.\u001b[39mright, depth \u001b[39m+\u001b[39m \u001b[39m1\u001b[39m))\n\u001b[1;32m 14\u001b[0m \u001b[39mreturn\u001b[39;00m dfs(root, \u001b[39m0\u001b[39m)\n\u001b[0;32m---> 17\u001b[0m root \u001b[39m=\u001b[39m [\u001b[39m3\u001b[39m,\u001b[39m9\u001b[39m,\u001b[39m20\u001b[39m,null,null,\u001b[39m15\u001b[39m,\u001b[39m7\u001b[39m]\n\u001b[1;32m 19\u001b[0m Solution()\u001b[39m.\u001b[39mmaxDepth(root)\n", "\u001b[0;31mNameError\u001b[0m: name 'null' is not defined" ] } ], "source": [ "# Definition for a binary tree node.\n", "\n", "# https://leetcode.com/problems/maximum-depth-of-binary-tree/solutions/1769367/python3-recursive-dfs-explained/?orderBy=most_votes\n", "class TreeNode:\n", " def __init__(self, val=0, left=None, right=None):\n", " self.val = val\n", " self.left = left\n", " self.right = right\n", "\n", "class Solution:\n", " def maxDepth(self, root: Optional[TreeNode]) -> int:\n", " def dfs(root, depth):\n", " if not root: return depth\n", " return max(dfs(root.left, depth + 1), dfs(root.right, depth + 1))\n", " \n", " return dfs(root, 0)\n", "\n", "\n", "root = [3,9,20,null,null,15,7]\n", "\n", "Solution().maxDepth(root)\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Here, \"Object references are passed by value.\"" ] }, { "cell_type": "code", "execution_count": 78, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0, 1]\n", "[0, 1]\n" ] } ], "source": [ "listA = [0]\n", "listB = listA\n", "listB.append(1)\n", "print (listA)\n", "print(listB)" ] }, { "cell_type": "code", "execution_count": 83, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0]\n", "[0, 1]\n", "[0]\n", "[0, 1]\n", "[0, 1]\n" ] } ], "source": [ "def reassign(list):\n", " print(list)\n", " list = [0, 1]\n", " print(list)\n", "\n", "def append(list):\n", " print(list)\n", " list.append(1)\n", " print(list)\n", "\n", "list = [0]\n", "reassign(list)\n", "append(list)\n", "\n", "print(list)" ] }, { "cell_type": "code", "execution_count": 85, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "some value\n" ] } ], "source": [ "def foo(x):\n", " print(x)\n", "\n", "bar = 'some value'\n", "foo(bar)" ] }, { "cell_type": "code", "execution_count": 88, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "another value\n", "some value\n" ] } ], "source": [ "def foo(x):\n", " x = 'another value'\n", " print (x)\n", "\n", "bar = 'some value'\n", "foo(bar)\n", "print(bar)" ] }, { "cell_type": "code", "execution_count": 93, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[0]\n", "[0, 1]\n", "[0, 1]\n" ] } ], "source": [ "def append_one(li):\n", " print(li)\n", " li.append(1)\n", " print(li)\n", " return li\n", "\n", "x = [0]\n", "x = append_one(x)\n", "print(x)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 105. Construct Binary Tree From Preorder and Inorder Traversal \n", "\n", "Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree." ] }, { "cell_type": "code", "execution_count": 102, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3\n" ] } ], "source": [ "class TreeNode:\n", " def __init__(self, val=0, left=None, right=None):\n", " self.val = val\n", " self.left = left\n", " self.right = right\n", "\n", "class Solution:\n", " def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:\n", "\n", " def array_to_tree(left, right):\n", " nonlocal preorder_index\n", " # if there are no elements to construct the tree\n", " if left > right: return None\n", "\n", " # select the preorder_index element as the root and increment it\n", " root_value = preorder[preorder_index]\n", " root = TreeNode(root_value)\n", "\n", "\n", " preorder_index += 1\n", "\n", " # build left and right subtree\n", " # excluding inorder_index_map[root_value] element because it's the root\n", " root.left = array_to_tree(left, inorder_index_map[root_value] - 1)\n", " root.right = array_to_tree(inorder_index_map[root_value] + 1, right)\n", "\n", " return root\n", "\n", " preorder_index = 0\n", "\n", " # build a hashmap to store value -> its index relations\n", " inorder_index_map = {}\n", " for index, value in enumerate(inorder):\n", " inorder_index_map[value] = index\n", "\n", " return array_to_tree(0, len(preorder) - 1)\n", "\n", "preorder = [3,9,20,15,7]\n", "inorder = [9,3,15,20,7]\n", "\n", "# preorder = [-1]\n", "# inorder = [-1]\n", "\n", "foo = Solution().buildTree(preorder, inorder)\n", "print(foo.val)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 121. Best Time to Buy and Sell Stock\n", "\n", "You are given an array prices where prices[i] is the price of a given stock on the ith day.\n", "\n", "You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.\n", "\n", "Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0." ] }, { "cell_type": "code", "execution_count": 109, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "inf\n" ] }, { "data": { "text/plain": [ "5" ] }, "execution_count": 109, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# could brute force with O(n^2) \n", "class Solution:\n", " def maxProfit(self, prices: List[int]) -> int:\n", " min_price = float('inf')\n", " print(min_price)\n", " max_profit = 0\n", " # for i in range(len(prices)):\n", " for price in prices:\n", " diff = price - min_price\n", "\n", " if price < min_price:\n", " min_price = price\n", " elif diff > max_profit:\n", " max_profit = diff\n", " \n", " return max_profit\n", "\n", "prices = [7,1,5,3,6,4]\n", "\n", "min(prices)\n", "\n", "Solution().maxProfit(prices)\n", "# Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.\n", "# Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell." ] }, { "cell_type": "code", "execution_count": 114, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "execution_count": 114, "metadata": {}, "output_type": "execute_result" } ], "source": [ "prices = [7,1,5,3,6,4]\n", "\n", "# using the builtins but doesn't really work very nicely. \n", "min(prices)\n", "max(prices)\n", "prices.index(max(prices))\n", "prices.index(min(prices))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 124. Binary Tree Maximum Path Sum (hard)\n", "\n", "A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.\n", "\n", "The path sum of a path is the sum of the node's values in the path.\n", "\n", "Given the root of a binary tree, return the maximum path sum of any non-empty path." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 125. Valid Palindrome (easy)\n", "\n", "A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.\n", "\n", "Given a string s, return true if it is a palindrome, or false otherwise." ] }, { "cell_type": "code", "execution_count": 116, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "amanaplanacanalpanama\n", "amanaplanacanalpanama\n" ] }, { "data": { "text/plain": [ "True" ] }, "execution_count": 116, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def isPalindrome(self, s):\n", " l, r = 0, len(s)-1\n", " while l < r:\n", " while l < r and not s[l].isalnum():\n", " l += 1\n", " while l