Leetcode Search a 2D Matrix II problem solution

YASH PAL,

In this Leetcode Search a 2D Matrix II problem solution Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:

  1. Integers in each row are sorted in ascending from left to right.
  2. Integers in each column are sorted in ascending from top to bottom.
Leetcode Search a 2D Matrix II problem solution

Problem solution in Python.

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if matrix==[] or matrix is None:
            return False
        col=len(matrix[0])-1
        row=0
        while col>=0 and row<len(matrix):
            if matrix[row][col]==target:
                return True
            elif matrix[row][col]>target:
                col-=1
            else:
                row+=1
        return False

Problem solution in Java.

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int row = matrix.length - 1;
        int col = 0;
        int colEnd = matrix[0].length;
        
        while (row >= 0 && col < colEnd) {
            if (matrix[row][col] == target) {
                return true;
            }
            else if (matrix[row][col] < target) {
                col++;
            }
            else {
                row--;
            }
        }
        
        return false;
    }
}

Problem solution in C++.

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // start our "pointer" in the bottom-left
        int row = matrix.size()-1;
        int col = 0;

        while (row >= 0 && col < matrix[0].size()) {
            if (matrix[row][col] > target) {
                row--;
            } else if (matrix[row][col] < target) {
                col++;
            } else { // found it
                return true;
            }
        }

        return false;
    }
};

Problem solution in C.

#define INT_MIN -2147483648
bool flag = false;

void run(int** matrix, int matrixSize, int* matrixColSize, int target, int x, int y)
{
    if(x < matrixSize && y < *matrixColSize && matrix[x][y] != INT_MIN)
    {
        if(matrix[x][y] == target)
        {
            flag = true;
            return;
        }
        else if(matrix[x][y] < target)
        {
            run(matrix,matrixSize,matrixColSize,target,x+1,y);
            run(matrix,matrixSize,matrixColSize,target,x,y+1);
            matrix[x][y] = INT_MIN;     //  record 
        }
    }
    return;
}

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target)
{
    flag = false;
    run(matrix,matrixSize,matrixColSize,target,0,0);
    return flag;
}

coding problems