Search an Element in a Row-Wise Column-Wise Sorted Matrix - Java Solution

1. Introduction

In this blog post, we'll explore a problem often encountered in the realm of matrix manipulation - searching for an element in a matrix that is sorted both row-wise and column-wise. This problem is a great example of how to efficiently navigate through a structured data set.

Problem

Given an m x n matrix where every row and column is sorted in increasing order, find the position of a target value in the matrix if it is present. If the target value is not present in the matrix, print “Not Found”.

Example 1:

Input: matrix[4][4] = { {10, 20, 30, 40},
                      {15, 25, 35, 45},
                      {27, 29, 37, 48},
                      {32, 33, 39, 50}};
              target = 29
Output: Found at (2, 1)
Explanation: Element at (2,1) is 29

Example 2:

Input : matrix[4][4] = { {10, 20, 30, 40},
                      {15, 25, 35, 45},
                      {27, 29, 37, 48},
                      {32, 33, 39, 50}};
              target = 100
Output : Element not found
Explanation: Element 100 is not found

2. Solution Steps

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

2. If the current element is greater than the target, move left.

3. If the current element is less than the target, move down.

4. If the target is found, return its position.

5. If the end of the row or column is reached without finding the target, print "Not Found".

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[][] matrix = { {10, 20, 30, 40},
                           {15, 25, 35, 45},
                           {27, 29, 37, 48},
                           {32, 33, 39, 50}};
        int target1 = 29;
        searchElement(matrix, target1); // Search for 29

        int target2 = 100;
        searchElement(matrix, target2); // Search for 100
    }

    // Method to search the element in the matrix
    public static void searchElement(int[][] matrix, int target) {
        int i = 0;
        int j = matrix[0].length - 1;

        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) {
                System.out.println("Found at (" + i + ", " + j + ")");
                return;
            }
            if (matrix[i][j] > target) {
                j--;
            } else {
                i++;
            }
        }
        System.out.println("Element not found");
    }
}

Output:

Found at (2, 1)
Element not found

Explanation:

In the first example, the matrix is searched for the target value 29. The search starts from the top-right corner (40) and moves left or down based on the comparison with the target. The value 29 is found at position (2, 1). In the second example, searching for the target value 100 results in "Element not found" since 100 is not in the matrix.