Searching in a 2D Matrix Using Swift

This article is part of my series on solving Striver’s SDE Sheet using Swift. Searching in a 2D matrix can be tricky at first glance, but with the right approach, it becomes manageable. In this tutorial, we will break down the process step-by-step, ensuring that you understand each part along the way.

Prerequisites

Before we dive into the tutorial, make sure you have the following:

• A basic understanding of the Swift programming language.
• Familiarity with arrays and matrices.
• A development environment set up for Swift (like Xcode).

Step-by-Step Guide

Understanding the Problem

Searching for a specific value in a 2D matrix involves checking each element until the desired value is found. However, we can optimize this process by leveraging the properties of the matrix.

Matrix Properties

In many cases, the matrix is sorted both row-wise and column-wise. This means that:

• Each row is sorted in ascending order.
• Each column is sorted in ascending order.

This property allows us to use a more efficient search algorithm than a simple linear search.

Algorithm Overview

We will use a two-pointer technique to search for the target value:

1. Start from the top-right corner of the matrix.
2. If the current element is equal to the target, we have found our value.
3. If the current element is greater than the target, move left.
4. If the current element is less than the target, move down.
5. Repeat until you find the target or go out of bounds.

Implementing the Solution in Swift

Now, let’s implement this algorithm in Swift. Below is a sample code snippet that demonstrates how to search in a 2D matrix:

func searchMatrix(matrix: [[Int]], target: Int) -> Bool {
    guard !matrix.isEmpty else { return false }
    let rows = matrix.count
    let cols = matrix[0].count
    var row = 0
    var col = cols - 1

    while row < rows && col >= 0 {
        if matrix[row][col] == target {
            return true
        } else if matrix[row][col] > target {
            col -= 1
        } else {
            row += 1
        }
    }
    return false
}

Testing the Function

To ensure our function works correctly, we can test it with a sample matrix and target value:

let matrix = [[1, 3, 5],
              [7, 10, 11],
              [12, 13, 15]]
let target = 10
let result = searchMatrix(matrix: matrix, target: target)
print(result) // Output: true

Conclusion

In this tutorial, we explored how to search for a value in a 2D matrix using Swift. By leveraging the properties of sorted matrices and implementing a two-pointer technique, we can efficiently find our target value. Practice this method with different matrices and target values to strengthen your understanding.

For more tutorials in this series, check out the following links:

https://medium.com/@leetsswift/leetcode-74-search-2d-matrix-40a65d65fccf?source=rss——data_structures-5

Continue reading on Medium »