Algorithm - LeetCode Problems 7

Problem 605. Can Place Flowers

• You have a long flowerbed in which some of the plots are planted, and some are not.

• However, flowers cannot be planted in adjacent plots.

• Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.

Examples

• Example 1:

  • Input: flowerbed = [1,0,0,0,1], n = 1
  • Output: true

• Example 2:

  • Input: flowerbed = [1,0,0,0,1], n = 2
  • Output: false

Constraints:

• 1 <= flowerbed.length <= 2 * 10^4
• flowerbed[i] is 0 or 1.
• There are no two adjacent flowers in flowerbed.
• 0 <= n <= flowerbed.length

Solution

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
    for (let i = 0; i < flowerbed.length && n > 0; i++) {
        if (!flowerbed[i- 1] && !flowerbed[i] && !flowerbed[i+1]) {
            flowerbed[i] = 1;
            n--;
        }
    }

    return n === 0;
};

Problem 695. Max Area of Island

• You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

• The area of an island is the number of cells with a value 1 in the island.

• Return the maximum area of an island in grid. If there is no island, return 0.

Example

• Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
• Output: 6
• Explanation: The answer is not 11, because the island must be connected 4-directionally.

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• grid[i][j] is either 0 or 1.

Solution

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxAreaOfIsland = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    let maxArea = 0;

    const bfs = (rowIndex, colIndex) => {
        const dx = [1, -1, 0, 0];
        const dy = [0, 0, 1, -1];
        let area = 0;
        const queue = [[rowIndex, colIndex]];

        while (queue.length) {
            const [row, col] = queue.shift();
            grid[row][col] = 0;
            area += 1;

            for (let i = 0; i < dx.length; i++) {
                const nextRow = row + dx[i];
                const nextCol = col + dy[i];

                if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && grid[nextRow][nextCol]) {
                    queue.push([nextRow, nextCol]);
                    grid[nextRow][nextCol] = 0;
                }
            }
        }

        return area;
    };

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j]) {
                maxArea = Math.max(maxArea, bfs(i, j));
            }
        }
    }

    return maxArea;
};

Problem 1323. Maximum 69 Number

• You are given a positive integer num consisting only of digits 6 and 9.

Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).

Example

• Example 1:

  • Input: num = 9669
  • Output: 9969
  • Explanation:
    • Changing the first digit results in 6669.
    • Changing the second digit results in 9969.
    • Changing the third digit results in 9699.
    • Changing the fourth digit results in 9666.
    • The maximum number is 9969.

• Example 2:

  • Input: num = 9996
  • Output: 9999
  • Explanation:
    • Changing the last digit 6 to 9 results in the maximum number.

Constraints

• 1 <= num <= 10^4
• num consists of only 6 and 9 digits.

Solution

/**
 * @param {number} num
 * @return {number}
 */
var maximum69Number  = function(num) {
    const numStr = num.toString();
    const maxNumStr = numStr.replace('6', '9');
    return parseInt(maxNumStr);
};