When nums[i] > nums[j], it is global inversion. Local inversion is special case of global inversion with j=i+1 Consider the array: [0,1,2,3,4,5] If i swap a random element by 2 positions (either to left or right). I will always create 2 inversions. Likewise, if I swap a random element by 3 positions. I end up creating 3 inversions. Similarly if I swap an element by 4 positions. I end up creating 4 inversions. ...
We need to divide the array nums into k subsets such that the sum of each subset is same. $$ k \times sum\ of\ each\ subset = total\ sum\ sum\ of\ each\ subset = total\ sum\ \div k\ target = total\ sum\ \div k $$ Now our task is to find all the k subsets in nums whose sum is target. My idea is to structure this as multi-level recursion. We first try to find the $$k^{th}$$ subset, then $$(k-1)^{th}$$, then $$(k-2)^{th} …$$ until there is only one subset left. The last subset will naturally sum to target. You can only go to $$(k-1)^{th}$$ level when you are able to successfully find $$k^{th}$$ level subset, ...
For each possible word, we ask the question: What possible queries can lead to this word?. For example consider the word: abd. Below are the possible (prefix, suffix) queries that can return abd 1 2 3 4 5 6 7 8 9 10 (prefix, suffix) a abd a bd a d ab abd ab bd ab d abd abd abd bd abd d Now, given word.length <= 7. Each word can at maximum generate 7*7=49 such pairs. Can we store all of them in a hashmap? Yes, because the total storage = 49 * number of words = O(n) Which is acceptable for this problem. ...
This problem is very similar to lc543, which is about finding the longest edge path in a tree. You can just copy over that code, and add 2 lines in it. Here we are doing the same thing as in lc543, however, when we encounter a non-matching child. We treat it as null. For example, here the longest path at root node is highlighted below in red with 6 edges. ...
I keep track of the top k elements in sorted list. The kth largest element is the smallest of the top k elements. e.g. top k(=6) elements: [3,5,7,10,42,56] in sorted order. The kth largest element = 6th largest element = smallest element in above list. When I insert an element, I simply check if it can make it’s place among k largest elements already present in the list. Which it can, if it can defeat the smallest element in our list. ...