Pacific Atlantic Water Flow

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

1. The order of returned grid coordinates does not matter.
2. Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  1   2   2   3  (5) *
       ~  3   2   3  (4) (4) *
       ~  2   4  (5)  3   1  *
       ~ (6) (7)  1   4   5  *
       ~ (5)  1   1   2   4  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

I thought at first that we can use DP, from the boarders search till the other end. It turns out that DP will miss some of the cases. Here we should use DFS. Using two different boolean matrix for pacific and atlantic, then starting from boarders and visiting all possible flows (low -> high because we start from boarder). In the end if the point is true for both matrices, we add it to result.

public class Solution {
    private static final int dx[] = {0, 0, -1, 1};
    private static final int dy[] = {1, -1, 0, 0}; 

    public List pacificAtlantic(int[][] matrix) {
        List rst = new ArrayList();
        if (matrix.length == 0 || matrix[0].length == 0) {
            return rst;
        }
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        
        boolean pacific[][] = new boolean[rows][cols];
        boolean atlantic[][] = new boolean[rows][cols];
        
        for(int i = 0; i < rows ;i++){
            flow(pacific, matrix, i, 0);
            flow(atlantic, matrix,i, cols - 1);
        }
        for(int j = 0; j < cols; j++){
            flow(pacific, matrix, 0, j);
            flow(atlantic,matrix, rows - 1, j);
        }
        for(int i = 0;i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(pacific[i][j] && atlantic[i][j])
                    rst.add(new int[] {i, j});
            }
        }
        return rst;

    }
    
    private void flow(boolean visited[][],int matrix[][],int x,int y){
        visited[x][y] = true;
        for(int i = 0;i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && nx < matrix.length && ny >= 0 && ny < matrix[0].length
            && !visited[nx][ny] && matrix[nx][ny] >= matrix[x][y]){
                flow(visited, matrix, nx, ny);
            }
        }
    }
}

UTF-8 Validation

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

1. For 1-byte character, the first bit is a 0, followed by its unicode code.
2. For n-bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.

This is how the UTF-8 encoding would work:

   Char. number range  |        UTF-8 octet sequence
      (hexadecimal)    |              (binary)
   --------------------+---------------------------------------------
   0000 0000-0000 007F | 0xxxxxxx
   0000 0080-0000 07FF | 110xxxxx 10xxxxxx
   0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
   0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Given an array of integers representing the data, return whether it is a valid utf-8 encoding.

Note:
The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

Example 1:

data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.

Return true.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

Example 2:

data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.

Return false.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

There should be lots of ways to do it. Mine is a very straightforward one: change input integer to binary strings and follow the encoding rules and check all numbers.

public boolean validUtf8(int[] data) {
        if (data.length == 0) {
            return false;
        }
        int len = data.length;
        String[] bytes = new String[len];
        for (int i = 0; i < len; i++) {
            int num = data[i];
            //1 byte should be at most 255
            if (num > 255) {
                return false;
            }
            bytes[i] = Integer.toBinaryString(num);
            //use 0 to make up bits
            while (bytes[i].length() < 8) {
                bytes[i] = "0" + bytes[i];
            }
        }
        
        int pos = 0;
        int leftLength = len;
        while (pos < len && leftLength > 0) {
            String currByte = bytes[pos];
            int n = 0;
            if (currByte.charAt(0) == '0') {
                //supposed to be 1 bit
                n = 1;
                pos++;
            } else {
                while (n < currByte.length() && currByte.charAt(n) == '1') {
                    n++;
                }
                if (n == 1) {
                    return false;
                }
                //Left bit strings in the array should at least be n
                if (leftLength < n) {
                    return false;
                }
                int curr = 1;
                pos++;
                while (curr < n) {
                    if (!"10".equals(bytes[pos].substring(0, 2))) {
                        return false;
                    }
                    curr++;
                    pos++;
                }
            }
            leftLength -= n;
        }
        return true;
    }

Is Subsequence

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:
s = "abc", t = "ahbgdc"

Return true.

Example 2:
s = "axc", t = "ahbgdc"

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Go through the string and whenever pass all chars that don't match. In the end a subsequence of the string should reach to the end.

