Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is not an extremely difficult question, but I always get TLE error (Time limit exceeded), before I realize that I have to use HashMap.

Solution

The solution is making use of HashMap and sorting to check anagrams. For more, read this blog.

My code

public class Solution {
    public List<String> anagrams(String[] strs) {
        List<String> ans = new ArrayList<String>();
        if (strs == null || strs.length == 0) {
            return ans;
        }
        HashMap<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str: strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String sorted = String.valueOf(chars);
            if (!map.containsKey(sorted)) {
                map.put(sorted, new ArrayList<String>());
            }
            map.get(sorted).add(str);
        }
        for (List<String> list: map.values()) {
            if (list.size() > 1) {
                ans.addAll(list);
            }
        }
        return ans;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This is an interesting question.

Most popular solution is DP. The explanation from this blog is slightly confusing, so I will explain it here. Basic idea is to do 2 iteration. First time get the heighest bound to the left of every point. Second time get the heighest bound to the right.

Example: input = [0,1,0,2,1,0,1,3,2,1,2,1].

Assume the 2 DP arrays are called highestLeftSoFar and highestRightSoFar.

highestLeftSoFar = 0,1,1,2,2,2,2,3,3,3,3,3

highestRightSoFar = 3,3,3,3,3,3,3,3,2,2,2,1

For each point, get the lowest bound (of the 2 bounds), and calculate water.

There is another solution making use of stack from this blog. This idea is IMHO not very good.

1. Use Stack to store the index of a bar;
2. If the current one is smaller then the top of the stack, push it to stack;
3. Otherwise, pop up the top until stack is empty or top is greater than the current one, add up the volume, push the current one to stack.

The tricky part is what is the volume to be added each time when we pop up a value from the stack.

My code

public class Solution {
    public int trap(int[] A) {
        if (A == null || A.length <= 1) {
            return 0;
        }
        int len = A.length;
        int[] leftBound = new int[len];
        for (int i = 1; i < len; i++) {
            leftBound[i] = Math.max(leftBound[i - 1], A[i - 1]);
        }
        int rightBound = 0;
        int water = 0;
        for (int i = len - 2; i > 0; i--) {
            rightBound = Math.max(rightBound, A[i + 1]);
            int contains = Math.min(leftBound[i], rightBound);
            // important to note, that contains can be 0!
            water += Math.max(0, contains - A[i]);
        }
        return water;
    }
}

Stack Solution.

public int trap(int[] A) {
    int cur = 0;
    while (cur < A.length && A[cur] == 0) cur ++;
    int vol = 0;
    Stack<Integer> stack = new Stack<Integer>();
    while (cur < A.length) {
        while (!stack.isEmpty() && A[cur] >= A[stack.peek()]) {
            int b = stack.pop();
            if (stack.isEmpty()) break;
            vol += ((cur - stack.peek() - 1) * (Math.min(A[cur], A[stack.peek()]) - A[b]));
        }
        stack.push(cur ++);
        cur ++;
    }
    return vol;
}

updated on Aug 27th, 2014, there is a very very good 2 pointer solution which reads the input only once!

This post wrote about it, and source code available.

public int trap(int[] A) {
    if (A == null || A.length == 0) {
        return 0;
    }

    int len = A.length;
    int left = 0;
    int right = len - 1;
    int leftHeight = 0;
    int rightHeight = 0;
    int water = 0;

    while (left < right) {
        leftHeight = Math.max(leftHeight, A[left]);
        rightHeight = Math.max(rightHeight, A[right]);
        // Two ways to write the following if-condition 
        // This would also work: if (A[left] < A[right]) {
        if (leftHeight < rightHeight) {
            // increase left pointer
            water += leftHeight - A[left];
            left++;
        } else {
            water += rightHeight - A[right];
            right--;
        }
    }
    return water;
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This is a very classic DFS search problem, and it is not easy.

The solution simply brute force DFS. Read more at this blog.

My code

public class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        int N = board.length;
        board = helper(board, N, 0, 0);
    }

    private char[][] helper(char[][] board, int N, int x, int y) {
        if (x == N) {
            return board;
        } else if (y == N) {
            return helper(board, N, x + 1, 0);
        } else if (board[x][y] != '.') {
            // made a mistake here with (y+1) instead of (x+1) 
            return helper(board, N, x, y + 1);
        } else {
            // put in from 1 to 9, and then check validation
            for (int i = 1; i <= 9; i++) {
                board[x][y] = (char) ('0' + i);
                if (isValid(board, x, y)) {
                    // if the number we just put in is valid inside the board
                    char[][] ans = helper(board, N, x, y + 1);
                    if (ans != null) {
                        return ans;
                    } else {
                        // putting in this number (i) will not work, so...
                        // put in next number and try, until 9
                    }
                }
                // this is important for backtarcking - set the char back to its original value!!! 
                board[x][y] = '.';
            }
        }
        // in fact, we can just return true/false for this question. 
        return null;
    }

