Simple Matrix Operations in Go

Lesson Overview

Welcome to this lesson covering Simple Matrix Operations . This is where we explore the arena of two-dimensional data structures, commonly known as matrices. Matrices play an instrumental role in many domains of programming, such as machine learning, computer vision, and game development, making it important for you to understand how to effectively manipulate and traverse them.

Matrix Review

In Go, matrices can be represented using slices of slices. This allows us to easily manipulate our data structures while retaining flexibility in specifying the size of the matrix dynamically. Here is an example of how you can declare and initialize a 3x3 matrix in Go: Go matrix := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9},} You can access elements of the matrix using indices of the row and column. For example, matrix[1][2] would access the element in the second row and third column, which is 6.

Matrix Traversal Review

We can access the number of rows in a matrix using len(matrix) . The number of columns can be determined by the length of any inner slice, such as len(matrix[0]) . Traversing a matrix usually involves nested loops. The outer loop normally iterates over the rows, and the inner loop iterates over the columns. Let's take a look at this code that simply prints each element of a matrix. Go for i := 0; i < len(matrix); i++ {for j := 0; j < len(matrix[i]); j++ {fmt.Print(matrix[i][j], " ")} fmt.Println()} Let's break this code down: Outer Loop This loop iterates over the rows of the matrix. len(matrix) returns the number of rows in the matrix. The variable i is the row index, starting at 0 and incrementing by 1 until it reaches the total number of rows. Go for i := 0; i < len(matrix); i++ {Inner Loop This loop iterates over the columns of the current row (i). len(matrix[i]) returns the number of columns in the i -th row of the matrix. The variable j is the column index, starting at 0 and incrementing by 1 until it reaches the total number of columns in the current row. Go for j := 0; j < len(matrix[i]); j++ {Accessing Elements matrix[i][j] accesses the element located at the i -th row and j -th column of the matrix. fmt.Print(matrix[i][j], " ") prints the accessed element, followed by a space " " . Go fmt.Print(matrix[i][j], " ") Printing Newline We print a newline character, moving the console cursor to the next line. Go fmt.Println() In summary, the outer loop iterates through each row, while the inner loop iterates through each column of the current row, printing each element followed by a space. After printing all elements in a row, it prints a newline character to start the next row on a new line.

Join the 1M+ learners on CodeSignal

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

Matrix Search

With this foundation in matrix traversal, let's tackle a common coding interview question. Given a sorted matrix where each row and column is sorted in ascending order, we have to search for a particular target value. One approach is traversing the entire matrix until we find the target value. However, this requires us to potentially search the entire matrix. Let's optimize our approach.

Since the matrix is sorted both row-wise and column-wise, we can leverage this property for an efficient search. Start from the top-right corner of the matrix:

If the current element equals the target, you've found the value.
If the current element is greater than the target, move left (one column back).
If the current element is less than the target, move down (one row forward).

Continue these steps until you either find the target or exhaust the search space. This method ensures that each step narrows down the potential search area efficiently.

Here's how you can implement this in Go:

package main

import (
    "fmt"
)

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }

    rows := len(matrix)
    cols := len(matrix[0])

    row := 0
    col := cols - 1

    for row < rows && col >= 0 {
        if matrix[row][col] == target {
            return true
        } else if matrix[row][col] > target {
            col-- // move left
        } else {
            row++ // move down
        }
    }

    return false // target not found
}

func main() {
    matrix := [][]int{
        {1, 4, 7, 11, 15},
        {2, 5, 8, 12, 19},
        {3, 6, 9, 16, 22},
        {10, 13, 14, 17, 24},
        {18, 21, 23, 26, 30},
    }
    target := 5

    if searchMatrix(matrix, target) {
        fmt.Println("Target found in the matrix.")
    } else {
        fmt.Println("Target not found in the matrix.")
    }
}

package main

import (
    "fmt"
)

func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }

    rows := len(matrix)
    cols := len(matrix[0])

    row := 0
    col := cols - 1

    for row < rows && col >= 0 {
        if matrix[row][col] == target {
            return true
        } else if matrix[row][col] > target {
            col-- // move left
        } else {
            row++ // move down
        }
    }

    return false // target not found
}

func main() {
    matrix := [][]int{
        {1, 4, 7, 11, 15},
        {2, 5, 8, 12, 19},
        {3, 6, 9, 16, 22},
        {10, 13, 14, 17, 24},
        {18, 21, 23, 26, 30},
    }
    target := 5

    if searchMatrix(matrix, target) {
        fmt.Println("Target found in the matrix.")
    } else {
        fmt.Println("Target not found in the matrix.")
    }
}

Code Breakdown

Let's break down the code step by step:

Function Definition

This line defines the function searchMatrix that returns a bool. The first parameter is a slice of slices of integers, and the second is the target value we are searching for.

func searchMatrix(matrix [][]int, target int) bool

func searchMatrix(matrix [][]int, target int) bool

Check for Empty Matrix

This check ensures that if the matrix is empty or the first row is empty, the function immediately returns false, as there is no element to search.

if len(matrix) == 0 || len(matrix[0]) == 0 {
    return false
}

if len(matrix) == 0 || len(matrix[0]) == 0 {
    return false
}

Determine Dimensions of the Matrix

This step fetches the number of rows and columns in the matrix to use in boundary conditions.

rows := len(matrix)
cols := len(matrix[0])

rows := len(matrix)
cols := len(matrix[0])

Set Initial Position

Initialize the starting point to the top-right corner of the matrix. row is initialized to 0 and col to the last column index cols - 1.

row := 0
col := cols - 1

row := 0
col := cols - 1

Start Matrix Traversal

The for loop runs as long as row is less than the number of rows and col is non-negative.

for row < rows && col >= 0 {

for row < rows && col >= 0 {

Comparison and Movement

If the current element matrix[row][col] is equal to the target, the function returns true.
If the current element is greater than the target, move left by decrementing col because all elements to the left are smaller.
If the current element is less than the target, move down by incrementing row because all elements below are larger.

if matrix[row][col] == target {
    return true
} else if matrix[row][col] > target {
    col-- // move left
} else {
    row++ // move down
}

if matrix[row][col] == target {
    return true
} else if matrix[row][col] > target {
    col-- // move left
} else {
    row++ // move down
}

Return Statement

If the loop completes and the target is not found, the function returns false.

return false // target not found

return false // target not found

In summary, the searchMatrix function searches for a target value within a two-dimensional matrix where each row and column is sorted in ascending order. By starting from the top-right corner and leveraging the sorted properties, it efficiently narrows the search space by moving left or down based on comparisons.