Array traversal coding pattern

498. Diagonal Traverse

https://leetcode.com/problems/diagonal-traverse/description/

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

Approach # Diagonal Iteration and Reversal

Let’s change the traversal as below to keep it simple.

1. The first row and the last column in this problem would serve as the starting point for the corresponding diagonal.
2. Given an element inside a diagonal, say [i,j], we can either go up the diagonal by going one row up and one column ahead i.e. [i−1,j+1] or, we can go down the diagonal by going one row down and one column to the left i.e. [i+1,j−1].

Following would be steps.

1. Initialize a ans array that we will eventually return.
2. We would have an outer loop that will go over each of the diagonals one by one.
3. We then have an inner while loop that iterates over all the elements in the diagonal.
4. For odd numbered diagonals, we simply need to add the elements in our intermediary array, in reverse order to the final result array.

Following is code for reference.

/**
 * @param {number[][]} mat
 * @return {number[]}
 */
var findDiagonalOrder = function (mat) {
    const m = mat.length;
    const n = mat[0].length;
    const ans = [];
    const starting = [];
    for (let j = 0; j < n; j++) {
        starting.push([0, j]);
    }
    for (let i = 1; i < m; i++) {
        starting.push([i, n - 1]);
    }
    // Now traverse each 
    let order = 0;
    for (const [x, y] of starting) {
        let i = x;
        let j = y;
        const local = [];
        while (i < m && j >= 0) {
            local.push(mat[i][j]);
            i++;
            j--;
        }
        if (order % 2 === 0) {
            local.reverse();
        }
        ans.push(...local);
        order++;
    }
    return ans;
};

We can further optimize code to run in one pass as below.

/**
 * @param {number[][]} mat
 * @return {number[]}
 */
var findDiagonalOrder = function (mat) {
    const m = mat.length;
    const n = mat[0].length;
    const ans = [];

    // we have to go over all the elements in the first row and the last column to cover all possible diagonals
    for (let d = 0; d < m + n - 1; d++) {
        const local = [];
        // The elements in teh first row and the last colum are the respective heads
        let i = d < n ? 0 : d - n + 1;
        let j = d < n ? d : n - 1;
        while (i < m && j >= 0) {
            local.push(mat[i][j]);
            i++;
            j--;
        }
        // Reverse even numbered diagonal
        if (d % 2 === 0) {
            local.reverse();
        }
        // Copy into ans
        ans.push(...local)
    }
    return ans;
};

1424. Diagonal Traverse II

https://leetcode.com/problems/diagonal-traverse-ii/

Given a 2D integer array nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]

Approach #1: Scan from starting positions (TLE)

/**
 * @param {number[][]} nums
 * @return {number[]}
 */
var findDiagonalOrder = function (nums) {
    const m = nums.length;
    const n = Math.max(...nums.map(a => a.length));
    const starting = [];
    const ans = [];
    for (let i = 0; i < m; i++) {
        starting.push([i, 0]);
    }
    for (let j = 1; j < n; j++) {
        starting.push([m - 1, j])
    }

    // Traverse from starting nodes
    for (const [i, j] of starting) {
        let x = i;
        let y = j;
        while (x >= 0 && y < n) {
            if (nums[x][y] > 0) {
                ans.push(nums[x][y]);
            }
            x--;
            y++;
        }
    }
    return ans;
};

Approach #2: Group Elements by the Sum of Row and Column Indices

Q. How do you get to the next value in the diagonal?

Ans. By going up, you move to row - 1. By going right, you move to col + 1. For each square, we will use the sum row + col as an identifier to the diagonal that it belongs to.

/**
 * @param {number[][]} nums
 * @return {number[]}
 */
var findDiagonalOrder = function (nums) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < nums[i].length; j++) {
            const diagonal = i + j;
            if (!map.has(diagonal)) {
                map.set(diagonal, []);
            }
            map.get(diagonal).push(nums[i][j]);
        }
    }
    // Build ans 
    const ans = [];
    let key = 0;
    while (map.has(key)) {
        ans.push(...map.get(key).reverse());
        key++;
    }
    return ans;
};

766. Toeplitz Matrix

https://leetcode.com/problems/toeplitz-matrix/description

Given an m x n matrix, return true if the matrix is Toeplitz. Otherwise, return false.

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same elements.

Example 1:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

Approach 1# Apply diagonal traversing

Similar to above problem, we can run the diagonal traversing and verify the same element. If not then return false.

Following is code for reference.

/**
 * @param {number[][]} matrix
 * @return {boolean}
 */
var isToeplitzMatrix = function (matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const starting = [];
    for (let i = 0; i < m; i++) {
        starting.push([i, 0]);
    }
    for (let j = 1; j < n; j++) {
        starting.push([0, j]);
    }
    // Run diagonal scan
    for (const [x, y] of starting) {
        const pivot = matrix[x][y];
        let i = x;
        let j = y;
        while (i < m && j < n) {
            if (pivot !== matrix[i][j]) {
                return false;
            }
            i++;
            j++;
        }
    }
    return true;
};

