@JeffJing
Do you have an example of the input?
Yong Su
@jeantimex
Engineer at Box working on React, Redux, React Native, Electron and Swift.
Posts made by jeantimex

RE: Another accepted Java solution (BFS)
I think we can, but we need to make sure we dfs all the possible paths before we can say "I find the shortest path!". Normally dfs uses recursion, however, we can use iteration in bfs and guaranteed the shorted path, it's much better.

RE: Rearrange Tasks
You are right! I am not sure if this will work: step 1, count the characters, group them in a hash map and sort by the count; step 2, pick each character in count order and form the final string. This is a simple idea and it will solve the case above, but not sure if there's any corner case.

RE: Share my Java recursive solution
Hi @xietao0221, let's take the successor for example, basically we always want to find
p
's closest node (in inorder traversal) and the node's value is larger thanp
's value, right? That node can either bep
's parent or the smallest node inp
' right branch.When the code runs into the else block, that means the current root is either
p
's parent or a node inp
's right branch.If it's
p
's parent node, there are two scenarios: 1.p
doesn't have right child, in this case, the recursion will eventually return null, sop
's parent is the successor; 2.p
has right child, then the recursion will return the smallest node in the right sub tree, and that will be the answer.If it's
p
's right child, there are two scenarios: 1. the right child has left sub tree, eventually the smallest node from the left sub tree will be the answer; 2. the right child has no left sub tree, the recursion will return null, then the right child (root) is our answer.I guess it's hard to understand unless you draw different scenarios out. :)

RE: Elegant Java solution
Hi @d20@15, you can imagine the helper( ) function goes from the bottom of the tree to the top, it's in postorder manner.
At every node, we need to make a decision, if the sum comes from the left path larger than the right path, we pick the left path and plus the current node's value, this recursion goes all the way up to the root node.

RE: Complicated segmentree solution, hope to find a better one
This is just amazing! Thanks for sharing this solution!

RE: Sort array with negative numbers followed by positive numbers
Just want to share the merge sort solution in
O(nlogn)
time, themerge()
function takesO(n)
time andO(1)
space. Not sure how hard is it to implement theO(n)
solution.public class Solution { public void rearrange(int[] a) { sort(a, 0, a.length  1); } void sort(int[] a, int lo, int hi) { if (lo >= hi) return; int mid = lo + (hi  lo) / 2; sort(a, lo, mid); sort(a, mid + 1, hi); merge(a, lo, mid, hi); } void merge(int[] a, int lo, int mid, int hi) { int i = lo, j = mid + 1; while (i <= mid && a[i] < 0) i++; while (j <= hi && a[j] < 0) j++; reverse(a, i, mid); // reverse the positive part A in the left to A' reverse(a, mid + 1, j  1); // reverse the negative part B in the right to B' reverse(a, i, j  1); // reverse A'B' to B'A' } void reverse(int[] a, int lo, int hi) { int i = lo, j = hi; while (i < j) { int tmp = a[i]; a[i++] = a[j]; a[j] = tmp; } } }

RE: Share some thoughts
Great problem, I like the way you go through the idea! Thanks @peisi!

Share my Java 2D Binary Indexed Tree Solution
Based on the 1D solution in problem Range Sum Query  Mutable, we can extend it to solve this 2D problem.
Initializing the binary indexed tree takes
O(mn*logm*logn)
time, bothupdate()
andgetSum()
takeO(logm*logn)
time. Thearr[][]
is used to keep a backup of thematrix[][]
so that we know the difference of the updated element and use that to update the binary indexed tree. The idea of calculatingsumRegion()
is the same as in Range Sum Query 2D  Immutable.public class NumMatrix { int m, n; int[][] arr; // stores matrix[][] int[][] BITree; // 2D binary indexed tree public NumMatrix(int[][] matrix) { if (matrix.length == 0  matrix[0].length == 0) { return; } m = matrix.length; n = matrix[0].length; arr = new int[m][n]; BITree = new int[m + 1][n + 1]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { update(i, j, matrix[i][j]); // init BITree[][] arr[i][j] = matrix[i][j]; // init arr[][] } } } public void update(int i, int j, int val) { int diff = val  arr[i][j]; // get the diff arr[i][j] = val; // update arr[][] i++; j++; while (i <= m) { int k = j; while (k <= n) { BITree[i][k] += diff; // update BITree[][] k += k & (k); // update column index to that of parent } i += i & (i); // update row index to that of parent } } int getSum(int i, int j) { int sum = 0; i++; j++; while (i > 0) { int k = j; while (k > 0) { sum += BITree[i][k]; // accumulate the sum k = k & (k); // move column index to parent node } i = i & (i); // move row index to parent node } return sum; } public int sumRegion(int i1, int j1, int i2, int j2) { return getSum(i2, j2)  getSum(i11, j2)  getSum(i2, j11) + getSum(i11, j11); } }

Share my Java Binary Indexed Tree Solution
In the following solution, initializing the binary indexed tree takes
O(nlogn)
time, bothupdate()
andgetSum()
takeO(logn)
time. Thearr[]
is used to keep a backup of thenums[]
so that we know the difference of the updated element and use that to update the binary indexed tree.For detailed explanation, please read this article.
public class NumArray { int[] arr; // stores nums[] int[] BITree; // binary indexed tree public NumArray(int[] nums) { int n = nums.length; arr = new int[n]; BITree = new int[n + 1]; for (int i = 0; i < n; i++) { update(i, nums[i]); // init BITree[] arr[i] = nums[i]; // init arr[] } } void update(int i, int val) { int diff = val  arr[i]; // get the diff arr[i] = val; // update arr[] i++; while (i <= arr.length) { BITree[i] += diff; // update BITree[] i += i & (i); // update index to that of parent } } int getSum(int i) { int sum = 0; i++; while (i > 0) { sum += BITree[i]; // accumulate the sum i = i & (i); // move index to parent node } return sum; } public int sumRange(int i, int j) { return getSum(j)  getSum(i  1); } }