Roman to Integer

/*

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

*/

//time: O(n), space:O(1)
public class Solution {
    public int romanToInt(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int res = map.get(s.charAt(s.length() - 1));
        for (int i = s.length() - 2; i >= 0; i--) {
            if (map.get(s.charAt(i)) >= map.get(s.charAt(i + 1))) {
                res += map.get(s.charAt(i));
            } else {
                res -= map.get(s.charAt(i));
            }
        }
        return res;
    }
}

Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

//DFS, time:O(n^2), space:O(1)
public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        subsetsHelper(nums, ans, new ArrayList<Integer>(), 0);
        return ans;
    }
    public void subsetsHelper(int[] nums, List<List<Integer>> ans,                                 List<Integer> list, int start) {
        ans.add(new ArrayList<Integer>(list));
        for (int i = start; i < nums.length; i++) {
            list.add(nums[i]);
            subsetsHelper(nums, ans, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}


/*
bfs:
First, adding an empty list to the ans, then iterate the input array, each time adding the number to all the existed subsets. The new subsets and the previous subsets together make up the new ans. 

time:O(n^2), space:O(1)
*/

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ans;
        }
        List<Integer> list = new ArrayList<>();
        ans.add(list);
        for (int i = 0; i < nums.length; i++) {
            int size = ans.size();
            for (int j = 0; j < size; j++) {
                list = new ArrayList<>(ans.get(j));
                list.add(nums[i]);
                ans.add(list);
            }
        }
        return ans;
    }
}

Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

/*

A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Also, we can use three pointers with one pass solution. In each step during the iteration, we do either of three things. Swap with the left, swap with the right, or move forward.

time:O(n), space:O(1)

*/

public class Solution {

    public void sortColors(int[] nums) {

        if (nums == null || nums.length == 0) {

            return;

        }

        int left = 0;

        int right = nums.length - 1;

        int i = 0;

        while (i <= right) {

            if (nums[i] == 1) {

                i++;

            } else if (nums[i] == 0) {

                swap(nums, left, i); 

                left++;

                i++;

            } else {

                swap(nums, right, i);

                right--;

            }

        }

    }

    public void swap(int[] nums, int a, int b) {

        int tmp = nums[a];

        nums[a] = nums[b];

        nums[b] = tmp;

    }

}

Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

/**
 * Definition for undirected graph.
 * class UndirectedGraphNode {
 *     int label;
 *     List<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { 
 *        label = x; 
 *        neighbors = new ArrayList<UndirectedGraphNode>(); 
 *     }
 * };
 */

/*
Use Queue to implement BFS and use HashMap to deep clone every graph node and connect their neighbors.

time:O(V+E), space:O(V), E is the number of neighbors, V is the number of nodes.
*/

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        queue.offer(node);
        map.put(node, new UndirectedGraphNode(node.label));
        while (!queue.isEmpty()) {
            UndirectedGraphNode curr = queue.poll();
            for (UndirectedGraphNode neighbor : curr.neighbors) {
                if (!map.containsKey(neighbor)) {
                    queue.offer(neighbor);
                    map.put(neighbor, new UndirectedGraphNode(neighbor.label));
                }
                map.get(curr).neighbors.add(map.get(neighbor));
            }
        }
        return map.get(node);
    }
}


//DFS, time:O(V+E), space:O(V)
public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
        Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
        return deepClone(map, node);
    }
    public UndirectedGraphNode deepClone(Map<UndirectedGraphNode,                                              UndirectedGraphNode> map, UndirectedGraphNode node) {
        if (node == null) {
            return null;
        }
        if (map.containsKey(node)) {
            return map.get(node);
        }
        map.put(node, new UndirectedGraphNode(node.label)); 
        for (UndirectedGraphNode neighbor : node.neighbors) {
            map.get(node).neighbors.add(deepClone(map, neighbor));
        }
        return map.get(node);
    }

}

First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

/* The isBadVersion API is defined in the parent class VersionControl.

      boolean isBadVersion(int version); */

/*

time:O(logn), space:O(1)

*/

public class Solution extends VersionControl {

    public int firstBadVersion(int n) {

        if (n <= 0) {

            return 0;

        }

        int left = 1;

        int right = n;

        while (left + 1 < right) {

            int mid = left + (right - left) / 2;

            if (isBadVersion(mid)) {

                right = mid;

            } else {

                left = mid;

            }

        }

        if (isBadVersion(left)) {

            return left;

        }

        return right;

    }

}

Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

/**

 * Your BSTIterator will be called like this:

 * BSTIterator i = new BSTIterator(root);

 * while (i.hasNext()) v[f()] = i.next();

 */

/**

 * Definition for binary tree

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

/*

Every time, we call next(), we will traverse to find the left most TreeNode of the current node if existed. If the current node is null, then we pop out a node from the stack and return its value. The first time we call next(), it takes O(h) time, but the other TreeNode in the stack will take only O(1) time when call the next(). And there are h TreeNode in the stack. So the average time complexity will be O(1) and space complexity will be O(h).

hasNext() and next(): time:O(1), space:O(h)

*/

