LeetCode

The Problem The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values. For example, for arr = [2,3,4], the median is 3. For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5. Implement the MedianFinder class: MedianFinder() initializes the MedianFinder object. void addNum(int num) adds the integer num from the data stream to the data structure. double findMedian() returns the median of all elements so far. Answers within 10⁻⁵ of the actual answer will be accepted. Examples Input ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] Output [null, null, null, 1.5, null, 2.0] Explanation MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2) medianFinder.addNum(3); // arr = [1, 2, 3] medianFinder.findMedian(); // return 2.0 Constraints -10⁵ <= num <= 10⁵ There will be at least one element in the data structure before calling findMedian(). At most 5 * 10⁴ calls will be made to addNum and findMedian(). Follow-up: If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution? If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution? Sorting Solution class MedianFinder { private var data: [Int] init() { self.data = [] } func addNum(_ num: Int) { data.append(num) } func findMedian() -> Double { data.sort() let n = data.count if (n & 1) != 0 { return Double(data[n / 2]) } else { return (Double(data[n / 2]) + Double(data[n / 2 - 1])) / 2 } } } Explanation One approach to solving this problem is to apply a built-in sorting algorithm. To find the result, we use an array to collect all numbers added using the addNum method. ...

The Problem Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. ...

The Problem 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. The path sum of a path is the sum of the node’s values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path. ...

The Problem 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. Examples Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] Input: preorder = [-1], inorder = [-1] Output: [-1] Constraints 1 <= preorder.length <= 3000 inorder.length == preorder.length -3000 <= preorder[i], inorder[i] <= 3000 preorder and inorder consist of unique values. Each value of inorder also appears in preorder. preorder is guaranteed to be the preorder traversal of the tree. inorder is guaranteed to be the inorder traversal of the tree. Depth First Search Solution func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? { if preorder.isEmpty || inorder.isEmpty { return nil } let rootVal = preorder[0] let root = TreeNode(rootVal) guard let mid = inorder.firstIndex(of: rootVal) else { return nil } if mid > 0 { root.left = buildTree(Array(preorder[1...mid]), Array(inorder[0..<mid])) } if mid < inorder.count - 1 { root.right = buildTree(Array(preorder[mid + 1..<preorder.count]), Array(inorder[mid + 1..<inorder.count])) } return root } Explanation We can solve this problem by understanding how preorder and inorder traversal work. ...

The Problem Given the root of a binary search tree and an integer k, return the kth smallest value (1-indexed) among all the values of the nodes in the tree. Examples Input: root = [3,1,4,null,2], k = 1 Output: 1 Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3 Constraints The number of nodes in the tree is n. 1 <= k <= n <= 10⁴ 0 <= Node.val <= 10⁴ Follow-up: If the BST is modified often (i.e., we can perform insert and delete operations) and you need to find the kth smallest element frequently, how would you optimize? ...