Mastering Matrix Traversals in Go

Introduction

Hello, Go programmer! Are you ready to embark on an intriguing coding journey? In this lesson, we're going to explore special traversals of matrices in Go. Matrices are rectangular 2D arrays, where each inner array maintains the same size. We'll navigate a matrix by zigzagging through columns, climbing up and down. Sound exciting? Buckle up, then, and get ready!

Task Statement

Here's the task: You've been given a 2D slice consisting of individual cells, each holding a unique integer value. Your goal is to create a function that will traverse this matrix, starting at the bottom-right cell. From there, you'll travel up to the top of the same column, then move left to the next column, and continue downward from the top of this new column. After reaching the bottom of the column, you'll again move left and start moving upward. This unique traversal pattern will be performed until all the cells have been visited. Consider this small 3x4 matrix as an example: Go matrix := [][]int{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12},} With 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

The first step toward a solution is understanding the dimensions of the matrix with which we're working. We can do this using Go's built-in functions to determine the length of slices. Let's set up our function and identify the matrix size: Go package main import "fmt" func ColumnTraverse(matrix [][]int) []int {rows := len(matrix) cols := len(matrix[0]) return nil}

Solution Building: Step 2

Now that we're aware of the matrix dimensions, we should establish the starting point (bottom-right) and the direction of travel (upward initially). Additionally, we'll need a slice to keep track of the cells we've visited in order. Go package main import "fmt" func ColumnTraverse(matrix [][]int) []int {rows := len(matrix) cols := len(matrix[0]) direction := "up" row := rows - 1 col := cols - 1 output := make([]int, 0, rows*cols) return output}

Join the 1M+ learners on CodeSignal

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

package main import "fmt" func ColumnTraverse(matrix [][]int) []int { rows := len(matrix) cols := len(matrix[0]) direction := "up" row := rows - 1 col := cols - 1 output := make([]int, 0, rows*cols) for len(output) < rows*cols { output = append(output, matrix[row][col]) if direction == "up" { if row-1 < 0 { direction = "down" col-- } else { row-- } } else { if row+1 == rows { direction = "up" col-- } else { row++ } } } return output } func main() { matrix := [][]int{ {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, } result := ColumnTraverse(matrix) for _, num := range result { fmt.Print(num, " ") } }

Traverse Using Decreasing Range

Let's explore one more way of traversal. We can leverage Go's for loop to traverse a 2D slice in reverse order. This capability can also create a sequence that decrements.

Consider our familiar 3x4 matrix:

matrix := [][]int{
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12},
}

matrix := [][]int{
    {1, 2, 3, 4},
    {5, 6, 7, 8},
    {9, 10, 11, 12},
}

Using decrementing loops, the reverse traverse pattern would produce this list: {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}.

Here's how we can implement this reverse traversal:

package main

import "fmt"

func ReverseTraverse(matrix [][]int) []int {
    rows := len(matrix)
    cols := len(matrix[0])
    output := make([]int, 0, rows*cols)

    for row := rows - 1; row >= 0; row-- {
        for col := cols - 1; col >= 0; col-- {
            output = append(output, matrix[row][col])
        }
    }

    return output
}

func main() {
    matrix := [][]int{
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
    }

    result := ReverseTraverse(matrix)
    for _, num := range result {
        fmt.Print(num, " ")
    }
}

package main

import "fmt"

func ReverseTraverse(matrix [][]int) []int {
    rows := len(matrix)
    cols := len(matrix[0])
    output := make([]int, 0, rows*cols)

    for row := rows - 1; row >= 0; row-- {
        for col := cols - 1; col >= 0; col-- {
            output = append(output, matrix[row][col])
        }
    }

    return output
}

func main() {
    matrix := [][]int{
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
    }

    result := ReverseTraverse(matrix)
    for _, num := range result {
        fmt.Print(num, " ")
    }
}

In this function, we start the loop for row from rows - 1 and run it to 0, decrementing it at each step. Similarly, our nested loop for col starts from cols - 1 and goes to 0. This allows us to start from the bottom-right corner and traverse leftward, then upward, covering the entire matrix in reverse order.