## Posts

Recent posts

### LeetCode 51 N Queens

The problem Input integer n Place n queens on n x n  board Q  means queen at cell .  Means empty space Queen can move in any direction Horizontally Up Down Diagonal neg + pos The Trick, let's say for 4x4 Understanding Notice that each and every queen has to be in a different row ! Notice that each and every queen has to be in a different column ! Notice that each and every queen has to be in a different positive diagonal ! Notice that each and every queen has to be in a different negative diagonal ! State - Set - is queen in column, posDiag (row-col), negDiag (row+col) Which rows have queen - do not have to store in state we just loop the rows Which columns have queen - store in state ! Which posDiag have queen - store in state! Which negDiag have queen - store in state! Trick posDiag -> row - column = constant Every time we increase row we increase column negDiag -> row + column = constant Every time we increase row we decrease column Loop 1st queen 1st row Can put first q

### 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 = , k = 1 Output:   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 https://amzn.to/3y84FHQ 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