Approach 2: Group by Category

1. As per geometry, a slope of line between two co-ordinates (x1,y1) and (x2,y2) is defined by m=(y2-y1)/(x2-x1)
2. If slope of line is at 45 degree then m==1 , it means y2-y1=x2-x1
3. If apply same rule for two cells on diagonal lines in the matrix is only possible if r2-r1=c2-c1 i.e. r1-c1=r2-c2
4. It means if use HashMap and group i-j then if there is mismatch then it is not a Toeplitz.

Following is code for reference.

/**
 * @param {number[][]} matrix
 * @return {boolean}
 */
var isToeplitzMatrix = function (matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const map = new Map();
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            const key = i - j;
            if (!map.has(key)) {
                map.set(key, matrix[i][j]);
            } else if (map.get(key) != matrix[i][j]) {
                return false;
            }
        }
    }
    return true;
};

Approach 3: Compare With Top-Left Neighbor

1. Every cell at (i,j) , previous diagonally cell exists at (i-1,j-1) .
2. It means we can simply compare runtime and if mismatch then return false.

Following is code for reference.

/**
 * @param {number[][]} matrix
 * @return {boolean}
 */
var isToeplitzMatrix = function (matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i > 0 && j > 0 && matrix[i][j] !== matrix[i - 1][j - 1]) {
                return false;
            }
        }
    }
    return true;
};

48. Rotate Image

https://leetcode.com/problems/rotate-image/description

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Approach #1: Rotate group of four cells

Observe how the cells move in groups when we rotate the image.

Let’s take following example and state of moving cells.

Following is code for reference

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function (matrix) {
    var n = matrix.length;
    for (var i = 0; i < Math.floor((n + 1) / 2); i++) {
        for (var j = 0; j < Math.floor(n / 2); j++) {
            var temp = 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] = matrix[i][j];
            matrix[i][j] = temp;
        }
    }
};

54. Spiral Matrix

https://leetcode.com/problems/spiral-matrix/description/

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Approach

1. We have possible directions as [right, down, left, up]
2. We keep a counter variable and if exhausted then increment the value.
3. The direction will be calculated by counter%4 position in the list of directions.
4. To track the visited node; we can modify the cell with value of 101 as we have limit of cell as -100 <= matrix[i][j] <= 100

Following is code for reference.

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    const VISITED = 1001; // As per -100 <= matrix[i][j] <= 100
    const ans = [];
    const m = matrix.length;
    const n = matrix[0].length;
    let counter = 0;
    const dfs = ([i, j]) => {
        ans.push(matrix[i][j]);
        matrix[i][j] = VISITED; 
        const [p, q] = directions[counter % 4];
        const x = i + p;
        const y = j + q;
        // if next node is already visited or not in rnage then change direction
        if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] === VISITED) {
            // recalculate next node by chaning direction
            counter++;
            const [a, b] = directions[counter % 4];
            const c = i + a;
            const d = j + b;
            // if next node is already visited then stop traversing
            if (c < 0 || c >= m || d < 0 || d >= n || matrix[c][d] === VISITED) {
                return;
            }
            return dfs([c, d]);
        }

        // call for next node with same counter
        dfs([x, y]);
    }
    dfs([0, 0]);
    return ans;
};

59. Spiral Matrix II

https://leetcode.com/problems/spiral-matrix-ii/description/

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

Example 1:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

Approach

Use the counter to fill the cell.

/**
 * @param {number} n
 * @return {number[][]}
 */
var generateMatrix = function (n) {
    const ans = new Array(n).fill(0).map(a => new Array(n).fill(-1));
    let counter = 0;
    let value = 1;
    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    const dfs = (i, j) => {
        ans[i][j] = value++;
        const [p, q] = dirs[counter % 4];
        const x = i + p;
        const y = j + q;
        // if next node is already visited or not in rnage then change direction
        if (x < 0 || x >= n || y < 0 || y >= n || ans[x][y] !== -1) {
            // recalculate next node by chaning direction
            counter++;
            const [a, b] = dirs[counter % 4];
            const c = i + a;
            const d = j + b;
            // if next node is already visited then stop traversing
            if (c < 0 || c >= n || d < 0 || d >= n || ans[c][d] !== -1) {
                return;
            }
            return dfs(c, d);
        }
        return dfs(x, y);
    }
    dfs(0, 0);
    return ans;
};

885. Spiral Matrix III

https://leetcode.com/problems/spiral-matrix-iii

You start at the cell (rStart, cStart) of an rows x cols grid facing east. The northwest corner is at the first row and column in the grid, and the southeast corner is at the last row and column.

