# 20191211

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Input: "()"
Output: true

Input: "()[]{}"
Output: true

Input: "(]"
Output: false

Input: "([)]"
Output: false

Input: "{[]}"
Output: true

Input: "}{"
Output:

 public boolean isValid(String s) {
        if (s.length() == 1) return false;
        Stack<Character> stack = new Stack();
    
        char[] charArray = s.toCharArray();
        for (char c : charArray) {
           if (c == '(' || c == '[' || c == '{') {
               stack.push(c);
           } else if (!stack.isEmpty()){
              char p = stack.pop();
              if (c == ')' && p != '(' ) {
                 return false;
              } else if (c == ']' && p != '[' ) {
                 return false;
              } else if (c == '}' && p != '{' ){
                return false;
              }
           } else {
              return false;
           }
        }
    return stack.isEmpty();
    }

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (c == ')' && !stack.isEmpty() && stack.peak() == '(') {
            stack.pop();
        } else if (c == ']' && !stack.isEmpty() && stack.peak() == '[') {
            stack.pop();
        } else if (c == '}' && !stack.isEmpty() && stack.peak() == '{') {
            stack.pop();
        } else {
            return false;
        }
    }
    
    return stack.isEmpty();
}

Number of Islands
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000
Output: 1

Example 2:

Input:
[[1,1,0,0,0],
 [1,1,0,0,0],
 [0,0,1,0,0],
 [0,0,0,1,1]]
Output: 3

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) {
        return 0;
    }
    
    int count = 0;
    int n = grid.length;
    int m = grid[0].length;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j, n, m);
                count++;
            }
        }
    }
    
    return count;
}

public void dfs(char[][] grid, int i, int j, int n, int m) {
    if (i >= n || j >= m || i < 0 || j < 0 || grid[i][j] == '0')
        return;
    
    grid[i][j] = '0';
    dfs(grid, i + 1, j, n, m);
    dfs(grid, i - 1, j, n, m);
    dfs(grid, i, j + 1, n, m);
    dfs(grid, i, j - 1, n, m);
}

Example:
Input: [2,1,5,6,2,3]
Output: 10

 public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            for (int j = i; j < heights.length; j++) {
                int minheight = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++)
                    minheight = Math.min(minheight, heights[k]);
                maxarea = Math.max(maxarea, minheight * (j - i + 1));
            }
        }
        return maxarea;
    }
}

public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxarea = 0;
        for (int i = 0; i < heights.length; ++i) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
                maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
            stack.push(i);
        }
        while (stack.peek() != -1)
            maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() -1));
        return maxarea;
    }

[1,1,1]
[1,1,0]
[1,0,1]

sr=1 sc=1 newcolor=2

public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
    if (image[sr][sc] == newColor) return image;
  
    dfs(image, sr, sc, newColor, image[sr][sc]);
    return image;
}

private void dfs(int[][] image, int sr, int sc, int newColor, int target) {
   if (sr < 0 || sr >= image.length || sc < 0 || sc >= image[0].length || image[sr][sc] != target) return;
   
   image[sr][sc] = newColor;
   dfs(image, n, m, sr + 1, sc, newColor, target);
   dfs(image, n, m, sr - 1, sc, newColor, target);
   dfs(image, n, m, sr, sc + 1, newColor, target);
   dfs(image, n, m, sr, sc - 1, newColor, target);
}