✔️ PYTHON ||  EXPLAINED  ||  ; ]
UPVOTE IF HELPFuuL\n\nEFFICIENT APPROACH -> O ( M + N )\n\nAs the rows are sorted -> matrix[i][j] < matrix[i][j+1]\nAs the columns are sorted -> matrix[i][j] >m
**UPVOTE IF HELPFuuL**\n\n**EFFICIENT APPROACH -> O ( M + N )**\n\nAs the rows are sorted **->** ```matrix[i][j] < matrix[i][j+1]```\nAs the columns are sorted **->** ```matrix[i][j] >matrix[i-1][j]```\n\nHence it can be said that :\n* any element right to ```matrix[i][j]``` will be greater than it.\n* any element to the top of ```matrix[i][j]``` will be less than it.\n\nSo we start searching from **BOTTOM_LEFT**:\n* if element found -> return **TRUE**\n* if ```matrix[i][j] > target``` -> move **UP**.\n* if ```matrix[i][j] < target``` -> move **RIGHT**.\n\n![image](https://assets.leetcode.com/users/images/ffcde87b-6220-4e61-a2ec-498abc7fd28d_1658626864.8423152.png)\n\n**UPVOTE IF HELPFuuL**\n\n```\nclass Solution:\n    def searchMatrix(self, mat: List[List[int]], target: int) -> bool:\n        \n        m=len(mat)\n        n=len(mat[0])\n        \n        i=m-1\n        j=0\n        \n        while i>=0 and j<n:\n            if mat[i][j]==target:\n                return True\n            elif mat[i][j]<target:\n                j+=1\n            else:\n                i-=1\n                \n        return False\n```\n\n**EFFICIENT APPROACH -> O ( M LOG N )**\nAs all the rows are sorted , an element can be clearly searched using *BINARY-SEARCH* for each row.\n\nFor each row -> O ( M )\nBinary search -> O ( LOG N )\n\n**UPVOTE IF HELPFuuL**\n\n**BINARY SEARCH SOLUTION**\n```\nclass Solution:\n    def searchMatrix(self, mat: List[List[int]], target: int) -> bool:\n        \n        m=len(mat)\n        n=len(mat[0])\n        \n        for i in range(m):\n            if mat[i][0]<=target and mat[i][-1]>=target:\n                lo=0\n                hi=n\n                while (lo<hi):\n                    mid=(lo+hi)//2\n                    \n                    if mat[i][mid]==target:\n                        return True\n                    elif mat[i][mid]<target:\n                        lo = mid + 1\n                    else:\n                        hi = mid\n                        \n        return False\n```\n![image](https://assets.leetcode.com/users/images/ae27af7f-fbb5-4d4a-be95-2faab90e51b9_1658629526.2394886.webp)\n
['Python3']