DEV Community

Tanuja V
Tanuja V

Posted on • Edited on

1 1

Search a 2D Matrix | LeetCode | Java

Algorithm:

  1. Apply Binary Search to find the row (where the potential target might be present)
  2. After find the row, apply Binary Search on that row. If the target element is present, we return true otherwise we return false.
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {

        int getRow = findRow(matrix, target);

        if(getRow==-1)
            return false;

        int low = 0;
        int high = matrix[0].length-1;

        while(low<=high){
            int mid = low + (high-low)/2;

            if(matrix[getRow][mid]==target)
                return true;

            else if(matrix[getRow][mid] < target)
                low = mid + 1;

            else
                high = mid - 1;
        }

        return false;
    }

    int findRow(int matrix[][], int target){
        int low = 0;
        int high = matrix.length-1;

        int lastCol = matrix[0].length-1;

        while(low<=high){
            int mid = low + (high-low)/2;

            if(matrix[mid][0]<=target && matrix[mid][lastCol]>=target)
                return mid;

            else if(matrix[mid][0]<target)
                low = mid + 1;

            else
                high = mid-1;
        }

        return -1;
    }
}
Enter fullscreen mode Exit fullscreen mode

Thanks for reading :)
Feel free to comment and like the post if you found it helpful
Follow for more 🤝 && Happy Coding 🚀

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7

Image of Docusign

Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs