Unique Matrix Traversal and Perfect Squares with TypeScript

Introduction

Hello, aspiring programmer! Are you ready to embark on a journey into the land of matrices? In this unit, we're in for a thrilling ride into the world of unique matrix traversal . We'll be navigating through the realm of 2D arrays following an intriguing and distinctive order. Stay seated, and let's dive right in!

Task Statement

Suppose we have a matrix where each cell represents a distinct symbol or integer. Our task is to decode this matrix by reading the cells in a particular order. The decoding begins from the top-left cell of the matrix. We move in a bottom-left downward diagonal direction until we hit the left boundary. Upon hitting the left boundary, we move one cell down (unless we're at the bottom-left corner already, in which case we move one cell to the right) and start moving in an upward diagonal direction towards the upper-right. While moving diagonally up-right, if we hit the top boundary, we move one cell to the right and start moving in a downward diagonal direction towards the bottom-left. However, if we hit the right boundary while moving diagonally upward, we move one cell down and start moving in a bottom-left direction. In other words, we keep zigzagging diagonally across the matrix until every cell in the matrix is visited. Upon completing this zigzag traversal, we will have a list of traversed cell values. Next, we process this list to uncover the indices of the perfect square numbers. The function should implement this traversal and return a list containing the positions of perfect square numbers in the traversed sequence. Take a 3x4 matrix, for instance: text {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}} Upon completing the diagonal traversal, we'll get the list: {1, 5, 2, 3, 6, 9, 10, 7, 4, 8, 11, 12} . From this list, we see that 1, 9, and 4 are perfect squares and are located at the 1st, 6th, and 9th positions in the list. Thus, our function returns: {0, 5, 8} .

Step Overview

To tackle this problem, we will take the following steps: Traverse the Matrix Diagonally : Begin from the top-left cell and zigzag through the matrix in a specific diagonal pattern. Record Traversed Values : As you traverse, collect the cell values in a list. Identify Perfect Squares : Inspect the collected values to determine which are perfect squares. Return Positions : Gather the positions of the perfect squares in the list and return them.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

TypeScript

function diagonalTraverseAndSquares(matrix: number[][]): number[] {
    const rows: number = matrix.length;
    const cols: number = matrix[0].length;
    const traversal: number[] = [];
    const results: number[] = [];

function diagonalTraverseAndSquares(matrix: number[][]): number[] {
    const rows: number = matrix.length;
    const cols: number = matrix[0].length;
    const traversal: number[] = [];
    const results: number[] = [];

TypeScript

    let row: number = 0, col: number = 0, dir: number = 1;
    for (let i: number = 0; i < rows * cols; i++) {  // Loop runs for the total number of cells in the matrix.
        traversal.push(matrix[row][col]);  // Append the current cell value to traversal.
        
        // Logic to control direction based on edges:
        if (dir === 1) {  // Moving down-left
            if (row === rows - 1) {
                col += 1;
                dir = -1;
            } else if (col === 0) {
                row += 1;
                dir = -1;
            } else {
                row += 1;
                col -= 1;
            }
        } else {  // Moving up-right
            if (col === cols - 1) {
                row += 1;
                dir = 1;
            } else if (row === 0) {
                col += 1;
                dir = 1;
            } else {
                row -= 1;
                col += 1;
            }
        }
    }

    let row: number = 0, col: number = 0, dir: number = 1;
    for (let i: number = 0; i < rows * cols; i++) {  // Loop runs for the total number of cells in the matrix.
        traversal.push(matrix[row][col]);  // Append the current cell value to traversal.
        
        // Logic to control direction based on edges:
        if (dir === 1) {  // Moving down-left
            if (row === rows - 1) {
                col += 1;
                dir = -1;
            } else if (col === 0) {
                row += 1;
                dir = -1;
            } else {
                row += 1;
                col -= 1;
            }
        } else {  // Moving up-right
            if (col === cols - 1) {
                row += 1;
                dir = 1;
            } else if (row === 0) {
                col += 1;
                dir = 1;
            } else {
                row -= 1;
                col += 1;
            }
        }
    }

TypeScript

    for (let idx: number = 0; idx < traversal.length; idx++) {
        const val: number = traversal[idx];
        const root: number = Math.sqrt(val);
        if (root === Math.floor(root)) {  // Check if the value is a perfect square number.
            results.push(idx);
        }
    }

    return results;
}

    for (let idx: number = 0; idx < traversal.length; idx++) {
        const val: number = traversal[idx];
        const root: number = Math.sqrt(val);
        if (root === Math.floor(root)) {  // Check if the value is a perfect square number.
            results.push(idx);
        }
    }

    return results;
}

TypeScript

const matrix: number[][] = [
    [16, 2, 3, 13],
    [5, 11, 10, 8],
    [9, 7, 6, 12],
    [4, 14, 15, 1]
];

const result: number[] = diagonalTraverseAndSquares(matrix);
console.log(result);  // Output: [ 0, 5, 6, 15 ]

const matrix: number[][] = [
    [16, 2, 3, 13],
    [5, 11, 10, 8],
    [9, 7, 6, 12],
    [4, 14, 15, 1]
];

const result: number[] = diagonalTraverseAndSquares(matrix);
console.log(result);  // Output: [ 0, 5, 6, 15 ]

TypeScript

function diagonalTraverseAndSquares(matrix: number[][]): number[] {
    const rows: number = matrix.length;
    const cols: number = matrix[0].length;
    const traversal: number[] = [];
    const results: number[] = [];

TypeScript

    let row: number = 0, col: number = 0, dir: number = 1;
    for (let i: number = 0; i < rows * cols; i++) {  // Loop runs for the total number of cells in the matrix.
        traversal.push(matrix[row][col]);  // Append the current cell value to traversal.
        
        // Logic to control direction based on edges:
        if (dir === 1) {  // Moving down-left
            if (row === rows - 1) {
                col += 1;
                dir = -1;
            } else if (col === 0) {
                row += 1;
                dir = -1;
            } else {
                row += 1;
                col -= 1;
            }
        } else {  // Moving up-right
            if (col === cols - 1) {
                row += 1;
                dir = 1;
            } else if (row === 0) {
                col += 1;
                dir = 1;
            } else {
                row -= 1;
                col += 1;
            }
        }
    }

TypeScript

    for (let idx: number = 0; idx < traversal.length; idx++) {
        const val: number = traversal[idx];
        const root: number = Math.sqrt(val);
        if (root === Math.floor(root)) {  // Check if the value is a perfect square number.
            results.push(idx);
        }
    }

    return results;
}

TypeScript

const matrix: number[][] = [
    [16, 2, 3, 13],
    [5, 11, 10, 8],
    [9, 7, 6, 12],
    [4, 14, 15, 1]
];

const result: number[] = diagonalTraverseAndSquares(matrix);
console.log(result);  // Output: [ 0, 5, 6, 15 ]

Introduction

Task Statement

Step Overview

Join the 1M+ learners on CodeSignal

Understanding Matrix Dimensions

Traversing the Matrix Diagonally

Identifying Perfect Squares

Example Usage

Conclusion