MayChallenge (51) } | Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Example 1:

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Constraints:

• The number of elements of the BST is between 1 to 10^4.
• You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

I use binary search tree to solve this problem, this important is function count(), let view code:

Find Kth Smallest in BST

	/**
	* 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 {
	public int kthSmallest(TreeNode root, int k) {
	int c = count(root.left);
	if (k<=c){
	return kthSmallest(root.left,k);
	}
	else if (k>c+1){
	return kthSmallest(root.right,k-1-c);
	}
	return root.val;
	}
	private int count(TreeNode node){
	if (node == null){
	return 0;
	}
	return 1+ count(node.left) + count(node.right);
	}
	}

view raw KthSmallestElementInBST.java delivered with ❤ by emgithub

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

This problem similar the odd problem i did here, it call is Dynamic Programming:

	class Solution {
	public int countSquares(int[][] matrix) {
	int m = matrix.length;
	int n = matrix[0].length;
	int [][]dp = new int[2][n+1];
	int res = 0;
	int unique = 0;
	for (int[] arr:matrix){
	for (int i:arr){
	System.out.print(i+" ");
	}
	System.out.println();
	}
	for (int i=0; i<=m; i++){
	for (int j=0; j<=n; j++){
	unique = i&1;
	if (i==0 || j==0){
	dp[unique][j] = 0;
	}
	else if (matrix[i-1][j-1] == 0){
	dp[unique][j] = 0;
	}
	else{
	dp[unique][j] = min(dp[1-unique][j],dp[1-unique][j-1],dp[unique][j-1]) + 1;
	}
	res+=dp[unique][j];
	}
	}
	return res;
	}
	private int min(int a, int b, int c){
	return a<b && a<c ? a: b<c ? b:c;
	}
	}

view raw CountSquareSubmatricesWithAllOne.java delivered with ❤ by emgithub

Thank you.