You will walk in a clockwise spiral shape to visit every position in this grid. Whenever you move outside the grid’s boundary, we continue our walk outside the grid (but may return to the grid boundary later.). Eventually, we reach all rows * cols spaces of the grid.

Return an array of coordinates representing the positions of the grid in the order you visited them.

Example 1:

Input: rows = 5, cols = 6, rStart = 1, cStart = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

Approach

1. Initially, we are located at the coordinates rStart and cStart and must make our first movement toward the East.
2. Let’s simulate the clockwise movement and note the distances moved with each direction to identify any patterns:

• Move 1 unit towards the East.
• Move 1 unit towards the South.
• Move 2 units towards the West.
• Move 2 units towards the North.
• Move 3 units towards the East.
• Move 3 units towards the South.
• Move 4 units towards the West.
• Move 4 units towards the North.
• and so on…

We observe a pattern where distances are covered in pairs of directions, increasing the distance by 1 after each pair. Specifically, we move in the order of East, South, West, and North, increasing the distance after every pair.

Following is code for reference.

/**
 * @param {number} rows
 * @param {number} cols
 * @param {number} rStart
 * @param {number} cStart
 * @return {number[][]}
 */
var spiralMatrixIII = function (rows, cols, rStart, cStart) {
    const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    const traversed = new Array(rows * cols).fill(0).map(a => new Array(2).fill(0));
    let index = 0;
    // Initial step size is 1, value of d represents the current direction
    let step = 1;
    let direction = 0;
    while (index < rows * cols) {
        // direction = 0 -> East
        // direction = 1 -> South
        // direction = 2 -> West
        // direction = 3 -> North
        for (let i = 0; i < 2; i++) { // Scan directions in pair
            for (let j = 0; j < step; j++) {
                // Validate the current position
                if (rStart >= 0 && rStart < rows && cStart >= 0 && cStart < cols) {
                    traversed[index][0] = rStart;
                    traversed[index][1] = cStart;
                    index++;
                }
                // Make changes to the current position
                rStart += dirs[direction][0];
                cStart += dirs[direction][1];
            }
            // Keep changing direction
            direction = (direction + 1) % 4;
        }
        // Increase steps after every pair of directions
        step++;
    }
    return traversed;
};

419. Battleships in a Board

https://leetcode.com/problems/battleships-in-a-board/description

Given an m x n matrix board where each cell is a battleship 'X' or empty '.', return the number of the battleships on board.

Battleships can only be placed horizontally or vertically on board. In other words, they can only be made of the shape 1 x k (1 row, k columns) or k x 1 (k rows, 1 column), where k can be of any size. At least one horizontal or vertical cell separates between two battleships (i.e., there are no adjacent battleships).

Example 1:

Input: board = [["X",".",".","X"],[".",".",".","X"],[".",".",".","X"]]
Output: 2

Approach # 1: Count first cell of battleships

1. Going over all cells, we can count only those that are the “first” cell of the battleship.
2. First cell will be defined as the most top-left cell.
3. We can check for first cells by only counting cells that do not have an ‘X’ to the left and do not have an ‘X’ above them.

Following is code for reference.

/**
 * @param {character[][]} board
 * @return {number}
 */
var countBattleships = function (board) {
    const m = board.length;
    const n = board[0].length;
    let ans = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === '.') {
                continue;
            }
            if (i > 0 && board[i - 1][j] === 'X') {
                continue;
            }
            if (j > 0 && board[i][j - 1] === 'X') {
                continue;
            }
            ans++;
        }
    }
    return ans;
};

Approach#2: Graph connected components

Since goal is to group all the ships to form battleships therefore we can apply graph algorithm to find out the connected components.

Following is code for reference.

const dfs = (board, i, j, visited) => {
    const m = board.length;
    const n = board[0].length;
    visited[i][j] = true;
    const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    for (const [p, q] of dirs) {
        const x = i + p;
        const y = j + q;
        if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] === 'X') {
            if (!visited[x][y]) {
                dfs(board, x, y, visited);
            }
        }
    }
}
/**
 * @param {character[][]} board
 * @return {number}
 */
var countBattleships = function (board) {
    const m = board.length;
    const n = board[0].length;
    const visited = new Array(m).fill(0).map(a => new Array(n).fill(false));
    let ans = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === 'X' && !visited[i][j]) {
                ans++;
                dfs(board, i, j, visited);
            }
        }
    }
    return ans;
};

2022. Convert 1D Array Into 2D Array

https://leetcode.com/problems/convert-1d-array-into-2d-array

You are given a 0-indexed 1-dimensional (1D) integer array original, and two integers, m and n. You are tasked with creating a 2-dimensional (2D) array with m rows and n columns using all the elements from original.

