Search A 2D Matrix Ii

                                            
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if (m == 0) return false;
        int n = matrix[0].size();
        
        int row = 0, col = n - 1;
        while (row < m && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] < target) {
                row++;
            } else {
                col--;
            }
        }
        
        return false;
    }
};

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

                                            
class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:
            return False
        
        row = 0
        col = len(matrix[0]) - 1
        
        while row < len(matrix) and col >= 0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] < target:
                row += 1
            else:
                col -= 1
        
        return False

                                            
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target){
    int row = 0;
    int col = *matrixColSize - 1;
    
    while (row < matrixSize && col >= 0) {
        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] < target) {
            row++;
        } else {
            col--;
        }
    }
    
    return false;
}

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

                                            
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
const searchMatrix = function(matrix, target) {
    let row = 0;
    let col = matrix[0].length - 1;
    
    while (row < matrix.length && col >= 0) {
        if (matrix[row][col] === target) {
            return true;
        } else if (matrix[row][col] < target) {
            row++;
        } else {
            col--;
        }
    }
    
    return false;
};

                                            
function searchMatrix(matrix: number[][], target: number): boolean {
    let row = 0;
    let col = matrix[0].length - 1;
    
    while (row < matrix.length && col >= 0) {
        if (matrix[row][col] === target) {
            return true;
        } else if (matrix[row][col] < target) {
            row++;
        } else {
            col--;
        }
    }
    
    return false;
};

                                            
class Solution {
    /**
     * @param Integer[][] $matrix
     */
    function searchMatrix($matrix, $target) {
        $rows = count($matrix);
        if ($rows == 0) {
            return false;
        }
        $cols = count($matrix[0]);
        $row = 0;
        $col = $cols - 1;
        
        while ($row < $rows && $col >= 0) {
            if ($matrix[$row][$col] == $target) {
                return true;
            } elseif ($matrix[$row][$col] < $target) {
                $row++;
            } else {
                $col--;
            }
        }
        
        return false;
    }
}

                                            
class Solution {
    func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
        guard !matrix.isEmpty else {
            return false
        }
        
        var row = 0
        var col = matrix[0].count - 1
        
        while row < matrix.count, col >= 0 {
            if matrix[row][col] == target {
                return true
            } else if matrix[row][col] < target {
                row += 1
            } else {
                col -= 1
            }
        }
        
        return false
    }
}

                                            
class Solution {
    fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
        var row = matrix.size - 1
        var col = 0
        
        while (row >= 0 && col < matrix[0].size) {
            when {
                matrix[row][col] == target -> return true
                matrix[row][col] < target -> col++
                else -> row--
            }
        }
        
        return false
    }
}

                                            
func searchMatrix(matrix [][]int, target int) bool {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return false
    }
    
    row, col := 0, len(matrix[0])-1
    
    for row < len(matrix) && col >= 0 {
        if matrix[row][col] == target {
            return true
        } else if matrix[row][col] < target {
            row++
        } else {
            col--
        }
    }
    
    return false
}

                                            
# @param {Integer[][]} matrix
# @param {Integer} target
# @return {Boolean}
def search_matrix(matrix, target)
    row = 0
    col = matrix[0].length - 1
    
    while row < matrix.length && col >= 0
        if matrix[row][col] == target
            return true
        elsif matrix[row][col] > target
            col -= 1
        else
            row += 1
        end
    end
    
    return false
end

                                            
object Solution {
    def searchMatrix(matrix: Array[Array[Int]], target: Int): Boolean = {
        if (matrix.isEmpty || matrix(0).isEmpty) {
            return false
        }
        
        var row = 0
        var col = matrix(0).length - 1
        
        while (row < matrix.length && col >= 0) {
            if (matrix(row)(col) == target) {
                return true
            } else if (matrix(row)(col) < target) {
                row += 1
            } else {
                col -= 1
            }
        }
        
        false
    }
}

                                            
impl Solution {
    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
        let mut row = 0;
        let mut col = matrix[0].len() as i32 - 1;
        
        while row < matrix.len() as i32 && col >= 0 {
            if matrix[row as usize][col as usize] == target {
                return true;
            } else if matrix[row as usize][col as usize] > target {
                col -= 1;
            } else {
                row += 1;
            }
        }
        
        false
    }
}

To solve this coding challenge, you must understand the structure of the input matrix and utilize its sorted properties to search for a target value efficiently. The matrix is sorted both row-wise and column-wise. This distinctive sorting property makes it possible to utilize a strategic search method instead of a straightforward linear search.

Explanation

Given an

m x n

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 challenge is to determine if a given target value exists within the matrix or not. The sorted properties of the matrix allow us to employ a search strategy that leverages these restrictions to eliminate large portions of the matrix that cannot contain the target:

Start the search from the top-right corner of the matrix.
Compare the current element with the target:

If the current element is equal to the target, return
True

.
If the current element is less than the target, move down to the next row because all elements in the current row to the left are smaller and can be ignored.
If the current element is greater than the target, move left to the previous column because all elements in the current column below are greater and can be ignored.

Repeat the comparison until you either find the target (return
True

) or exhaust the search area (return
False

).

This method is efficient because it narrows down the search space progressively by eliminating either a row or a column at each comparison step.

Detailed Steps in Pseudocode:

Initialization :

If the matrix is empty or the first row of the matrix is empty, return
False

(no need to continue).
Set the starting point at the top-right corner of the matrix (
row = 0

,
col = last column index

).

Search Process :

While the current position is within the bounds of the matrix:

Compare the current element with the target:

If
matrix[row][col]

is equal to the target, return
True

.
If
matrix[row][col]

is less than the target, increment the row index (move down).
If
matrix[row][col]

is greater than the target, decrement the column index (move left).

If the loop ends without finding the target, return
False

.

Pseudocode with Comments:

                                            
# Check if the matrix is empty or has no columns.
if matrix is empty OR first row of matrix is empty:
return False

# Start from the top-right corner of the matrix.
row = 0
col = number of columns in the matrix - 1

# Loop while the current position is within the bounds of the matrix.
while row < number of rows in matrix AND col >= 0:
# If the current element is equal to the target, return True.
if matrix[row][col] == target:
return True
# If the current element is less than the target, move to the next row.
elif matrix[row][col] < target:
row = row + 1
# If the current element is greater than the target, move to the previous column.
else:
col = col - 1

# If we exit the loop, the target is not in the matrix, so return False.
return False

Step-by-Step Explanation:

Check Matrix : First, ensure that the matrix is not empty and that it contains at least one column.
Initial Position : Start the search at the top-right corner, because this position offers the best insight due to the sorted nature of the matrix.
Comparison and Movement :

If the element at the current position matches the target, the search is successful, and the function returns
True

.
If the element is smaller than the target, it implies that the target cannot be in the same row (to the left), so we move down to the next row.
If the element is larger than the target, it implies that the target cannot be in the same column (below), so we move left to the previous column.

Exit Condition : The while loop ensures that the search continues as long as we are within the boundaries of the matrix. If the loop terminates, it indicates that the target is not present in the matrix, and the function returns
False

.

This strategy ensures an efficient search with a time complexity of O(m + n), where m is the number of rows and n is the number of columns, due to the elimination process in each step of the loop.