Leetcode–Validate Binary Search Tree

The Problem:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

Notes:

  1. Note that a valid BST should have ALL node in the left less than the root (of each level), not only the immediate left child. This impose a min-max constraint of all the nodes other than top root.
  2. In the recursion, it also pass that min-max constraint from top to bottom. In each recursion it checks left and right node not only valid for their parent (left < root < right), but also check if they are in the min-max range (The range is built up by all their ancestors).

Java Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   public boolean isValidBST(TreeNode root){
        return isValid(root Integer.MIN_VALUE, Integer.MAX_VALUE) ;
    }
 
    private boolean isValid(TreeNode root, int min, int max){
        if(root==null) return true;
        if(root.val <= min || root.val >= max)
            return false;
        return isValid(root.left, min, root.val) && isValid(root.right, root.val, max);
    }
}

Leetcode–Convert Sorted List to Binary Search Tree

The Problem:

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

Notes:

  1. Similar to Convert Sorted Array to Binary Search Tree, but in this problem we don’t have easy access to the middle element.
  2. A bottom-up approach is used here, the treenodes will be constructed by the order of listnode in p. The trick is keep a pointer to the current ListNode p, p is “global” and gets updated in each recursion. So inside each recursion, treenode should be constructed exactly in order left->parent->right, because p will get updated in branches also.

Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; next = null; }
 * }
 */
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode p; // p need to be passed in and out of constructTree
    public TreeNode sortedListToBST(ListNode head) {
        int len = getLength(head);
        if(len == 0) return null;
        p = head;
        return constructTree(0, len-1);
    }
    
    private int getLength(ListNode head){
        int len = 0;
        while(head!= null){
            head = head.next;
            len++;
        }
        return len;
    }
    
    private TreeNode constructTree(int start, int end){
        if(start > end) return null;
        int mid = (start+end)/2;
        TreeNode parent = new TreeNode(0);
        //--!!--here the order should be :
        // 1. left (p got updated there also) 2. parent (AND UPDATE p) 3. right
        parent.left = constructTree(start, mid-1);
        parent.val = p.val;
        p = p.next;
        parent.right = constructTree(mid+1, end);
        return parent;
    }
}

Leetcode–Convert Sorted Array to Binary Search Tree

The Problem:

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Notes:

  1. BST is left node left less than parent then less than right. As the input array is in ascending order, in each recursion , take the middle element as parent,  first half start a branch to construct left child, latter half start another branch to construct right child.

Java Solution

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        int len = num.length;
        if(len==0) return null;
        return constructTree(num, 0, len-1);
        
    }
    
    private TreeNode constructTree(int[] num, int start, int end){
        if(start > end) return null;
        int mid = (start+end)/2;
        TreeNode parent = new TreeNode(num[mid]);
        parent.left = constructTree(num, start, mid-1);
        parent.right = constructTree(num, mid+1, end);
        return parent;
    }
}

Leetcode–Search for a Range

The Problem:

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Notes:

  1. Do binary search, when found match, then expand to get range.
  2. Mistake I made:
    1. When doing low– and high++, need to check the bound before accessing the element.
    2. Array to initialize with value can written as ” new int[] {a, b}”

Java Solution

public class Solution {
    public int[] searchRange(int[] A, int target) {
        if(A.length==0 || target < A[0] || target > A[A.length-1]) 
           return new int[]{-1,-1};
        int low = 0;
        int high = A.length-1;
        while(low <= high){
            int mid = (low+high)/2;
            if(A[mid]== target){
                low = mid-1;
                while(low >=0 && A[low]==target){
                    low--;
                }
                high = mid+1;
                while(high < A.length && A[high]==target){
                    high++;
                }
                return new int[]{low+1, high-1};
            }
            else if (A[mid] < target){
                low = mid+1;
            }
            else {
                high = mid-1;
            }
        }
        return new int[]{-1,-1};
    }
}

Leetcode–Search Insert Position

The Problem:

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Notes:

  1. Be careful about bounds, and do binary search.
  2. Attention to return low or high, also see in Sqrt(x)
  3. Mistake I made:
    1. if target equals to or less than first number, both return 0; but if target equals to last number return length-1, greater than last number should return length.

Java Solution

public class Solution {
    public int searchInsert(int[] A, int target) {
        if(A==null || A.length==0) return 0;
        if(target <= A[0]) return 0;
        if(target > A[A.length-1]) return A.length;
        int low = 0;
        int high = A.length-1;
        while(low <= high){
            int mid = (high+low)/2;
            if(A[mid]==target)
                return mid;
            if(A[mid] < target){
                low = mid+1;
            }
            else{
                high = mid-1;
            }
        }
        return low;
    }
}

Leetcode–Search a 2D Matrix

The Problem:

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Notes:

  1. First find the candidate row, then do binary search

Java Solution

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        for(int i = 0; i < m; i++){
            if(target < matrix[i][0])
                return false;
            else if(target > matrix[i][n-1])
                continue;
            else{
                // in this row
                int low = 0;
                int high = n-1;
                while(low <= high){
                    int mid = (high + low)/2;
                    if(matrix[i][mid] == target)
                        return true;
                    else if (matrix[i][mid] > target)
                        high= mid-1;
                    else 
                        low = mid+1;
                }
                return false;
            }
        }
        return false;
    }
}

Leetcode–Sqrt(x)

The Problem:

Implement int sqrt(int x).

Compute and return the square root of x.

Notes:

  1. Like Divide two integers and Pow(x,n), a math problem in face is a search problem, here we use binary search.
  2. Note that when doing square, the result could exceed integer range, so we use long type to hold the value.
  3. Mistakes I made:
    1. condition for while loop is high>=low, not high > low
    2. In each step, either high or low will update, but should update to mid+-1 instead of mid, because if mid happens to be same as low, it will keep going to same branch and result in infinite loop.

Java Solution

public class Solution {
    public int sqrt(int x) {
        if(x==0 || x==1) return x;        
        long low= 1;
        long high = x;
        while(high >=low){   // not high>low  
            long mid = (low+high)/2;
            if(x==mid * mid)
                return (int)mid;
            if(x<mid*mid)
                high = mid-1;  // not high=mid 
            else
                low = mid+1;    
        }
        return (int)high;
    }
}