The elements from indices 0 to n - 1 (inclusive) of original should form the first row of the constructed 2D array, the elements from indices n to 2 * n - 1 (inclusive) should form the second row of the constructed 2D array, and so on.

Return an m x n 2D array constructed according to the above procedure, or an empty 2D array if it is impossible.

Example 1:

Input: original = [1,2,3,4], m = 2, n = 2
Output: [[1,2],[3,4]]
Explanation: The constructed 2D array should contain 2 rows and 2 columns.
The first group of n=2 elements in original, [1,2], becomes the first row in the constructed 2D array.
The second group of n=2 elements in original, [3,4], becomes the second row in the constructed 2D array.

Approach 1: Use mod to location 2d position

/**
 * @param {number[]} original
 * @param {number} m
 * @param {number} n
 * @return {number[][]}
 */
var construct2DArray = function (original, m, n) {
    const size = original.length;
    if (size !== m * n) {
        return [];
    }
    const ans = new Array(m).fill(0).map(a => new Array(n).fill(0));
    for (let i = 0; i < size; i++) {
        const x = Math.floor(i / n);
        const y = i % n;
        ans[x][y] = original[i];
    }
    return ans;
};

Approach #2: Use counter

/**
 * @param {number[]} original
 * @param {number} m
 * @param {number} n
 * @return {number[][]}
 */
var construct2DArray = function (original, m, n) {
    const size = original.length;
    if (size !== m * n) {
        return [];
    }
    const ans = new Array(m).fill(0).map(a => new Array(n).fill(0));
    let index = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            ans[i][j] = original[index++];
        }
    }
    return ans;
};

2419. Longest Subarray With Maximum Bitwise AND

https://leetcode.com/problems/longest-subarray-with-maximum-bitwise-and/description

You are given an integer array nums of size n.

Consider a non-empty subarray from nums that has the maximum possible bitwise AND.

• In other words, let k be the maximum value of the bitwise AND of any subarray of nums. Then, only subarrays with a bitwise AND equal to k should be considered.

Return the length of the longest such subarray.

The bitwise AND of an array is the bitwise AND of all the numbers in it.

A subarray is a contiguous sequence of elements within an array.

Example 1:

Input: nums = [1,2,3,3,2,2]
Output: 2
Explanation:
The maximum possible bitwise AND of a subarray is 3.
The longest subarray with that value is [3,3], so we return 2.

Approach: Longest consecutive sequence of the maximum value

1. We’re given an array, and the goal is to find a subarray where the bitwise AND of all the numbers is as large as possible.
2. The maximum possible bitwise AND of a subarray would be the maximum number in the array itself.
3. This is because the bitwise AND operation with a larger number and a smaller number would always result in a number less than or equal to the smaller number.
4. Therefore, the maximum possible bitwise AND of a subarray can only be achieved when all the numbers in the subarray are equal to the maximum number in the array.

So, the task is to find the longest subarray where all the numbers are the maximum value in the array.

Following is code for reference.

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSubarray = function (nums) {
    const n = nums.length;
    let max = 0;
    let ans = 0;
    let window = 0;
    for (const num of nums) {
        if (num > max) {
            max = num;
            ans = 0; // reset
            window = 0;
        }
        if (num === max) {
            window++;
        } else {
            window = 0;
        }
        ans = Math.max(ans, window);
    }
    return ans;
};

1371. Find the Longest Substring Containing Vowels in Even Counts

https://leetcode.com/problems/find-the-longest-substring-containing-vowels-in-even-counts

Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, 'a', 'e', 'i', 'o', and 'u' must appear an even number of times.

Example 1:

Input: s = "eleetminicoworoep"
Output: 13
Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.

Example 2:

Input: s = "leetcodeisgreat"
Output: 5
Explanation: The longest substring is "leetc" which contains two e's.

Example 3:

Input: s = "bcbcbc"
Output: 6
Explanation: In this case, the given string "bcbcbc" is the longest because all vowels: a, e, i, o and u appear zero times.

Constraints:

• 1 <= s.length <= 5 x 10^5
• s contains only lowercase English letters.

Approach#1: Bruteforce (TLE)

/**
 * @param {string} s
 * @return {number}
 */
var findTheLongestSubstring = function (s) {
    const vowels = new Map([['a', 0], ['e', 1], ['i', 2], ['o', 3], ['u', 4]]);
    const n = s.length;
    let ans = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            const sub = s.substring(i, j + 1);
            // count vowles
            const sum = new Array(5).fill(0);
            for (const chr of sub) {
                if (vowels.has(chr)) {
                    sum[vowels.get(chr)]++;
                }
            }
            let valid = true;
            for (const num of sum) {
                if (num % 2 === 1) {
                    valid = false;
                }
            }
            if (valid) {
                ans = Math.max(ans, j - i + 1);
            }
        }
    }
    return ans;
};

Happy coding!!!