Navigating Matrices with Zigzag Traversals in Kotlin

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:

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:

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:

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.

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