Peak Index in a Mountain Array

Problem:

Peak Index in a Mountain Array

Let's call an array A a mountain if the following properties hold:

A.length >= 3

There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Example 1:

Input: [0,1,0]

Output: 1

Example 2:

Input: [0,2,1,0]

Output: 1

Note:

3 <= A.length <= 10000

0 <= A[i] <= 10^6

A is a mountain, as defined above.

Solution:

We can use binary search to find the peak. 

class Solution {
  public static void main(String...args) {
    int[] arr = new int[]{0,2,1,0};
    int r = solve(arr);
    System.out.println(r);
  }
  private static int solve(int[] arr) { //1 2 3 4 5 7 3
    int lo = 0;   //4
    int hi = arr.length - 1;    //6
    while(lo < hi) {
      int mid = lo + (hi - lo)/2;    //5
      if(arr[mid-1] < arr[mid] && arr[mid] < arr[mid+1]) {
        lo = mid + 1;
      } else if (arr[mid-1] > arr[mid] && arr[mid] > arr[mid+1]) {
        hi = mid;
      } else {
        return mid;
      }
    }
    return lo;
  }
}

The time complexity is O(logN) and the space complexity is O(1).

Root to leaf paths

Problem

Given a binary tree, return all root-to-leaf paths.

Note: A leaf is a node with no children.

Example:

Input:

   1

 /   \

2     3

 \

  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

Solution

We can pre-order traversal the tree, use an array to record the path, once reach the leaf, print out the path. Since we want to print out all the path instead of just one, we need to backtrack. After visiting a subtree, the root node of the subtree needs to be removed from the array.

The time cost will be O(N) since we need to visit each node, the space cost will be proportional to the height of the tree. So space cost is O(logN) to O(N).

import java.util.*;
public class RootToLeaf {
  /*
   1
 /   \
2     3
 \
  5

  */
  public static void rootToLeaf(Node root, List<Integer> path) {//1
    if(root == null) return;
    if(root.left == null && root.right == null) {
      path.forEach(i -> System.out.print(i + "->"));//1->2->5, 1->3
      System.out.println(root.value);
      return;
    }
    path.add(root.value);//""
    rootToLeaf(root.left, path);
    rootToLeaf(root.right, path);
    path.remove(new Integer(root.value));
  }

  public static void main(String...args) {
    Node root = new Node(1, new Node(2, null, new Node(5, null, null)), new Node(3, null, null));
    List<Integer> path = new ArrayList<>();
    rootToLeaf(root, path);
  }

  private static class Node {
    int value;
    Node left;
    Node right;
    public Node(int value, Node left, Node right) {
      this.value = value;
      this.left = left;
      this.right = right;
    }
  }
}

Time cost O(N), space cost O(H).

Find Minimum in Rotated Sorted Array

Problem

Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 

Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]

Output: 0

Solution

This is an edge detection problem, the brutal force way is to check the first occurrence of a[i-1] > a[i]. The time cost will be O(N).

With binary search, the cost can be cut down to O(logN). The middle could land on the left of the edge or right of the edge. We also need to consider special cases when the array is not rotating, the array has only one element. 

public class MinInRotatedArray {
  public static int min(int[] a) {
    //3,4,5,6,7,0,1,2
    //        * .   
    int N = a.length;//8
    int lo = 0;
    int hi = N - 1;
    if(a[lo] <= a[hi]) return a[lo];
   
    int mid = 0;
    while(lo < hi) {//4,7
      mid = lo + (hi - lo)/2;//5
      if(mid > 0 && a[mid] < a[mid - 1]) {
        return a[mid];
      } else if(mid < N - 1 && a[mid] > a[mid+1]) {
        return a[mid+1];
      }
      if(a[lo] < a[mid]) lo = mid + 1;
      else if(a[lo] > a[mid]) {
        hi = mid - 1;
      }
      else return a[mid];
    }
    return a[mid];
  }
  public static void main(String...args) {
    System.out.println(min(new int[]{3,4,5,6,7,0,1,2}));
    System.out.println(min(new int[]{3,4,5,6,7,0,1,2}));
    System.out.println(min(new int[]{5,6,7,0,1,2,3,4}));
    System.out.println(min(new int[]{0,1,2,3,4,5,6,7}));
    System.out.println(min(new int[]{7,0,1,2,3,4,5,6}));
    System.out.println(min(new int[]{1,2,3,4,5,6,7,0}));
    System.out.println(min(new int[]{0}));
  }
}

Time cost O(logN), space cost O(1).

Implement int sqrt

Problem

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4

Output: 2

Example 2:

Input: 8

Output: 2

Explanation: The square root of 8 is 2.82842..., and since 

             the decimal part is truncated, 2 is returned.

Solution

The brutal force way is to try all the numbers i from 2 to x/2, if i*i <= x and (i+1) >x, i is the value. The cost O(N) can be reduced to O(logN) with binary search.

public class SqureRoot {
  public static int sqrt(int x) {
    if(x==1) return 1;
    if(x==2) return 1;
    //8
    int lo = 2;
    int hi = x/2;  //4
 
    while(lo < hi) {
      int mid = lo + (hi - lo)/2;//3
      int sqr = mid*mid;
      if(sqr < x) lo = mid+1;
      else if(sqr > x) hi = mid - 1;//2
      else return mid;
    }
    return lo;
  }

  public static void main(String...args) {
    System.out.println(sqrt(4));
    System.out.println(sqrt(8));
  }
}

The Time cost is O(logN), the space cost is O(1).

distance of binary tree node

Problem

