Skip to main content


Showing posts from July, 2022

LeetCode 347. Top K Frequent Elements

Given an integer array  nums  and an integer  k , return  the   k   most frequent elements . You may return the answer in  any order . Example 1: Input:  nums = [1,1,1,2,2,3], k = 2 Output:  [1,2] Example 2: Input:  nums = [1], k = 1 Output:  [1] Option 1 - Map to count + Sort to get top k - O(nlgn) We need to count what is the freq or how many times an item appeared. The obvious thing is  for each item  put it in a hashmap where Key is the item Value is the number of times it appeared Now the only thing that is left is to sort this hashtable. sorting is O(nlgn), placing everyting and counting is O(n) so this makes it overall O(nlgn) Option 2 - Improvement over option 1 - Instead of sorting use a Heap This is a common thing when you need to sort but the  core of the problem is not sorting  but as in this example only get top k then we could utilize a heap. We still build a  map  as in option 1 which takes O(n) this is the counting map. Building a heap  heapify  takes O(n) Remove  each

LeetCode 129 Sum Root to Leaf Number

  LeetCode 129 Sum Root to Leaf Numbers Given a root of binary tree containing digits from 0 to 9 only. Return the total sum of all root to leaf. The question is taken from the book “ Elements of Programming Interviews in Python ” page 125 We see we have here these routes to path 495 +491 +40 Which in total is 1026 Now let’s see how to solve it in java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { // This is an excellent trick to save us from passing params. int total = 0; public int sumNumbers(TreeNode root) { sumNumbers(root, 0); return total; } private void sumNumbers(Tr