Search in 2D Matrix in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of search in sorted 2D matrix

What is the output of the following Go code that searches for the number 5 in a sorted 2D matrix?

DSA Go

package main
import "fmt"
func searchMatrix(matrix [][]int, target int) bool {
    rows := len(matrix)
    if rows == 0 {
        return false
    }
    cols := len(matrix[0])
    r, c := 0, cols-1
    for r < rows && c >= 0 {
        if matrix[r][c] == target {
            return true
        } else if matrix[r][c] > target {
            c--
        } else {
            r++
        }
    }
    return false
}
func main() {
    matrix := [][]int{
        {1, 4, 7, 11},
        {2, 5, 8, 12},
        {3, 6, 9, 16},
        {10, 13, 14, 17},
    }
    fmt.Println(searchMatrix(matrix, 5))
}

A runtime error

B false

C true

D compilation error

💡 Hint

Think about how the search moves through the matrix starting from the top-right corner.

The code starts searching from the top-right corner. It moves left if the current number is greater than the target, or down if smaller. Since 5 is in the matrix, it returns true.

❓ Predict Output

intermediate

Output when target is not in matrix

What does the following Go code print when searching for 15 in the given sorted 2D matrix?

DSA Go

package main
import "fmt"
func searchMatrix(matrix [][]int, target int) bool {
    rows := len(matrix)
    if rows == 0 {
        return false
    }
    cols := len(matrix[0])
    r, c := 0, cols-1
    for r < rows && c >= 0 {
        if matrix[r][c] == target {
            return true
        } else if matrix[r][c] > target {
            c--
        } else {
            r++
        }
    }
    return false
}
func main() {
    matrix := [][]int{
        {1, 4, 7, 11},
        {2, 5, 8, 12},
        {3, 6, 9, 16},
        {10, 13, 14, 17},
    }
    fmt.Println(searchMatrix(matrix, 15))
}

A true

B compilation error

C runtime error

D false

💡 Hint

Check if 15 exists in the matrix by following the search path.

The search moves through the matrix but never finds 15, so it returns false.

🧠 Conceptual

advanced

Why start search from top-right corner in 2D matrix?

Why is the top-right corner chosen as the starting point for searching a target in a sorted 2D matrix where rows and columns are sorted ascending?

A Because from top-right, moving left decreases values and moving down increases values, allowing elimination of rows or columns efficiently.

B Because top-right corner always contains the smallest element in the matrix.

C Because starting from top-right avoids checking the entire matrix by jumping diagonally.

D Because top-right corner is the only position where binary search can be applied directly.

💡 Hint

Think about how the values change when moving left or down from the top-right corner.

Starting at the top-right corner allows the algorithm to discard a row or a column at each step because moving left decreases values and moving down increases values, matching the sorted property.

🔧 Debug

advanced

Identify the bug in 2D matrix search code

What error will the following Go code produce when searching for 3 in the matrix, and why?

DSA Go

package main
import "fmt"
func searchMatrix(matrix [][]int, target int) bool {
    rows := len(matrix)
    if rows == 0 {
        return false
    }
    cols := len(matrix[0])
    r, c := 0, cols-1
    for r < rows && c >= 0 {
        if matrix[r][c] == target {
            return true
        } else if matrix[r][c] > target {
            c--
        } else {
            r++
        }
    }
    return false
}
func main() {
    matrix := [][]int{
        {1, 4, 7},
        {2, 5, 8},
        {3, 6, 9},
    }
    fmt.Println(searchMatrix(matrix, 3))
}

A runtime error: index out of range

B false

C true

D compilation error

💡 Hint

Check the initial value of column index c and how it is used to access matrix elements.

The code sets c = cols, which is out of bounds since valid indices are 0 to cols-1. Accessing matrix[r][c] causes an index out of range runtime error.

🚀 Application

expert

Count occurrences of target in sorted 2D matrix

Given a sorted 2D matrix where each row and column is sorted ascending, which approach efficiently counts how many times a target appears?

A Traverse entire matrix and count occurrences, resulting in O(m*n) time.

B Start from bottom-left corner and move up or right to count all occurrences in O(m+n) time.

C Perform binary search on each row separately and sum counts, resulting in O(m log n) time.

D Start from top-left corner and move diagonally down-right to count occurrences.

💡 Hint

Consider how moving up or right from bottom-left corner helps eliminate rows or columns.

Starting from bottom-left, if current element is greater than target, move up; if less, move right. This way, all occurrences can be counted efficiently in O(m+n) time.