Given 2 nodes on a binary search tree, find the distance of the two nodes. The distance is the minimum number of edges from one node to the other. 

For example: in the following binary search tree

             7

         /         \

       5           10

    /    \             \

  3       6           13

The distance of node 3 and 6 is 2, the distance of node 3 and 10 is 3.

Solution:

From root, we walk to node 3, the distance is 2, the distance from root to node 6 is 2 as well. The distance from root to 5 is 1, so the formula is: dist(7, 3) + dist(7, 6) - 2*dist(7,5).

The key is to find the common parent node of 3 and 6, which can be found during post order traversal.

class NodeDistance {
  private static class Node {
    int value;
    Node left;
    Node right;
    public Node(int value, Node left, Node right) {
      this.value = value;
      this.left = left;
      this.right = right;
    }
  }
  public static void main(String...args) {
    Node root = new Node(7, null, null);
    root.left = new Node(5, new Node(3, null, null), new Node(6, null, null));
    root.right = new Node(10, null, new Node(13, null, null));
    NodeDistance nd = new NodeDistance();
    System.out.println(nd.findDistance(root, 3, 6));
  }
  public int findDistance(Node root, int w, int v) {//13, 6
    Node common = findCommonParent(root, w, v);
    if(common == null) return 0;
    return dist(common, w) + dist(common, v);
  }
    /*
               7
         /         \
       5           10
    /    \             \
  3       6           13
  */
  private int dist(Node root, int target) {//5, 3
    if(root.value == target) return 0;
    else if(root.value < target) {
      return 1 + dist(root.right, target);
    } else {
      return 1 + dist(root.left, target);
    }
  }
 
  private Node findCommonParent(Node root, int w, int v) {//3, 6
    if(root == null || root.value == w || root.value == v) {
      return root;
    }
    Node lchild = findCommonParent(root.left, w, v);
    Node rchild = findCommonParent(root.right, w, v);
    if(lchild == null) {
      return rchild;
    } else if(rchild == null) {
      return lchild;
    } else {
      return root;
    }
  }
}

The time complexity is O(logN) and the space complexity is O(1)

Find first and last position

Problem

Given an ascending sorted integer array, find the first and last position of a target number. If target is not in the array, return [-1, -1]

For example, given an array [1, 3, 6, 8, 8, 9] and target 8, the program should output [3, 4], if the target is 6, the program should output [-1, -1]

Solution

Solution 1:

brutal force solution is to iterate the array, when the first match is found, we register the first position, then keep moving right, detect the first position that is not equal to target, then register the last position. A few edge conditions should be considered, such as the first and last positions are the same, the target is at the end of the array, the target is at the beginning of the array, the whole array only has target, the whole array is size 1 and 2.

class TargetFinder {
  private static final int TARGET = 8;
  public static int[] findFirstAndLast(int[] a) {
    int first = -1;
    int last = -1;
    for(int i = 0; i < a.length; i++) {
      if(a[i] == TARGET && first == -1) {
        first = i;
      }
      if(first != -1 && a[i] != TARGET) {
        last = i - 1;
        break;
      }
    }
    if(first != -1 && last == -1) last = a.length - 1;
    return new int[]{first, last};
  }
  public static void main(String...args) {
    int[] a = new int[]{5,7,7,8,8,10};
    int[] result = findFirstAndLast(a);
    System.out.println("[" + result[0] + "," + result[1] + "]");
  }
}

The time complexity is O(N) and space complexity is O(1)

Solution 2:

The array is sorted, so we don't have to iterate the array, we can do binary search. One strategy that will not work is to use binary search to find a match, then search left and right in order to detect the boundary. In case the whole array matches the target, the performance degrade to O(N). We need to use binary search to find both left and right boundary. The binary search won't stop when finding the target, it will continue until the boundary is detected.
....8 8 8 8...
    l         h
       m
When searching for left boundary, whenever mid hit target, we move hi to mid, then calculate the mid again. Repeat, until hi and lo point to the same position, the left boundary is found.

When searching for right boundary, whenever mid hit target, we move lo to mid, then calculate the mid again. Repeat, until hi and lo point to the same position, the left boundary is found.

class TargetFinder {
  private static final int TARGET = 8;
  //5,7,7,8,8,10
  //      l h
  //      m  (mid won't change)
  public static int findLast(int[] a) {
    int lo = 0;
    int hi = a.length - 1;
    int lastMid = Integer.MIN_VALUE;
    while(lo < hi) {
      int mid = lo + (hi - lo)/2; 
      if(lastMid == mid) mid++;  //lo + (1)/2 = lo special case, mid won't change, we need to break the dead loop
      if(a[mid] < TARGET) lo = mid + 1;
      else if(a[mid] > TARGET) hi = mid - 1;
      else {
        lo = mid;
      }
      lastMid = mid;
    }
    if(a[lo] == TARGET) return lo;
    else return -1;
  }
  //5,7,7,8,8,10
  //      l
  //           h
  //    m
  public static int findFirst(int[] a) {
    int lo = 0;
    int hi = a.length - 1;
    while(lo < hi) {
      int mid = lo + (hi - lo)/2;
      if(a[mid] < TARGET) lo = mid + 1;
      else if(a[mid] > TARGET) hi = mid - 1;
      else {
        hi = mid;
      }
    }
    if(a[lo] == TARGET) return lo;
    else return -1;
  }

  public static void main(String...args) {
    int[] a = new int[]{5,7,7,8,8,10};
    System.out.println("[" + findFirst(a) + "," + findLast(a) + "]");
  }
}

The time cost is O(logN), the space cost is O(1)