[Leetcode] Count of Range Sum

327. Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.
Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.

Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.

Example:
Given nums = [-2, 5, -1], lower = -2, upper = 2,
Return 3.
The three ranges are : [0, 0], [2, 2], [0, 2] and their respective sums are: -2, -1, 2.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

 

My naive approach gets me TLE, as expected.


//This naive O(n^2) algorithm of course gets me TLE
public int countRangeSum_my_naive_way(int[] nums, int lower, int upper) {
Set<String> uniqueRangeSums = Sets.newHashSet();
StringBuilder sb = new StringBuilder();
for(int i = 0; i < nums.length; i++){
long sum = nums[i];
if(sum >= lower && sum <= upper) uniqueRangeSums.add(sb.append("" + i + i).toString());
sb.setLength(0);
for(int j = i+1; j < nums.length; j++){
sum += nums[j];
if(sum >= lower && sum <= upper) uniqueRangeSums.add(sb.append("" + i + j).toString());
sb.setLength(0);
}
}
return uniqueRangeSums.size();
}

 

Then looked at dietpepsi’s post: https://discuss.leetcode.com/topic/33738/share-my-solution

I didn’t sort out my logic following his ideas yet. [TODO] completely understand it.


public int countRangeSum(int[] nums, int lower, int upper) {
int n = nums.length;
long[] sums = new long[n+1];
for(int i = 0; i < n; i++){
sums[i+1] = sums[i] + nums[i];
}
return countWhileMergeSort(sums, 0, n+1, lower, upper);
}

private int countWhileMergeSort(long[] sums, int start, int end, int lower, int upper) {
if(end - start <= 1) return 0;
int mid = (start+end)/2;
int count = countWhileMergeSort(sums, start, mid, lower, upper) + countWhileMergeSort(sums, mid, end, lower, upper);
int j = mid, k = mid, t = mid;
long[] cache = new long[end-start];
for(int i = start, r = 0; i < mid; i++, r++){
while(k < end && sums[k] - sums[i] < lower) k++;
while(j < end && sums[j] - sums[i] <= upper) j++;
while(t < end && sums[t] < sums[i]) cache[r++] = sums[t++];
cache[r] = sums[i];
count += j-k;
}
System.arraycopy(cache, 0, sums, start, t-start);
return count;
}

Advertisements

Data Stream as Disjoint Intervals

https://leetcode.com/problems/data-stream-as-disjoint-intervals/

  • I’m thinking to maintain the numbers as a sorted array, but it doesn’t give me quick insertion into the correct place
  • Then I was thinking to use the previous problem Insert Interval to help with this one, but that’s purely cheating and I’m not if that can work either.
  • The moment, I clicked the Tag, it shows Binary Search Tree, I’m impressed!
    • It’s this thought process that values! Don’t click to show Tags too early, think about it, which data structure would you come up to use?
  • Now, my thoughts:
    • try to use the idea from https://fishercoder.com/2016/07/16/count-of-smaller-numbers-after-self/
    • to build a BST, while inserting a new node, check to see if merge is needed, check both the node’s parent and child, let each node’s value be the lower boundary of the interval and define another field which is the array of interval in this node class
    • after trial and error, rewriting it multiple times: discussion with badyu2000@ here: https://discuss.leetcode.com/topic/47084/java-fast-log-n-solution-186ms-without-using-the-treemap-but-a-customized-bst/12
    • I’ve got my 100% original code to pass 8/9 test cases, I’m really excited about it, my thought process could be visited in that thread, but I’m still puzzled why the last case didn’t pass, from my eyes check, I don’t see any difference between my output and the expected output.

Count of Smaller Numbers After Self

https://leetcode.com/problems/count-of-smaller-numbers-after-self/

Inspired by this post: https://discuss.leetcode.com/topic/31405/9ms-short-java-bst-solution-get-answer-when-building-bst

  • Several keys:
    • it’s always returning the node in the recursive function instead of returning node.left or node.right, but just updating the final result Integer[] ans along the way
    • Single-step through it via Eclipse helps understand it better if you cannot completely visualize how the resursive call goes.
    • don’t need to construct root node (last element in the original array) beforehand, just let the recursive function build it itself, it’s actually one of the base cases for the recursive function
    • two base cases:
      • when the node is null, then we know it’s a new node, so we just construct a new node with its val and sum == 0 and assign the prevSum to ans[i]
      • when the node is not null and nums[i] equals to node.val, that means this is a duplicate value for the previous node, so we just update the dup field and assign the prevSum directly to ans[i]
    • all the rest, we’ll make it recursive calls to itself, also two cases:
      • if the to-be-inserted node’s value is smaller than the current node.val, then the to-be-inserted node should be appended as left child of the current node and prevSum doesn’t need to be updated (think about this example: [5,2,6,1], when we insert 2 into the tree, it should be appended as the left child of 6 and prevSum doesn’t need to be updated)
      • if the to-be-inserted node’s value is greater than the current node.val, then the to-be-inserted node’s should be appended as the current node’s right child and prevSum needs to be updated to prevSum + node.sum + node.dup (think about this example: [5,2,6,1], when we insert 5 into the tree, it should be appended as the right child of 2 and prevSum should be updated to prevSum + node.sum + node.dup)

