public int largestBSTSubtree(TreeNode root) {
int[] size = {0};
helper(root, size);
return size[0];
}
private int[] helper(TreeNode root, int[] size) { // array
int[] res = new int[3]; // nums, min, max
res[0] = 0;
res[1] = Integer.MAX_VALUE; // min
res[2] = Integer.MIN_VALUE; // max
if (root == null) return res;
int[] left = helper(root.left, size);
int[] right = helper(root.right, size);
if (left[0] == 1  right[0] == 1) {
res[0] = 1;
} else {
if (root.val > left[2] && root.val < right[1]) {
res[0] = 1 + left[0] + right[0];
if (res[0] > size[0]) size[0] = res[0];
res[1] = Math.min(root.val, left[1]);
res[2] = Math.max(root.val, right[2]);
} else {
res[0] = 1;
}
}
return res;
}
crickey180
@crickey180
Can I get that 1% of inspiration?
Posts made by crickey180

Java 3element array TopDown O(n)

RE: Java: Least is Most
@tracymcgrady e.g. [ [1,4], [2,3], [3,4] ], the interval with early start might be very long and incompatible with many intervals. But if we choose the interval that ends early, we'll have more space left to accommodate more intervals. Hope it helps.

RE: Java: Never Start or Stick to the End
@rgilbertpaul Maybe you mean if the given tree has the structure of a linkedlist, the time complexity would be O(n^2). But the tree given is a binary tree, so the time complexity should be O(n log n). Thx for your reply : )

RE: Can anyone help? Java DFS solution but have some problem _(:з」∠)_
@monstergump You are welcome~

RE: Can anyone help? Java DFS solution but have some problem _(:з」∠)_
@monstergump Not sure what exactly do you mean... But here are some thoughts:
first,
this is not a valid base case, because we have nodes with negative value.if (root.val == sum) { return 1;}
e.g.
[0,1,null,1]
0
this should return 3, your code would return 1.second,
broken pathe.g.
[1,2,null,3]
4
this should return 0, your code would return 1.I'll use the node value to represent the node, and show the call stacks returns 1.
call stack0: pathSum(root.left, sum) > pathSum(1, 4)
call stack1: pathSum(root.left, sum  root.val) > pathSum(1.left, 4  1) > pathSum(2, 3)
call stack2: pathSum(root.left, sum) > pathSum(2.left, 3) > pathSum(3, 3)
then returns 1.So you need a way to make sure that the path doesn't split in the middle.
Hope it helps.

RE: Can anyone help? Java DFS solution but have some problem _(:з」∠)_
@monstergump The way you implemented make it possible to have a broken path, so you have 102 = 8 as an answer.. You can check my solution.

Java: Never Start or Stick to the End
Either the path has not started, or it has to go all the way to the end.
Isn't it like the career we chose? : )Time Complexity: O(n log n): each node is visited by its ancestors.
Space Complexity: O(1): we don't store nodes.public int pathSum(TreeNode root, int sum) { return helper(root, sum, false); } // Either the path has not started, or it has to go all the way to the end. private int helper(TreeNode root, int sum, boolean hasStarted) { if (root == null) return 0; // if the path has not started, we start now or not. if (!hasStarted) { return helper(root, sum, true) + helper(root.left, sum, false) + helper(root.right, sum, false); } // if the path has started sum = root.val; return helper(root.left, sum, true) + helper(root.right, sum, true) + (sum == 0? 1 : 0); }

Java Recursive and Iterative
Iterative:
public String getPermutation(int n, int k) { // e.g n = 5 // [1][1][2][6][24] int[] factorial = new int[n]; factorial[0] = 1; for(int i = 1; i < n; i++) { factorial[i] = factorial[i1] * i; } ArrayList<Integer> numbers = new ArrayList<>(); for(int i = 1; i <= n; i++) { numbers.add(i); } String res = ""; for(int i = n1; i >= 0; i) { int num = (k1)/factorial[i]; res += numbers.get(num); k = num * factorial[i]; numbers.remove(num); } return res; }
Recursive:
public String getPermutation(int n, int k) { // recursive // how do you make the problem smaller? List<Integer> list = new ArrayList<>(); // 1,1,2,6 int[] factorials = new int[n]; factorials[0] = 1; for(int i = 1; i < n; i++) { factorials[i] = factorials[i1] * i; } for(int i = 1; i <= n; i++) { list.add(i); } return helper(list, k, factorials); } private String helper(List<Integer> list, int k, int[] factorials) { if(list.size() == 0) { return ""; } int num = (k1)/factorials[list.size()1]; String str = "" + list.get(num); k = num * factorials[list.size()1]; list.remove(num); return str+helper(list, k, factorials); }

Java: Least is Most
Actually, the problem is the same as "Given a collection of intervals, find the maximum number of intervals that are nonoverlapping." (the classic Greedy problem: Interval Scheduling). With the solution to that problem, guess how do we get the minimum number of intervals to remove? : )
Sorting Interval.end in ascending order is O(nlogn), then traverse intervals array to get the maximum number of nonoverlapping intervals is O(n). Total is O(nlogn).
public int eraseOverlapIntervals(Interval[] intervals) { if (intervals.length == 0) return 0; Arrays.sort(intervals, new myComparator()); int end = intervals[0].end; int count = 1; for (int i = 1; i < intervals.length; i++) { if (intervals[i].start >= end) { end = intervals[i].end; count++; } } return intervals.length  count; } class myComparator implements Comparator<Interval> { public int compare(Interval a, Interval b) { return a.end  b.end; } }