Navigating Matrices with Zigzag Traversals in Kotlin | CodeSignal Learn

Navigating Matrices with Zigzag Traversals in Kotlin | CodeSignal Learn

Introduction

Hello, fellow coder! Are you ready to tackle an exciting coding challenge using Kotlin ? In this lesson, we're going to explore unique methods for traversing matrices. Matrices in Kotlin are represented as 2D arrays where each inner array maintains the same size. We'll perform a traversal through these matrices by moving up and down across columns, creating a zigzag pattern as we go. Sounds intriguing? Let's get started!

Task Statement

Here's your task: Given a 2D array where each element holds a unique integer value, your goal is to develop a function that traverses the matrix starting from the bottom-right cell. From there, you'll travel upwards to the top of the same column, then move left to the next column, and begin moving downward from the top of this new column. Continue this pattern of traversal until all cells have been visited. Consider this small 3x4 matrix as an example: Kotlin val matrix = arrayOf(intArrayOf(1, 2, 3, 4), intArrayOf(5, 6, 7, 8), intArrayOf(9, 10, 11, 12)) Using the described traversal pattern, your function should return this list: [12, 8, 4, 3, 7, 11, 10, 6, 2, 1, 5, 9] .

Solution Building: Step 1

To begin our solution, we need to determine the dimensions of our matrix. We'll accomplish this using Kotlin's array properties. Let's start by setting up our function and identifying the matrix size: Kotlin fun columnTraverse(matrix: Array<IntArray>): IntArray {val rows = matrix.size val cols = matrix[0].size}

Solution Building: Step 2

With the matrix dimensions known, we can set our starting point (bottom-right) and the initial direction of travel (upward). We'll also need an array to track the cells we've visited in order: Kotlin fun columnTraverse(matrix: Array<IntArray>): IntArray {val rows = matrix.size val cols = matrix[0].size var direction = "up" var row = rows - 1 var col = cols - 1 val output = IntArray(rows * cols) var index = 0}

Solution Building: Step 3

Now, let's implement a while loop to traverse the matrix. This loop will continue until all the cells have been visited. As we "visit" each cell, we'll add its value to our array. Kotlin fun columnTraverse(matrix: Array<IntArray>): IntArray {// Determine the number of rows and columns in the matrix val rows = matrix.size val cols = matrix[0].size // Set initial direction of traversal to "up" var direction = "up" // Start from the bottom-right corner of the matrix var row = rows - 1 var col = cols - 1 // Prepare an array to store the traversal result val output = IntArray(rows * cols) var index = 0 // Traverse until all cells have been visited while (index < rows * cols) {// Add the current cell's value to the output array output[index++] = matrix[row][col] // Determine the next cell based on the current direction when {direction == "up" -> {// If moving up and reached the top, switch direction to "down" and move left if (row - 1 < 0) {direction = "down" col -= 1} else {// Otherwise, move up to the previous row row -= 1}} else -> {// If moving down and reached the bottom, switch direction to "up" and move left if (row + 1 == rows) {direction = "up" col -= 1} else {// Otherwise, move down to the next row row += 1}}}} // Return the resulting traversal order return output} fun main() {val matrix = arrayOf(intArrayOf(1, 2, 3, 4), intArrayOf(5, 6, 7, 8), intArrayOf(9, 10, 11, 12)) val result = columnTraverse(matrix) println(result.joinToString(" "))} And there you have it! This Kotlin function returns the output array, giving us the specific order of traversal through the matrix.

Sign up

Join the 1M+ learners on CodeSignal

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

Traverse Using Decreasing Range

Let's explore another method of traversal. Kotlin allows us to use a for-loop to iterate through a 2D matrix in reverse order, utilizing ranges. This adds flexibility in creating sequences that decrement. Consider our 3x4 matrix: val matrix = arrayOf(intArrayOf(1, 2, 3, 4), intArrayOf(5, 6, 7, 8), intArrayOf(9, 10, 11, 12)) Using a decrementing loop, the reverse traversal pattern would produce the list: [12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] . Here's how we can achieve this reverse traversal: fun reverseTraverse(matrix: Array<IntArray>): IntArray {// Determine the number of rows and columns in the matrix val rows = matrix.size val cols = matrix[0].size // Prepare an array to store the traversal result val output = IntArray(rows * cols) var index = 0 // Loop through rows in reverse order, starting from the last row for (row in rows - 1 downTo 0) {// Loop through columns in reverse order for each row for (col in cols - 1 downTo 0) {// Add the current cell's value to the output array output[index++] = matrix[row][col]}} // Return the resulting reverse traversal order return output} fun main() {val matrix = arrayOf(intArrayOf(1, 2, 3, 4), intArrayOf(5, 6, 7, 8), intArrayOf(9, 10, 11, 12)) val result = reverseTraverse(matrix) println(result.joinToString(" "))} In this function, the loop for row starts from rows - 1 and runs to 0, decrementing at each step. Likewise, the nested loop for col starts from cols - 1 and proceeds to 0 . This process allows us to begin from the bottom-right corner and traverse leftward, then upward, covering the entire matrix in reverse order.

Kotlin

fun reverseTraverse(matrix: Array<IntArray>): IntArray {
    // Determine the number of rows and columns in the matrix
    val rows = matrix.size
    val cols = matrix[0].size
    // Prepare an array to store the traversal result
    val output = IntArray(rows * cols)
    var index = 0

    // Loop through rows in reverse order, starting from the last row
    for (row in rows - 1 downTo 0) {
        // Loop through columns in reverse order for each row
        for (col in cols - 1 downTo 0) {
            // Add the current cell's value to the output array
            output[index++] = matrix[row][col]
        }
    }

    // Return the resulting reverse traversal order
    return output
}

fun main() {
    val matrix = arrayOf(
        intArrayOf(1, 2, 3, 4),
        intArrayOf(5, 6, 7, 8),
        intArrayOf(9, 10, 11, 12)
    )

    val result = reverseTraverse(matrix)
    println(result.joinToString(" "))
}