CountNumbersSmallerAfterSelf

  • It really opened my eyes that one TreeNode could have multiple values in it, yes, why not?
  • I knew that I had to build the tree, but I had difficulty thinking how to build the tree, it turns out that he built the tree from the given array right to left order, thus achieving the purpose of counting the number of smaller elements to the right of it
  • The result array must be taken into the insertNode() function, because I was thinking to build the tree first, and then dfs this tree and put the value of each node into the result, this won’t work because the same number might appear again in different positions, then the count of smaller numbers after them will be different.
  • Remember to return the node we just built to node to get ready for the next insertNode() call, that’s why we have to return a node instead of making this function a void return type.
  • This insertNode() is a recursive call!!! Naturally, otherwise, how can it build the tree? It needs to traverse it from top to bottom every time when it tries to insert a new node.
  • Beautiful! Definitely an eye-opener for me!
  • Again, data structure is the core in computing!
  • One small note: the reason we used Integer[] ans instead of int[] ans is that we cannot have a list of primitive types, it must be an object, thus we used Integer[], cool!

public class Solution {
class Node{
int val;
int sum;
int dup = 1;
Node left;
Node right;
public Node(int v, int s){
this.val = v;
this.sum = s;
}
}

public List<Integer> countSmaller(int[] nums) {
Integer[] ans = new Integer[nums.length];
Node root = null;
for(int i = nums.length-1; i >= 0; i--){
root = insertNode(nums[i], root, i, 0, ans);
}
return Arrays.asList(ans);
}

Node insertNode(int val, Node node, int i, int prevSum, Integer[] ans){
if(node == null){
node = new Node(val, 0);
ans[i] = prevSum;
} else if(val == node.val){
node.dup += 1;
ans[i] = prevSum + node.sum;
} else if(val > node.val){
node.right = insertNode(val, node.right, i, prevSum + node.sum + node.dup, ans);
} else {
node.sum += 1;
node.left = insertNode(val, node.left, i, prevSum, ans);
}

return node;
}

}

My naive brute force algorithm returns me a TLE:

public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
for(int i = 0; i < nums.length; i++){
int count = 0;
for(int j = i+1; j < nums.length; j++){
if(nums[i] > nums[j]) count++;
}
res.add(count);
}
return res;
}

 

Kth Smallest Element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

A simple in-order traversal could get it AC’ed. Cheers.

[TODO] read others’ more optimal code that didn’t traverse the entire tree, instead, they just return when they found the kth one. Rewrite it myself.


public class Solution {
List<Integer> list;
public int kthSmallest(TreeNode root, int k) {
list = new ArrayList<Integer>();
inorder(root);
return list.get(k-1);
}

void inorder(TreeNode root){
if(root == null) return;
if(root.left != null) inorder(root.left);
list.add(root.val);
if(root.right != null) inorder(root.right);
}
}

Recover Binary Search Tree

https://leetcode.com/problems/recover-binary-search-tree/

I attempted to break this one completely by myself, my approach was to find the two nodes by DFS and just swap the two nodes’ values by storing the first value temporarily and DFS the tree three times:

  1. 1st time, to find the first node that should be swapped and store its value in temp1
  2. 2nd time, to find the second node that should be swapped and store its value in temp2, and assign temp1 to be its new value
  3. 3rd time, to find the first node and assign temp1 to be its new value. Done.

Looks like a feasible approach, I even wrote the code for the above approach, but it takes more time to handle the root case (I think I might need process root separately and then do DFS on left and right subtrees.)

Then this most upvoted post amazingly used the simple in-order traversal to have implemented this:

https://discuss.leetcode.com/topic/3988/no-fancy-algorithm-just-simple-and-powerful-in-order-traversal

  • inorder traversal is like this (or its template):
    public void inorderTraversal(TreeNode root){inorderTraversal(root.left); //do some business logic;inorderTraversal(root.right)}
  • prev means the one previous to the current root, refer to in-order traversal, previous element must be smaller than the current root, if it’s bigger, then we find the first element, thus we store it in the variable called firstElement
  • prev = root;

    this is the last step in the “do some business logic”, so we’ll always to have update the previous node to be the current root before it traverses the right subtree, since the current root will be the new previous node for the right subtree.


public class Solution {

TreeNode first = null;
TreeNode second = null;
TreeNode prev = new TreeNode(Integer.MIN_VALUE);

public void recoverTree(TreeNode root) {
inorderTraversal(root);

int temp = first.val;
first.val = second.val;
second.val = temp;
}

void inorderTraversal(TreeNode root){
if(root == null) return;

inorderTraversal(root.left);

if(first == null && prev.val >= root.val){
first = prev;
}

if(first != null && prev.val >= root.val){
second = root;
}

prev = root;

inorderTraversal(root.right);
}
}