    // this validation method we borrowed from my old code
    private boolean isValid(char[][] board, int i, int j) {
        boolean[] map = new boolean[9];
        for (int k = 0; k < 9; k++) 
            if (k != j && board[i][k] == board[i][j])
                return false;
        for (int k = 0; k < 9; k++) 
            if (k != i && board[k][j] == board[i][j])
                return false;
        for (int row = i / 3 * 3; row < i / 3 * 3 + 3; row++) 
            for (int col = j / 3 * 3; col < j / 3 * 3 + 3; col++) 
                if ((row != i || col != j) && board[row][col] == board[i][j])
                    return false;
        return true;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This question is easy, just swap numbers in place.

My code

public class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null) {
            return;
        }
        int N = matrix.length;
        // 5 - 2/3
        // 6 - 3/3
        int m = N / 2;
        int n = (N + 1) / 2;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // eg. N = 4, i = 0, j = 1
                // (0, 1) <- (2, 0)
                // (2, 0) <- (3, 2)
                // (3, 2) <- (1, 3)
                // (1, 3) <- (0, 1)
                int temp = matrix[i][j];
                matrix[i][j] = matrix[N - 1 - j][i];
                matrix[N - 1 - j][i] = matrix[N - 1 - i][N - 1 - j];
                matrix[N - 1 - i][N - 1 - j] = matrix[j][N - 1 - i];
                matrix[j][N - 1 - i] = temp;
            }
        }
    }
}

A cleaner version from this blog.

This code is very concise and beautiful, because it added the following 2 variables:

x = n-1-a

y = n-1-b

public void rotate(int[][] matrix) {
    for (int a = 0, x = matrix.length - 1; a < x; a++, x--) {
        for (int b = a, y = x; b < x; b++, y--) {
            int t = matrix[a][b];
            matrix[a][b] = matrix[y][a];
            matrix[y][a] = matrix[x][y];
            matrix[x][y] = matrix[b][x];
            matrix[b][x] = t;
        }
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This question is based on “Permutations”, plus duplication avoidance.

This question, together with “Permutations”, is very classic and frequent questions, thus the basis for many similar DFS problems. Read this blog for more.

The idea is when getting element from remaining list and add to current list, check for duplication. If the number occured before, skip operation. (Don’t forget sorting is required at first).

The key points to keep in mind:

1. Use another array to flag the ‘visited’ items
2. Check items with same value, and ONLY USE THE FIRST INSTANCE OF THE SAME VALUE. Which is to say, if current = previous, but previous is not visited, do not use current number.

My code

public class Solution {
    public List<List<Integer>> permuteUnique(int[] num) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (num == null || num.length == 0) {
            return ans;
        }
        int len = num.length;
        Arrays.sort(num);
        helper(ans, new ArrayList<Integer>(), num, len, new boolean[len]);
        return ans;
    }

    private void helper(List<List<Integer>> ans, List<Integer> path, int[] num, int len, boolean[] visited) {
        if (path.size() == len) {
            ans.add(new ArrayList<Integer>(path));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (i > 0 && num[i - 1] == num[i] && !visited[i - 1]) {
                // important: if previous number have same value as (i)th
                // but have never been visited, then skip current number
                continue;
            }
            if (!visited[i]) {
                path.add(num[i]);
                visited[i] = true;
                helper(ans, path, num, len, visited);
                path.remove(path.size() - 1);
                visited[i] = false;
            }
        }
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This is a very classic question.

One solution is to recursively push elements into a list, until all elements are pushed. Make use of a ‘visited’ array.

Another solution is using 2 nested for-loops to keep adding next elements. Read this post:

Loop through the array, in each iteration, a new number is added to different locations of results of previous iteration. Start from an empty List.

Keep in mind: this type of permutation questions always requires insert/delete before/after a recursion.

In case you are interested, there is a third solution, swap element method. It is also explained in the same post:

Swap each element with each element after it.

My code

Adding elements one by one (recommended)

public class Solution {
    public List<List<Integer>> permute(int[] num) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        if (num == null || num.length == 0) {
            return ans;
        }
        int len = num.length;
        Arrays.sort(num);
        helper(ans, new ArrayList<Integer>(), num, len, new boolean[len]);
        return ans;
    }

    private void helper(List<List<Integer>> ans, List<Integer> path, int[] num, int len, boolean[] visited) {
        if (path.size() == len) {
            ans.add(new ArrayList<Integer>(path));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (!visited[i]) {
                path.add(num[i]);
                visited[i] = true;
                helper(ans, path, num, len, visited);
                path.remove(path.size() - 1);
                visited[i] = false;
            }
        }
    }
}

The double nested for-loop method

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        //start from an empty list
        result.add(new ArrayList<Integer>());

        for (int i = 0; i < num.length; i++) {
            //list of list in current iteration of the array num
            ArrayList<ArrayList<Integer>> current = new ArrayList<ArrayList<Integer>>();

            for (ArrayList<Integer> l : result) {
                // # of locations to insert is largest index + 1
                for (int j = 0; j < l.size()+1; j++) {
                    // + add num[i] to different locations
                    l.add(j, num[i]);
                    ArrayList<Integer> temp = new ArrayList<Integer>(l);
                    current.add(temp);
                    l.remove(j);
                }
            }
            result = new ArrayList<ArrayList<Integer>>(current);
        }
        return result;
    }
}

