[Leetcode] Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Analysis:

The idea is very simple: Just Preorder visit the tree and for each node, treat it as root and count the number of path which is equal to sum. There should be a better way to remove the duplicate visit?  

    int helper(TreeNode root, int sum, int total) {
        if (root == null)
            return 0;
        else {
            total += root.val;
            int count = sum == total ? 1 : 0;
            count += helper(root.left, sum, total);
            count += helper(root.right, sum, total);
            return count;
        }
    }
    
    public int pathSum(TreeNode root, int sum) {
        if (root == null)
            return 0;
        else {
            int count = helper(root, sum, 0);
            return count + pathSum(root.left, sum) + pathSum(root.right, sum);
        }
    }

[Leetcode] Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Analysis:

One intuitive solution is to iterate all the substring of length p.length() and compare whether the substring is an anagram of p by sorting both substring and p and compare. Unfortunately, it will be time out for big data set since the running time would be O(n*n*klog(k) where n is the length of s and k is the length of p.

Think again how we know two strings are the anagram: we can either sort the two string, or we can count each letters of the string and compare whether the count of each letters are equal. So, for s, we first get the count of each letter of the substring of first p.length() characters.Then, whenever move a letter forward one letter,  we just need to change the count by removing 1 count of the first letter and adding 1 count of the last letter. The running time would be O(n+k) since equals function takes constant time. 

    boolean equals(int[] a, int[] b) {
        for(char c = 'a'; c<='z'; c++) {
            if (a[c] != b[c])
                return false;
        }
        return true;
    }
    
    public List<Integer> findAnagrams(String s, String p) {
        int[] pCount = new int[256];
        for(char c: p.toCharArray())
            pCount[c]++;
            
        int[] sCount = new int[256];
        for(int i=0; i<p.length() && i < s.length(); i++)
            sCount[s.charAt(i)]++;
        
        List<Integer> list = new ArrayList<>();
        if (equals(pCount, sCount))
            list.add(0);
        
        for(int i= p.length(); i < s.length(); i++) {
            sCount[s.charAt(i)]++;
            sCount[s.charAt(i-p.length())]--;
            if (equals(pCount, sCount))
                list.add(i-p.length() + 1);
        }
        return list;
    }

[Leetcode] 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.

Analysis:

The problem to have the two subset whose sums are equal is the same as the problem to find a subset whose sum is half of the total of the array which is a typical 0,1 knapsack problem: for a given nums[i], if it is included in the subset, then dp[i][j] = dp[i-1][j - nums[i]], otherwise, dp[i][j] = dp[i-1][j]. The dp transition function is  dp[i][j] = dp[i-1][j] || (j >=nums[i-1] && dp[i-1][j-nums[i-1]]). We can also write the dp algorithm with one dimension array:  dp[j] = dp[j] || (j >=nums[i-1] && dp[j-nums[i-1]]); 

Two dimension array:

    public boolean canPartition(int[] nums) {
        int total = 0;
        for(int i = 0; i<nums.length; i++)
            total += nums[i];
            
        if (total %2 != 0)
            return false;
        
        int target= total / 2;
        boolean[][] dp = new boolean[nums.length+1][target+1];
        dp[0][0] = true;
        for(int i=1; i<=nums.length; i++) {
            for(int j=1; j<=target; j++) {
                dp[i][j] = dp[i-1][j] || (j >=nums[i-1] && dp[i-1][j-nums[i-1]]); 
            }
        }
        return dp[nums.length][target];
    }

One dimension array:

public boolean canPartition(int[] nums) {
        int total = 0;
        for(int i = 0; i<nums.length; i++)
            total += nums[i];
            
        if (total %2 != 0)
            return false;
        
        int target= total / 2;
        boolean[] dp = new boolean[target+1];
        dp[0] = true;
        for(int i=1; i<=nums.length; i++) {
            for(int j=target; j >=0 ;j--) {
                dp[j] = dp[j] || (j >=nums[i-1] && dp[j-nums[i-1]]); 
            }
        }
        return dp[target];
    }

[Leetcode] 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).

Analysis:

Initially, I was trying to iterate all position, and for each position (i,j) use DFS to see whether it can reach both Atlantic and Pacific but unfortunately it is TLE. For each position, the worst case is to visit all node of the matrix and takes O(m*n) time. So for total m*n node it takes O((m*n)^2).

If we think the problem the other way, if a position (i,j) can reach both Pacific and Atlantic, it mean there must be Pacific position (pi, pj) and Atlantic (ai, ai) which connect to (i, j). In another word, (i, j) must be in the DFS/BFS search path beginning from (pi, pj) and (ai, aj). So, if we can find all the node which can be reached from Pacific edge (row or column is 0) and Atlantic (row or column is maximum), these node are the position where water can flow to both the Pacific and Atlantic ocean.

