Algorithm - LeetCode Problems 20

Problem 222. Count Complete Tree Nodes

• Given the root of a complete binary tree, return the number of the nodes in the tree.

• According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

• Design an algorithm that runs in less than O(n) time complexity.

Examples

• Example 1:
  • Input: root = [1,2,3,4,5,6]
  • Output: 6

• Example 2:
  • Input: root = []
  • Output: 0

Constraints:

• The number of nodes in the tree is in the range [0, 5 * 10^4].
• 0 <= Node.val <= 5 * 10^4
• The tree is guaranteed to be complete.

solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var countNodes = function(root) {
    if (!root) return 0;
    
  	let count = 1;
    count += countNodes(root.left);
    count += countNodes(root.right);
    
  	return count;
};

Problem 1905. Count Sub Islands

• You are given two m x n binary matrices grid1 and grid2 containing only 0's (representing water) and 1's (representing land). An island is a group of 1's connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.

• An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.

• Return the number of islands in grid2 that are considered sub-islands.

Examples

• Example 1:
  • Input: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
  • Output: 3
  • Explanation:
    • In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
    • The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.

• Example 2:
  • Input: grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
  • Output: 2
  • Explanation:
    • In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
    • The 1s colored red in grid2 are those considered to be part of a sub-island. There are two sub-islands.

Constraints:

• m == grid1.length == grid2.length
• n == grid1[i].length == grid2[i].length
• 1 <= m, n <= 500
• grid1[i][j] and grid2[i][j] are either 0 or 1.

Solution

/**
 * @param {number[][]} grid1
 * @param {number[][]} grid2
 * @return {number}
 */
var countSubIslands = function(grid1, grid2) {
    const M = grid2.length;
    const N = grid2[0].length;
    let count = 0;
    let isSubIsland = true;

    const dfs = (row, col) => {
        if (row < 0 || row >= M || col < 0 || col >= N || grid2[row][col] === 0) {
            return;
        }

        if (grid1[row][col] === 0) {
            isSubIsland = false;
            return;
        }

        grid1[row][col] = 0;
        grid2[row][col] = 0;
        
        dfs(row + 1, col);
        dfs(row - 1, col);
        dfs(row, col + 1);
        dfs(row, col - 1);
    };

    for (i = 0; i < M; i++) {
        for (j = 0; j < N; j++) {
            isSubIsland = true;
            
            if (grid2[i][j] === 1) {
                dfs(i, j);
                
                if (isSubIsland) {
                    count++;
                }
            }
        }
    }

    return count;
};

Problem 647. Palindromic Substrings

• Given a string s, return the number of palindromic substrings in it.

• A string is a palindrome when it reads the same backward as forward.

• A substring is a contiguous sequence of characters within the string.

Examples

• Example 1:

  • Input: s = "abc"
  • Output: 3
  • Explanation: Three palindromic strings: "a", "b", "c".

• Example 2:

  • Input: s = "aaa"
  • Output: 6
  • Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Constraints

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

Solution

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
    let count = 0;

    const countPalindrome = (str, start, end) => {
        while (start >= 0 && end < str.length && str[start] === str[end]) {
            start--;
            end++;
            count++;
        }
    };

    for (let i = 0; i < s.length; i++) {
        countPalindrome(s, i, i); // odd-length palindromes
        countPalindrome(s, i, i+1); // even-length palindromes
    }

    return count;
};