public boolean isSubsequence(String s, String t) {
        int lenS = s.length(), lenT = t.length();
        if (lenS == 0) {
            return true;
        }
        if (lenS > lenT) {
            return false;
        }
        
        int posS = 0, posT = 0;
        while (posS < lenS && posT < lenT) {
            while (posT < t.length() && t.charAt(posT) != s.charAt(posS)) {
                posT++;
            }
            posS++;
            posT++;
        }
        return posS == lenS;
    }

Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Based on the problem, we know if the sum of all elements in the array is odd, we cannot partition it to two equal subsets. So we first sum up all elements and check if the sum is even. After we pass the first check, our problem becomes if we can find a subset with sum half of the sum of all elements. Now we use DP. Here I iterate from target to a element, this is necessary because each number can only be used once, also it can help us to avoid some of the unnecessary iteration.

public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return false;
        }
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        if (sum % 2 != 0) {
            return false;
        }
        sum = sum / 2;
        boolean[] sums = new boolean[sum + 1];
        sums[0] = true;
        
        for (int n : nums) {
            for (int i = sum; i >= n; i--) {
                sums[i] |= sums[i - n];
            }
        }
        return sums[sum];
    }

Ternary Expression Parser

Given a string representing arbitrarily nested ternary expressions, calculate the result of the expression. You can always assume that the given expression is valid and only consists of digits 0-9, ?, :, T andF (T and F represent True and False respectively).

Note:

1. The length of the given string is ≤ 10000.
2. Each number will contain only one digit.
3. The conditional expressions group right-to-left (as usual in most languages).
4. The condition will always be either T or F. That is, the condition will never be a digit.
5. The result of the expression will always evaluate to either a digit 0-9, T or F.

Example 1:

Input: "T?2:3"

Output: "2"

Explanation: If true, then result is 2; otherwise result is 3.

Example 2:

Input: "F?1:T?4:5"

Output: "4"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(F ? 1 : (T ? 4 : 5))"                   "(F ? 1 : (T ? 4 : 5))"
          -> "(F ? 1 : 4)"                 or       -> "(T ? 4 : 5)"
          -> "4"                                    -> "4"

Example 3:

Input: "T?T?F:5:3"

Output: "F"

Explanation: The conditional expressions group right-to-left. Using parenthesis, it is read/evaluated as:

             "(T ? (T ? F : 5) : 3)"                   "(T ? (T ? F : 5) : 3)"
          -> "(T ? F : 3)"                 or       -> "(T ? F : 5)"
          -> "F"                                    -> "F"

The idea is that for ternary expression, calculating forward or backward leads to the same result. If we calculate forwardly, it would be hard to calculate the nested expressions. The idea is to use a stack, whenever we see a "?", we calculate result and push the correct result in to the stack. Otherwise we push it to the stack.

public String parseTernary(String expression) {
        if (expression.length() == 0) {
            return "";
        }
        Stack<character> stack = new Stack<>();
        int len = expression.length();
        for (int i = len - 1; i >= 0; i--) {
            char c = expression.charAt(i);
            if (!stack.isEmpty() && stack.peek() == '?') {
                stack.pop(); //?
                char first = stack.pop();
                stack.pop(); //:
                char second = stack.pop();
                if (c == 'T') {
                    stack.push(first);
                } else {
                    stack.push(second);
                }
            } else {
                stack.push(c);
            }
        }
        return "" + stack.pop();
    }

Word Squares

Given a set of words (without duplicates), find all word squares you can build from them.

A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

For example, the word sequence ["ball","area","lead","lady"] forms a word square because each word reads the same both horizontally and vertically.

b a l l
a r e a
l e a d
l a d y

Note:

1. There are at least 1 and at most 1000 words.
2. All words will have the exact same length.
3. Word length is at least 1 and at most 5.
4. Each word contains only lowercase English alphabet a-z.

Example 1:

Input:
["area","lead","wall","lady","ball"]

