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 and even enjoyable. In this tutorial, we will explore how to efficiently search for a target value in a 2D matrix.

Prerequisites

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

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

Step-by-Step Guide

Understanding the Problem

We need to search for a target value in a 2D matrix where:

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

This property allows us to use an efficient search algorithm rather than a brute-force approach.

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, return its position.
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 the code 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 {
        let current = matrix[row][col]
        if current == target {
            return true
        } else if current > target {
            col -= 1
        } else {
            row += 1
        }
    }
    return false
}

Explanation of the Code

Let’s break down the code step by step:

• Function Definition: The function searchMatrix takes a 2D array matrix and an integer target as parameters.
• Guard Statement: We check if the matrix is empty. If it is, we return false.
• Variable Initialization: We initialize rows and cols to store the dimensions of the matrix. We also set row to 0 and col to the last column index.
• While Loop: The loop continues until we either find the target or go out of bounds. Inside the loop, we compare the current element with the target.
• Return Value: If we find the target, we return true. If we exit the loop without finding it, we return false.

Conclusion

Searching in a 2D matrix can be efficiently accomplished using the two-pointer technique. This method leverages the sorted properties of the matrix to minimize the number of comparisons needed. With the Swift implementation provided, you can easily integrate this search functionality into your applications.

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

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

Continue reading on Medium »