Kth Smallest Element in BST
230. Kth Smallest Element in a BSTProblem DescriptionGiven the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree. IntuitionBinary TreeIn BST, all nodes in the left subtree are smaller than the root. So if the left subtree has L nodes, the root is the (L+1)th smallest. We can use this to decide whether to go left, return current, or go right.inorderIn BST, an inorder traversal visits nodes in sorted order, so th...
Lowest Common Ancestor of BST
Lowest Common Ancestor of a Binary Search TreeProblem DescriptionGiven a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).” IntuitionSince tree is BST, we know every left child is strictly less than root value, and eve...
Minimum Window Substring
Minimum Window SubstringProblem DescriptionGiven two strings s and t of lengths m and n respectively, return the minimum window substring 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 "". The testcases will be generated such that the answer is unique. IntuitionWe need to find the shortest substring of s that contains all characters from t. Store the character frequencies of t in a hash map...
Product of Array Except Self
Product of Array Except SelfProblem DescriptionGiven 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]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in $O(n)$ time and without using the division operation. IntuitionSince product[i] should be the product of all numbers except nums[i], we could break it down into two parts left[i] and ...
Validate Binary Search Tree
Validate Binary Search TreeProblem DescriptionGiven the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys strictly less than the node’s key. The right subtree of a node contains only nodes with keys strictly greater than the node’s key. Both the left and right subtrees must also be binary search trees. IntuitionBased on the BST definition, we could set min and max as the val...
3sum
3sumProblem DescriptionGiven 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. Notice that the solution set must not contain duplicate triplets. IntuitionWe can break down this problem by fixing one element and converting it into a 2Sum problem: Fix one element as the first number Solve for the remaining elements using the 2Sum approach Time Complexity: $O(n^2)$Space Complexity: $O(n)$ for s...
Binary Tree Level Order Traversal
Binary Tree Level Order TraversalProblem DescriptionGiven the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level). IntuitionDFSWe use layer to track current node’s depth. We insert values from top to bottom and from left to right by visiting left subtree before right subtree. BFSWe use a queue to track all nodes at the current level. For each level, we process all nodes in the queue: extract their values and add their childr...
Construct Binary Tree from Preorder and Inorder
105. Construct Binary Tree from Preorder and Inorder TraversalProblem DescriptionGiven 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. IntuitionThe front element of preorder traversal is the tree’s root node(the middle of inorder traversal). We use it to determine which elements belong the left subtree and the right subtree, and keep comparing the preo...
Container With Most Water
Container With Most WaterProblem DescriptionYou are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the $i^{th}$ line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container. IntuitionThe area of water a container is determined by two factors: heig...
Thread and Process
Program (程式)Program 意旨軟體工程師在 IDE、editor 等所寫的程式碼(code)，也就是說還尚未 load 入記憶體的 code，我們稱之為 Program。• 相同 Program 所建立的 Process 可以多個同時存在。 Process (行程，亦可稱作處理程序、進程)Process 是正在執行中的 Program 實例，點開應用程式就是讓 OS 從硬碟中載入到 Memory 中，分配必要的系統資源，建立一個 Process 來執行它。 以下條列幾點 Process 的觀念 Process 是電腦中已執行 Program 的 Instance。 每一個 Process 是互相獨立的。 Process 本身不是基本執行單位，而是 Thread 的資源管理和執行環境。 Process 需要一些資源才能完成工作，如 CPU、記憶體、檔案以及 I/O 裝置。 在多功作業系統(Multitasking Operating System)中，可以同時執行數個 Process ，然而一個 CPU 一次只能執行一個 Process，而 Process...