Output:
[
  [ "wall",
    "area",
    "lead",
    "lady"
  ],
  [ "ball",
    "area",
    "lead",
    "lady"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Example 2:

Input:
["abat","baba","atan","atal"]

Output:
[
  [ "baba",
    "abat",
    "baba",
    "atan"
  ],
  [ "baba",
    "abat",
    "baba",
    "atal"
  ]
]

Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Very interesting problem. Let's explain by an example, consider we have 3 words in the list and we are trying to find the forth word. Based on the definition of word square, we know the prefix of the forth word should be the same as the forth character of each existing word in the list. e.g., :

wal | l
are  | a
lea  | d


Now all we need to do is find all words with prefix "lad", which is backtracking. A better way to search prefix is to use trie (no surprise). And that's it.

public class WordSquares {


    public List<List<String>> wordSquares(String[] words) {
        List<List<String>> rst = new ArrayList<>();
        if (words.length == 0) {
            return rst;
        }
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        List<String> curr = new ArrayList<>();
        int len = words[0].length();
        for (String word : words) {
            curr.add(word);
            search(rst, trie, curr, len);
            curr.remove(curr.size() - 1);
        }
        return rst;
    }

    private void search(List<List<String>> rst, Trie trie, List<String> curr, int len) {
        if (curr.size() == len) {
            rst.add(new ArrayList<>(curr));
            return;
        }
        String prefix = "";
        int index = curr.size();
        for (String word : curr) {
            prefix += word.charAt(index);
        }
        List<String> startsWith = trie.prefixWith(prefix);
        for (String next : startsWith) {
            curr.add(next);
            search(rst, trie, curr, len);
            curr.remove(curr.size() - 1);
        }
    }

    private class Trie {
        TrieNode root;
        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            TrieNode node = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (node.children[c - 'a'] == null) {
                    node.children[c - 'a'] = new TrieNode(c);
                }
                node = node.children[c - 'a'];
            }
            node.isWord = true;
        }

        public List<String> prefixWith(String prefix) {
            List<String> rst = new ArrayList<>();
            TrieNode node = root;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);
                if (node.children[c - 'a'] == null) {
                    return rst;
                }
                node = node.children[c - 'a'];
            }
            return node.prefixWith(prefix);
        }
    }





    private class TrieNode {
        char c;
        TrieNode[] children;
        boolean isWord;


        public TrieNode() {
            children = new TrieNode[26];
            isWord = false;
        }

        public TrieNode(char c) {
            this();
            this.c = c;
        }

        public List<String> prefixWith(String prefix) {
            List<String> rst = new ArrayList<>();
            if (isWord) {
                rst.add(prefix);
            }
            for (TrieNode child : children) {
                if (child != null) {
                    rst.addAll(child.prefixWith(prefix + child.c));
                }
            }
            return rst;
        }
    }
}

Longest Absolute File Path

Suppose we abstract our file system by a string in the following manner:

The string "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext" represents:

dir
    subdir1
    subdir2
        file.ext

The directory dir contains an empty sub-directory subdir1 and a sub-directory subdir2 containing a file file.ext.

The string "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" represents:

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

The directory dir contains two sub-directories subdir1 and subdir2. subdir1 contains a file file1.ext and an empty second-level sub-directory subsubdir1. subdir2contains a second-level sub-directory subsubdir2 containing a file file2.ext.

We are interested in finding the longest (number of characters) absolute path to a file within our file system. For example, in the second example above, the longest absolute path is"dir/subdir2/subsubdir2/file2.ext", and its length is 32 (not including the double quotes).

Given a string representing the file system in the above format, return the length of the longest absolute path to file in the abstracted file system. If there is no file in the system, return0.

Note:

• The name of a file contains at least a . and an extension.
• The name of a directory or sub-directory will not contain a ..

Time complexity required: O(n) where n is the size of the input string.

Notice that a/aa/aaa/file1.txt is not the longest file path, if there is another path aaaaaaaaaaaaaaaaaaaaa/sth.png.

The idea is just calculating the length of the absolute path of each file. We split the string by "\n". Then for each string, if we see a "\t", we know its a new depth, so we remove the tab and increment the depth. If we see "." in the string, we know it's a file, we calculate the path by adding its parent directory length to itself. If it's not a file, we record the length using a list, and by adding its parent directory length to itself. Since the directory is ordered, we go deep to the first file, then return back to another directory, like DFS. So overwritten a dir will not impact the total length.

public int lengthLongestPath(String input) {
        if (input.length() == 0) {
            return 0;
        }
        int maxLen = 0;
        String[] dirs = input.split("\\n");
        List depths = new ArrayList<>();
        depths.add(0);
        for (String line : dirs) {
            int depth = 0;
            while (line.charAt(0) == '\t') {
                line = line.substring(1);
                depth++;
            }
            if (line.indexOf('.') > 0) {
                maxLen = Math.max(maxLen, line.length() + depths.get(depth));
            } else {
                if (depth <= depths.size() - 2) {
                    depths.set(depth + 1, depths.get(depth) + line.length() + 1);
                } else {
                    depths.add(depths.get(depth) + line.length() + 1);
                }
            }
        }
        return maxLen;
    }