<commit_before>## 329. Longest Increasing Path in a Matrix

### Description

```
Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
```

### Solution

1. Start from every node to do dfs.
2. If `matrix[x][y]<=previousVal`, then reject by returning -1
3. Plus one distance of current node
4. Use `distance` array to store the distance of current node in case it's been calculated before. Since a node can be right of left node, left of right node, down of upper node and up of down node, at most can be dfs and calculated 4 times.
5. Must check if this val bigger than previous one before checking distance[x][y] to avoid a >= number making use of the start node of real Longest Increasing Path.

```
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix.length == 0)  return 0;
        int[][] distance = new int[matrix.length][matrix[0].length];
        int max = 0;
        for(int i=0; i<matrix.length; i++){
            for(int j=0; j<matrix[0].length; j++){
                max = Math.max(max, dfs(matrix, i, j, Long.MIN_VALUE, distance));
            }
        }
        return max;
    }
    private int dfs(int[][] matrix, int x, int y, long previousVal, int[][] distance){
        if(x<0 || x>=matrix.length || y<0 || y>=matrix[0].length)   return -1;
        if(matrix[x][y]<=previousVal)                               return -1;
        if(distance[x][y]!=0)                                       return distance[x][y];
        int max = 0;
        int val = matrix[x][y];
        max = Math.max(max, dfs(matrix, x-1, y, val, distance));
        max = Math.max(max, dfs(matrix, x+1, y, val, distance));
        max = Math.max(max, dfs(matrix, x, y-1, val, distance));
        max = Math.max(max, dfs(matrix, x, y+1, val, distance));
        int ans = max+1;
        distance[x][y] = ans;
        return ans;
    }
}
```

Time: O(m*n). Suppose one dfs visits every node, then it just goes further enough, say m*n is length of its Longest Increasing Path, then every dfs is calculated. Then the m*n-1 dfs each takes O(1) by `distance[x][y]`. So the time complexity is m*n+(m*n-1)*1 = O(m*n). The idea is similiar to other case where one dfs not visiting all nodes. It takes only O(m*n) to compute distance for each slot in m*n try. So it's m*n+m*n, basically O(m*n). Just like the idea of m+n in dijkstra algo.
Space: O(m*n), the distance array is m*n in shape.

## 109. Convert Sorted List to Binary Search Tree

### Description

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5
```

### First Solution - get length and find middle

buildTree recursively, find length and then middle node(this takes space O(1), build a list as index will take space O(n)), build root node with it, assign left list to buildTree(), `root.left = buildTree(leftList)`, the same as right list.

```
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head);
    }
    private TreeNode buildTree(ListNode head){
        int length = getLength(head);
        if(length==0)   return null;
        if(length==1){
            head.next = null;
            return new TreeNode(head.val);
        }
        ListNode cur = head;
        ListNode pre = null;
        for(int i=0; i<length/2; i++){
            pre = cur;
            cur = cur.next;
        }
        pre.next = null;
        TreeNode root = new TreeNode(cur.val);
        TreeNode treeNode = root;
        root.left = buildTree(head);
        root.right = buildTree(cur.next);
        return root;
    }
    private int getLength(ListNode head){
        ListNode cur = head;
        int length = 0;
        while(cur!=null){
            length++;
            cur=cur.next;
        }
        return length;
    }
}
```

Time: O(nlogn)
Space: O(1)

### Second Solution - use list to find middle by O(1)


Time: O(n)
Space: O(n)

### Final Solution

Idea: Doing inorder traversal on binary search tree will get ascending sort list. Therefor simulate inorder traversal will work to build binary search tree now that I already have ascendingly sorted array.



```
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private ListNode curListNode;<commit_msg>2019-06-14 new posts<commit_after>## 329. Longest Increasing Path in a Matrix

### Description

```
Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:

Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
```

### Solution