void dfs(int[][] matrix, boolean[][] visited, int pre, int x, int y) {
        if (x < 0 || x >= matrix.length || y <0 || y >= matrix[0].length || visited[x][y] ||  matrix[x][y] < pre)
            return;
        
        visited[x][y] = true;

        dfs(matrix, visited, matrix[x][y], x-1, y);
        dfs(matrix, visited, matrix[x][y], x+1, y);
        dfs(matrix, visited, matrix[x][y], x, y-1);
        dfs(matrix, visited, matrix[x][y], x, y+1);

    }
    
    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> list = new ArrayList<>();
        if (matrix.length == 0)
            return list;
        int m = matrix.length; 
        int n = matrix[0].length;
        
        boolean[][] dp1 = new boolean[m][n];
        boolean[][] dp2 = new boolean[m][n];
        for(int i=0; i<m; i++) {

            //Pacific
            dfs(matrix, dp1, Integer.MIN_VALUE, i, 0);

            //Atlantic
            dfs(matrix, dp2, Integer.MIN_VALUE, i, n-1);
        }
        
        for(int i=0; i<n; i++) {
            dfs(matrix, dp1, Integer.MIN_VALUE, 0, i);
            dfs(matrix, dp2, Integer.MIN_VALUE, m-1, i);
        }
    
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if (dp1[i][j] && dp2[i][j]) {
                    int[] pos = {i,j};
                    list.add(pos);
                }
            }
        }
    
        
        return list;
    }

[Leetcode] Battleships in a Board

Given an 2D board, count how many different battleships are in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may assume the following rules:

• You receive a valid board, made of only battleships or empty slots.
• Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
• At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

Example:

X..X
...X
...X

In the above board there are 2 battleships.

Invalid Example:

...X
XXXX
...X

This is not a valid board - as battleships will always have a cell separating between them.

Your algorithm should not modify the value of the board.

Analysis:

At the very first glance, it looks like a BFS/DFS to find the group of connected nodes. But it has the limit that all the battleships have to be in the same row or column. In addition, it has the limit that the board cannot be changed, which means you cannot mark the board as visited or not.

Given that the battleship must be in the same row or column, we can simply check all rows and columns and count it if it is a valid battleship. For each row, we need to collect the number of battleships, which is nothing but the same as finding the number of word separated by space. Notice that you need to check whether the battleship is valid or not by checking whether it has upper or down row battleship connected. Similarly we can get the battleships for the columns, except that for the battleship occupying only one space which has been collected by the row already, so no need to recollected.

Comparing to other solutions, this solution is able to take care of the invalid board as well. 

    int getColCount(char[][] board, int k) {
        int m = board.length;
        int n = board[0].length;
        int i = 0;
        int count = 0;
        while(i < m) {
            while(i < m && board[i][k] == '.')
                i++;

            boolean valid = true;
            int c = 0;
            while(i < m && board[i][k] == 'X') {
                if ((k > 0 && board[i][k-1] == 'X') || (k < n-1 && board[i][k+1] == 'X'))
                    valid = false;
                i++;
                c++;
            }

            //exclude the single node
            if (valid && c > 1)
                count++;
        }
        
        return count;
    }
    
    
    int getRowCount(char[][] board, int k) {
        int m = board.length;
        int n = board[0].length;
        int i = 0;
        int count = 0;
        while(i < n) {
            while(i <n && board[k][i] == '.')
                i++;

            boolean valid = true;
            int c = 0;
            while(i <n && board[k][i] == 'X') {
                if ((k > 0 && board[k-1][i] == 'X') || (k < m-1 && board[k+1][i] == 'X'))
                    valid = false;
                i++;
                c++;
            }
            if (valid && c > 0)
                count++;
        }
        
        return count;
    }
    
    public int countBattleships(char[][] board) {
        int count = 0;
        if (board.length == 0)
            return 0;
            
        for(int i=0; i<board.length; i++)
            count+= getRowCount(board, i);

        for(int i=0; i<board[0].length; i++)
            count+= getColCount(board, i);        
        
        return count;
    }

[Leetcode] Longest Repeating Character Replacement

Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.

Note:
Both the string's length and k will not exceed 104.

Example 1:

Input:
s = "ABAB", k = 2

Output:
4

Explanation:
Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input:
s = "AABABBA", k = 1

Output:
4

Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

Analysis:

The basic idea is to iterate all substring which could satisfy the condition.  That is, the substring would become repeating character string if k characters were replaced. If we have count of all substring characters, we know that the maximum number of characters to be replaced = the total number of characters - the max number of any single letter. It would takes O (n^2 * k) time.

We can improve the performance. Notice that if substring(i, j) is a repeating character string and substring(i, j+1) is not, then all substring(i, j+n) will not be a repeating character as well. So we have to increase the i to have another repeating character substring. It is actual a slide window and takes O(n*k) time. 

    int getCount(Map<Character, Integer> m, int k) {
        
        int maxVal = 0;
        int total = 0;
        
        for(Character c: m.keySet()) {
            total += m.get(c);
            maxVal = Math.max(maxVal, m.get(c));
        }

        if (total - maxVal > k)
            return -1;
        
        return total;
    }

    public int characterReplacement(String s, int k) {
        int ret = 0;
        int i = 0;
        int j = 0;

        Map<Character, Integer> m = new HashMap<>();
        while(j < s.length()) {
            m.put(s.charAt(j), m.getOrDefault(s.charAt(j), 0) + 1);
            int count = getCount(m, k);
            //if not satisfied, shrink the windows by increasing i
            if (count < 0) {
                while(i < j && count < 0) {
                    m.put(s.charAt(i), m.get(s.charAt(i)) - 1);
                    count = getCount(m, k);
                    i++;
                }
            }
            ret = Math.max(ret, count);
            j++;
        }
        
        return ret;
    }