Search a 2D Matrix II - Java Solution

1. Introduction

This blog post discusses a solution to the "Search a 2D Matrix II" problem. This problem is particularly interesting due to the unique structure of the matrix: each row and each column are sorted in ascending order. The challenge is to write an efficient algorithm that searches for a target value in such a matrix.

Problem

Given an m x n integer matrix where each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom, the task is to find whether a target value exists in the matrix.

2. Solution Steps

1. Start from the top-right corner of the matrix.

2. If the target is greater than the current element, move down to the next row (since all elements in the current row are smaller).

3. If the target is less than the current element, move left to the next column (since all elements in the current column are larger).

4. Repeat steps 2 and 3 until the target is found or the boundaries of the matrix are exceeded.

5. If the target is found, return true; if the search exits the boundaries of the matrix, return false.

3. Code Program

public class Search2DMatrixII {
    public static void main(String[] args) {
        int[][] matrix = {
            {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}
        };
        int target = 5;
        System.out.println(searchMatrix(matrix, target)); // Test the function
    }

    // Function to search a value in the matrix
    public static boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length, n = matrix[0].length;
        int i = 0, j = n - 1; // Start from the top-right corner

        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                return true; // Target found
            } else if (matrix[i][j] < target) {
                i++; // Move down
            } else {
                j--; // Move left
            }
        }
        return false; // Target not found
    }
}

Output:

true

Explanation:

1. searchMatrix: This function efficiently searches for the target value in the matrix.

2. The search starts from the top-right corner of the matrix. This starting point is crucial because it allows us to move in directions where the value will either increase (down) or decrease (left).

3. If the current element matches the target, true is returned immediately.

4. If the target is greater than the current element, the search moves down to increase the value. If the target is less, it moves left.

5. The process continues until the target is found or the search goes out of the matrix bounds.

6. This approach leverages the sorted properties of the rows and columns, ensuring that the search is efficient with a worst-case time complexity of O(m + n), where m is the number of rows and n is the number of columns.