The swap element method

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        permute(num, 0, result);
        return result;
    }

    void permute(int[] num, int start, ArrayList<ArrayList<Integer>> result) {

        if (start >= num.length) {
            ArrayList<Integer> item = convertArrayToList(num);
            result.add(item);
        }

        for (int j = start; j <= num.length - 1; j++) {
            swap(num, start, j);
            permute(num, start + 1, result);
            swap(num, start, j);
        }
    }

    private ArrayList<Integer> convertArrayToList(int[] num) {
        ArrayList<Integer> item = new ArrayList<Integer>();
        for (int h = 0; h < num.length; h++) {
            item.add(num[h]);
        }
        return item;
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

The basic idea is to multiple numbers 1 by 1, and do decimal carry later. Note the max length of result is (m+n) assuming 2 input are length m and n respectively.

The code seems easy, but be careful when converting result array into string. That is, we should omit preceding ‘0’s.

Read this blog for more.

My code

public class Solution {
    public String multiply(String num1, String num2) {
        if (num1 == null || num1.length() == 0) {
            return "0";
        } else if (num2 == null || num2.length() == 0) {
            return "0";
        }
        int len1 = num1.length();
        int len2 = num2.length();
        int len = len1 + len2;
        // eg. 99 * 999 = 98901
        int[] digits = new int[len];

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                // multiply the (i)th number from the end of num1
                // with the (j)th number from the end of num2
                int product = (num1.charAt(len1 - i) - '0') * (num2.charAt(len2 - j) - '0');
                // this produce saves to the (i+j-1)th position in array
                int ansPos = len + 1 - i - j;
                digits[ansPos] += product;
            }
        }
        // answer is got and saved in digits array, but we
        // need to handle the carry numbers
        for (int i = len - 1; i > 0; i--) {
            digits[i - 1] += digits[i] / 10;
            digits[i] %= 10;
        }
        // last step is the print the answer, but mind the prefix 0s
        int p = 0;
        while (p < len && digits[p] == 0) {
            p++;
        }
        if (p == len) {
            return "0";
        } else {
            StringBuilder sb = new StringBuilder();
            while (p < len) {
                sb.append(String.valueOf(digits[p++]));
            }
            return sb.toString();
        }
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This is a DP problem. But we do not have to save all values into a DP array.

A analysis of DP solution from this blog explains it very well:

Search forward, and see for each node of array, what is the current maximum place we can reach, and every time we reach a local maximum, we add counter by 1, if we can reach the terminal, just return the counter.

It’s easy to get “time limit exceed” if you solve this problem like a traditional DP question.

So I come up with a solution using 2 pointers: ‘left’ and ‘right’ that denotes the boundary that can be jumps to within a certain number of jumps. What I need to do is updating the 2 pointers and increase the counter for number of jumps.

My code

traditional DP

public class Solution {
    public int jump(int[] A) {
        int len = A.length;
        if (len <= 1) return 0;
        int[] dp = new int[len];
        if (A[0] == 0) return 0;
        int cur = 1;
        for (int i = 0; i < len; i ++) {
            if (i != 0 && dp[i] == 0) 
                return 0;
            // array dp represent the steps to reach point i
            for (; cur < len && cur <= i + A[i]; cur ++) {
                dp[cur] = dp[i] + 1;
            }
            if (dp[len - 1] != 0) 
                return dp[len - 1];
        }
        return 0;
    }
}

DP without array (recommended)

public class Solution {
    public int jump(int[] A) {
        if (A == null || A.length <= 1) {
            return 0;
        }
        int len = A.length;
        // note that this is a DP question, but considering the required out, 
        // we do not need dp array (i.e.) 
        // int[] dp = new int[len];

        int jumps = 0;
        int left = 0;
        int right = 0;

        while (right < len) {
            int reachable = right;
            jumps++;
            for (int i = left; i <= right; i++) {
                reachable = Math.max(reachable, i + A[i]);
            }
            if (reachable == right) {
                // unable to jump forward
                return -1;
            }
            if (reachable >= len - 1) {
                return jumps;
            } else {
                left = right + 1;
                right = reachable;
            }
        }
        return -1;
    }
}

non-DP

public class Solution {
    public int jump(int[] A) {
        if (A == null || A.length <= 1) {
            return 0;
        }
        int len = A.length;
        // note that this is a DP question, but considering the required out, 
        // we do not need dp array (i.e.) 
        // int[] dp = new int[len];

        int jumps = 0;
        int left = 0;
        int right = 0;

        while (right < len) {
            int reachable = right;
            jumps++;
            for (int i = left; i <= right; i++) {
                reachable = Math.max(reachable, i + A[i]);
            }
            if (reachable == right) {
                // unable to jump forward
                return -1;
            }
            if (reachable >= len - 1) {
                return jumps;
            } else {
                left = right + 1;
                right = reachable;
            }
        }
        return -1;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a very difficult question!

The tricky part of this question is the limit in space/time. If we sort and check, the space is constent, but time is increased.

The key is to make use of the position index of the array.

Solution

Make sure that (i)th item of the array stores value (i+1). The image below and the quoted text from this blog are very good explanations.

The idea is simple. What is the most desired array we want to see? Something like [1,2,3] then we know 4 is missing, or [1, 8, 3, 4] then we know 2 is missing. In other word, “all the numbers are in their correct positions”.

What are correct positions? For any i, A[i] = i+1. So our goal is to rearrange those numbers (in place) to their correct positions.

We then need to decide how to arrange them. Let’s take the [3, 4, -1, 1] as an example. The 1st number, 3, we know it should stay in position 2. So we swap A[0] = 3 with A[2]. We then get [-1, 4, 3, 1]. We can’t do anything about -1 so we leave it there. The 2nd number, 4, we know it should sit in A[3]. So we swap A[1] = 4 with A[3]. We then get [-1, 1, 3, 4]. Now 1 should stay in A[0], so we keep swapping and we get [1, -1, 3, 4]. Notice now every positive number is staying in their correct position (A[0]=1, A[2]=3 and A[3]=4). We then need one more scan to find out 2 is missing.

My code

public class Solution {
    public int firstMissingPositive(int[] A) {
        if (A == null || A.length == 0) {
            return 1;
        }
        int len = A.length;
        int p = 0;
        while (p < len) {
            if (A[p] == p + 1) {
                // the number is in its correct position~
                p++;
                continue;
            } else if (A[p] <= 0 || A[p] > len) {
                // the number is out of range, leave it alone then.
                p++;
                continue;
            } else if (A[p] == A[A[p] - 1]) {
                // this is an important case!!! I missed it just now~
                p++;
                continue; 
            }
            swop(A, p, A[p] - 1);
        }
        // now check and find the first number that is not in correct position
        p = 0;
        while (p < len) {
            if (A[p] != p + 1) {
                return p + 1;
            }
            p++;
        }
        return p + 1;
    }

    private void swop(int[] A, int x, int y) {
        int temp = A[x];
        A[x] = A[y];
        A[y] = temp;
    }
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This is a implementation question, not difficult.

My code

code 1

public class Solution {
    public String countAndSay(int n) {
        String num = "1";
        for (int i = 1; i < n; i++) {
            num = say(num);
        }
        return num;
    }

    private String say(String input) {
        // 21 -> 1211
        int len = input.length();
        String output = "";
        int left = 0;
        int right = 0;
        while (right < len) {
            left = right;
            // forward right until right pointer to a different value
            // compared to that pointed by left pointer
            while (right < len && input.charAt(left) == input.charAt(right)) {
                right++;
            }
            output += String.valueOf(right - left);
            output += input.charAt(left);
        }
        return output;
    }
}

code 2

public String countAndSay(int n) {
    String s = "1";
    for (int i = 2; i <= n; i ++) {
        char[] nums = s.toCharArray();
        String newS = "";
        int len = nums.length, left = 0, right = 0;
        while (right < len) {
            while (right < len && nums[left] == nums[right]) right ++;
            newS += (right - left) + "" + nums[left];
            left = right;
        }
        s = newS;
    }
    return s;
}