public class BSTIterator {

    public Stack<TreeNode> stack = new Stack<>();

    public TreeNode root;

    public BSTIterator(TreeNode root) {

        this.root = root;

    }

    /** @return whether we have a next smallest number */

    public boolean hasNext() {

        return root != null || !stack.isEmpty();

    }

    /** @return the next smallest number */

    public int next() {

        while (root != null) {

            stack.push(root);

            root = root.left;

        }

        root = stack.pop();

        TreeNode node = root;

        root = root.right;

        return node.val;

    }

}

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

/*
BFS traversal, 
time:O(n), space:O(n)
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while(!queue.isEmpty()) {
            depth++;
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ans.add(list);
        }
        return ans;
    }
}

Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the empty string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

/*

Set an array to record the number of each character in string t. Use two pointers to iterate string s, when the substring in string s contains string t, if the length of the substring is smaller than the previous recorded length, update the minimum window substring. Then move forward the left pointer and continue to check if the new substring contains string t.

time:O(n), space:O(1)

*/

public class Solution {

    public String minWindow(String s, String t) {

        if (s == null || s.length() == 0 || t == null) {

            return "";

        }

        int[] map = new int[256];

        for (char ch : t.toCharArray()) {

            map[ch]++; 

        }

        int i = 0;

        int j = 0;

        int count = t.length();

        int length = Integer.MAX_VALUE;

        String res = "";

        for (i = 0; i < s.length() - t.length() + 1; i++) {

            while (j < s.length() && count > 0) {

                if (map[s.charAt(j)]-- > 0) {

                    count--;

                }

                j++;

            }

            if (count == 0 && j - i < length) {

                length = j - i;

                res = s.substring(i, j);

            }

            if (map[s.charAt(i)]++ == 0) {

                count++;

            }

        }

        return res;

    }

}

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:

11110
11010
11000
00000

Answer: 1

/*

When find one land, increment the number of lands, then use DFS/BFS to find all the adjacent lands. In order to avoid duplicate, set each land just found to be water, like set '1' to '0'.

*/

//DFS, time:O(m*n), space:O(1)

public class Solution {

    public int numIslands(char[][] grid) {

        if (grid == null || grid.length == 0 || 

            grid[0] == null || grid[0].length == 0) {

            return 0;

        }

        int m = grid.length;

        int n = grid[0].length;

        int count = 0;

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (grid[i][j] == '0') {

                    continue;

                }

                count++;

                dfs(grid, i, j);

            }

        }

        return count;

    }

    public void dfs(char[][] grid, int i, int j) {

        if (i < 0 || i >= grid.length || 

            j < 0 || j >= grid[0].length) {

            return;

        }

        if (grid[i][j] == '1') {

            grid[i][j] = '0';

            dfs(grid, i + 1, j);

            dfs(grid, i, j + 1);

            dfs(grid, i - 1, j);

            dfs(grid, i, j - 1);

        }

    }

}

//BFS, time:O(m*n), space:O(m*n)

public class Solution {

    public int numIslands(char[][] grid) {

        if (grid == null || grid.length == 0 || 

            grid[0] == null || grid[0].length == 0) {

            return 0;

        }

        int m = grid.length;

        int n = grid[0].length;

        int count = 0;

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (grid[i][j] == '0') {

                    continue;

                }

                count++;

                bfs(grid, i, j);

            }

        }

        return count;

    }

    public void bfs(char[][] grid, int i, int j) {

        int m = grid.length;

        int n = grid[0].length;

        int[] dx = {1, 0, -1, 0};

        int[] dy = {0, 1, 0, -1};

        Queue<Integer> queue = new LinkedList<>();

        queue.offer(i * n + j);

        grid[i][j] = '0';

        while (!queue.isEmpty()) {

            int index = queue.poll();

            for (int k = 0; k < 4; k++) {

                int nx = index / n + dx[k];

                int ny = index % n + dy[k];

                if (nx < 0 || nx >= m || ny < 0 || ny >= n) {

                    continue;

                }

                if (grid[nx][ny] == '0') {

                    continue;

                }

                queue.offer(nx * n + ny);

                grid[nx][ny] = '0';

            }

        }

    }

}

Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

Example

sqrt(3) = 1

sqrt(4) = 2

/*

time:O(logn), space:O(1)

*/

public class Solution {

    public int mySqrt(int x) {

        if (x == 0) {

            return 0;

        }

        int left = 0;

        int right = x;

        while (left + 1 < right) {

            int mid = left + (right - left) / 2;

            if (mid < x / mid) {

                left = mid;

            } else {

                right = mid;

            }

        }

        if (right <= x / right) {

            return right;

        }

        return left;

    }

}