# 20200304

Given a string, find the length of the longest substring without repeating characters.

Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.

Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
// K : V
// p : 1
// w : 1
// k : 1
w.iscontains in map
currently lenght = 2

abcabcbb
l
h
result

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length == 0)
        return 0;
        
    Map<Charcater, Integer> map = new HashMap<>();
    int low = 0;
    int result = 0;
    for (int high = 0; high < s.lenght; high++) {
        if (map.containsKey(s.charAt(high)) {
            low = Math.max(low, map.get(s.charAt(high)));
        }
        result = Math.max(result, high - low + 1);
        map.put(s.charAt(high), high + 1);
    }
    
    return result;
}

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:
Input: [[7,10],[2,4]]
Output: 1

0---------------------30
5-----10
15---20

[[2,4], [7,10]]

start = 2, 7
end = 4, 10
room = 1

[[0, 30], [5, 10], [15, 20]]
start = 0, 5, 15
end = 10, 20, 30
room = 2

public int minMeetingRooms(int[][] intervals) {
    int[] start = new int[intervals.length];
    int[] end = new int[intervals.length];
     for (int i = 0; i < intervals.length; i++) {
        start[i] = intervals[i][0];
        end[i] = intervals[i][1];
     }
    Arrays.sort(start);
    Arrays.sort(end);
    
    int result = 0;
    int endPointer = 0
    for (int i = 0; i < start.length; i++) {
        if (start[i] < end[endPointer]) {
            result++;
        } else {
            endPointer++;
        }
    }
    
    return result;
}

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples 1:

Input: [3,9,20,null,null,15,7]

   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7 

Output:

[
  [9],
  [3,15],
  [20],
  [7]
]

  Input: [3,9,8,4,0,1,7]

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7 

Output:

[
  [4],
  [9],
  [3,0,1],
  [8],
  [7]
]


Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0's right child is 2 and 1's left child is 5)

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7
    /\
   /  \
   5   2

Output:

[
  [4],      (-2)
  [9,5],    (-1)
  [3,0,1],  (0)
  [8,2],    (1)
  [7]       (2)
]

4
9 5
3 0 1
8 2
7

public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null)
        return result;
        
    Map<Integer, List<Integer>> map = new HashMap<>();
    Queue<TreeNode> nodeQueue = new LinkedList<>();
    Queue<Integer> idxQueue = new LinkedList<>();
    
    // int min = 0;
    // int max = 0;
    
    nodeQueue.offer(root);
    idxQueue.offer(0);
    while (!nodeQueue.isEmpty()) {
        TreeNode node = nodeQueue.poll();
        int idx = idxQueue.poll();
        
        if (!map.containsKey(idx)) {
            map.put(idx, new ArrayList<>());
        }
        map.get(idx).add(node.val);
        
        if (node.left != null) {
            nodeQueue.offer(node.left);
            idxQueue.offer(idx - 1);
           // min = Math.min(min, idx - 1);
        }
        if (node.right != null) {
            nodeQueue.offer(node.right);
            idxQueue.offer(idx + 1);
           // max = Math.max(max, inx + 1);
        }
    }
    
//    for (int i = min; i < max; i++) {
//        result.add(map.get(i));
//    }
    
    for (List<Integer> value: map.values()) {
        result.add(value);
    }
    
    return result;
}