1. Start from every node to do dfs.
2. If `matrix[x][y]<=previousVal`, then reject by returning -1
3. Plus one distance of current node
4. Use `distance` array to store the distance of current node in case it's been calculated before. Since a node can be right of left node, left of right node, down of upper node and up of down node, at most can be dfs and calculated 4 times.
5. Must check if this val bigger than previous one before checking distance[x][y] to avoid a >= number making use of the start node of real Longest Increasing Path.

```
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix.length == 0)  return 0;
        int[][] distance = new int[matrix.length][matrix[0].length];
        int max = 0;
        for(int i=0; i<matrix.length; i++){
            for(int j=0; j<matrix[0].length; j++){
                max = Math.max(max, dfs(matrix, i, j, Long.MIN_VALUE, distance));
            }
        }
        return max;
    }
    private int dfs(int[][] matrix, int x, int y, long previousVal, int[][] distance){
        if(x<0 || x>=matrix.length || y<0 || y>=matrix[0].length)   return -1;
        if(matrix[x][y]<=previousVal)                               return -1;
        if(distance[x][y]!=0)                                       return distance[x][y];
        int max = 0;
        int val = matrix[x][y];
        max = Math.max(max, dfs(matrix, x-1, y, val, distance));
        max = Math.max(max, dfs(matrix, x+1, y, val, distance));
        max = Math.max(max, dfs(matrix, x, y-1, val, distance));
        max = Math.max(max, dfs(matrix, x, y+1, val, distance));
        int ans = max+1;
        distance[x][y] = ans;
        return ans;
    }
}
```

Time: O(m*n). Suppose one dfs visits every node, then it just goes further enough, say m*n is length of its Longest Increasing Path, then every dfs is calculated. Then the m*n-1 dfs each takes O(1) by `distance[x][y]`. So the time complexity is m*n+(m*n-1)*1 = O(m*n). The idea is similiar to other case where one dfs not visiting all nodes. It takes only O(m*n) to compute distance for each slot in m*n try. So it's m*n+m*n, basically O(m*n). Just like the idea of m+n in dijkstra algo.
Space: O(m*n), the distance array is m*n in shape.

## 109. Convert Sorted List to Binary Search Tree

### Description

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5
```

### First Solution - get length and find middle

buildTree recursively, find length and then middle node(this takes space O(1), build a list as index will take space O(n)), build root node with it, assign left list to buildTree(), `root.left = buildTree(leftList)`, the same as right list.

```
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        return buildTree(head);
    }
    private TreeNode buildTree(ListNode head){
        int length = getLength(head);
        if(length==0)   return null;
        if(length==1){
            head.next = null;
            return new TreeNode(head.val);
        }
        ListNode cur = head;
        ListNode pre = null;
        for(int i=0; i<length/2; i++){
            pre = cur;
            cur = cur.next;
        }
        pre.next = null;
        TreeNode root = new TreeNode(cur.val);
        TreeNode treeNode = root;
        root.left = buildTree(head);
        root.right = buildTree(cur.next);
        return root;
    }
    private int getLength(ListNode head){
        ListNode cur = head;
        int length = 0;
        while(cur!=null){
            length++;
            cur=cur.next;
        }
        return length;
    }
}
```

Time: O(nlogn)
Space: O(1)

### Second Solution - use list to find middle by O(1)


Time: O(n)
Space: O(n)

### Final Solution - Simulate inorder traversal

Idea: Doing inorder traversal on binary search tree will get ascending sort list. Therefor simulate inorder traversal will work to build binary search tree now that I already have ascendingly sorted array.

Start building the tree recursively using inorder traversal, only set the val when it's visiting the node in the second time. Use global curListNode, and set it to its next after using the val. Use start and end index to check if it's leaf node.

```
left=build(start, mid)
root=new TreeNode(this.cur.val) // mid
right=build(mid+1, end)
```

```
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private ListNode curListNode;
{'fraction_non_alphanumeric': 0.11717957389245857, 'fraction_numerical': 0.016486303686168415, 'mean_word_length': 2.5780399274047188, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4370043', 'n_tokens_mistral': 3814, 'n_tokens_neox': 3681, 'n_words': 1468}