Diagonal Matrix Traversal

Introduction

Hello, aspiring programmer! Are you ready to explore the fascinating world of matrices ? Today, we’ll embark on an exciting journey into the realm of unique matrix traversal. We’ll be working with 2D matrices and discovering a special order of traversal that’s both fun and intriguing. Buckle up, and let’s get started!

Task Statement

Imagine you have a 2D matrix where each cell contains a unique symbol or integer. Your task is to decode this matrix by reading its cells in a particular order. Follow these steps for the diagonal zigzag traversal: Start at the top-left cell of the matrix ([0][0]). Move one cell down. Move diagonally in the top-right direction until you reach the top boundary. When you hit the top boundary, move one cell to the right and start moving diagonally in the bottom-left direction. If you hit the left boundary, move one cell down (unless it’s the last left boundary, in which case move one cell to the right) and start moving diagonally in the top-right direction. If you hit the right boundary, move one cell to the right (unless it’s the last right boundary, in which case move one cell down) and start moving diagonally in the bottom-left direction. Continue zig-zagging diagonally across the matrix, switching direction at each boundary, until every cell is visited. After completing this zigzag traversal, you’ll have a list of the traversed cell values. Next, you’ll process this list to find the indices of the perfect square numbers. The function diagonalTraverseAndSquares(matrix: Array[Array[Int]]): List[Int] should implement this traversal and return a list containing the positions of perfect square numbers in the traversed sequence. Take a 3x4 matrix, for example: Scala val matrix = Array(Array(1, 2, 3, 4), Array(5, 6, 7, 8), Array(9, 10, 11, 12)) val matrix = Array(Array(1, 2, 3, 4), Array(5, 6, 7, 8), Array(9, 10, 11, 12)) After the diagonal traversal, you’ll get the list: List(1, 5, 2, 3, 6, 9, 10, 7, 4, 8, 11, 12) . In this list, 1, 9, and 4 are perfect squares, located at the 0th, 5th, and 8th positions (using zero-based indexing). Thus, the function returns: List(0, 5, 8) .

Solution Building: Step 1

First, let’s put on our Scala hats and examine the dimensions of the 2D matrix. To understand the structure of our matrix, we use the .length property to determine the number of rows and columns. Next, we initialize two mutable lists: traversal and results . The traversal list will store the cell values obtained from the matrix based on our unique diagonal zigzag traversal. The results list will later be filled with the positions of perfect square numbers found in the traversal list. Scala import scala.collection.mutable.ListBuffer def diagonalTraverseAndSquares(matrix: Array[Array[Int]]): List[Int] = {val rows = matrix.length val cols = matrix(0).length val traversal = ListBuffer[Int]() val results = ListBuffer[Int]() import scala.collection.mutable.ListBuffer def diagonalTraverseAndSquares(matrix: Array[Array[Int]]): List[Int] = {val rows = matrix.length val cols = matrix(0).length val traversal = ListBuffer[Int]() val results = ListBuffer[Int]() Here, ListBuffer is used for efficient appending of elements, and the function is defined to take a 2D array of integers as input.

Join the 1M+ learners on CodeSignal

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

Solution Building: Step 2

The next step is to traverse the 2D matrix in a zigzag diagonal pattern. We start from the top-left corner (cell [0][0]) and use two variables, row and col, to track the current cell indices. We also initialize a variable dir with 1, which indicates that the starting direction is the down-left direction.

The movement isn’t just simple left-right or up-down; as per the rules, we need to change direction whenever we hit an edge. Let dir = -1 represent the up-right direction. To ensure we continue the correct diagonal movement and don’t exceed the matrix boundaries, we use conditional checks within the loop.

Scala

  var row = 0
  var col = 0
  var dir = 1
  for (_ <- 0 until rows * cols) { // Loop runs for total number of cells in the matrix
    traversal += 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
      }
    }
  }

  var row = 0
  var col = 0
  var dir = 1
  for (_ <- 0 until rows * cols) { // Loop runs for total number of cells in the matrix
    traversal += 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
      }
    }
  }

This loop ensures that every cell in the matrix is visited in the correct zigzag diagonal order, and each value is added to the traversal list.

Introduction

Task Statement

Solution Building: Step 1

Join the 1M+ learners on CodeSignal

Solution Building: Step 2

Solution Building: Step 3

Lesson Summary