[Java/C++] FULL VISUALL explanation
Hello, Ladies-N-Gentlemen today we are going to solve a another easy-peasy question.\n\nI hope so, that questions is clear what it is all are talking about. Bec
Hello, **Ladies-N-Gentlemen** today we are going to solve a another easy-peasy question.\n\nI hope so, that questions is clear what it is all are talking about. Because, question statement is very clear!!\n\n```\n# Brute Force Approach\n```\nSo, let\'s talk about what will be **`Brute Force approach` to solve this problem.**\n\nThe very brute-force approach is, we will traverse it\'s every row & column of the matrix.\n\n**Let\'s understand it visually,**\n\n![image](https://assets.leetcode.com/users/images/01f6dc7a-0662-47d6-ab59-a9c196f332a8_1658635775.4245615.gif)\n\n\n**JAVA**\n```\nclass Solution {\n    public boolean searchMatrix(int[][] matrix, int target) {\n        for(int i = 0; i < matrix.length; i++){\n            for(int j = 0; j < matrix[0].length; j++){\n                if(matrix[i][j] == target) return true;\n            }\n        }\n        return false;\n    }\n}\n```\n**C++**\n```\nclass Solution {\npublic:\n    bool searchMatrix(vector<vector<int>>& matrix, int target) {\n        for(int i = 0; i < matrix.size(); i++){\n            for(int j = 0; j < matrix[0].size(); j++){\n                if(matrix[i][j] == target) return true;\n            }\n        }\n        return false;\n    }\n};\n```\nANALYSIS :-\nAs, you are seeing we are traversing it\'s all row and column therefore the **Time Complexity** will be **`O(N^2)`** And the **Space Complexity** will be **`O(1)`**\n\n```\n# Better Approach\n```\nLet\'s take an example to understand this approach,\n\n![image](https://assets.leetcode.com/users/images/17612fa0-eaeb-4e73-bf78-e65c2c87bf09_1658633211.0689182.png)\n\nSo, what we gonna do is we will start traversing from **`top-right corner`** or you can even start from **`bottom-left corner`**. Now you\'ll ask why not from **top-left OR bottom-right?** Well, there\'s a reason why not from there, we\'ll come to this point later on.\n\n**`Now, let\'s start traversing and understand it\'s visaully`**\n\n**`Note :-`** \n\n![image](https://assets.leetcode.com/users/images/b6e5483e-07e9-4200-9a5e-9a3d38307ae1_1658634345.6110325.png)\n\n![image](https://assets.leetcode.com/users/images/2a424696-79ea-47f1-82fe-836a00afa034_1658634181.3804603.gif)\n\n\nSo, what we are doing you got the idea,\n* If value is **`>`** then target, then move to **left i.e. j--**\n\n\n* If value is **`<`** then target, then move **down i.e. i++** \n* If value is **`==`** to target, **return true**\n* Else **return false**\n\nNow, let\'s code it up:-\n**Java**\n```\nclass Solution {\n    public boolean searchMatrix(int[][] matrix, int target) {\n        int i = 0;\n        int j = matrix[0].length - 1;\n        \n        while(i >= 0 && i < matrix.length && j >= 0 && j < matrix[0].length){\n            if(matrix[i][j] == target) return true;\n            else if(matrix[i][j] > target) j--;\n            else if(matrix[i][j] < target) i++;\n        }\n        return false;\n    }\n}\n```\n**C++**\n```\nclass Solution {\npublic:\n    bool searchMatrix(vector<vector<int>>& matrix, int target) {\n        int i = 0;\n        int j = matrix[0].size() - 1;\n        \n        while(i >= 0 && i < matrix.size() && j >= 0 && j < matrix[0].size()){\n            if(matrix[i][j] == target) return true;\n            else if(matrix[i][j] > target) j--;\n            else if(matrix[i][j] < target) i++;\n        }\n        return false;\n    }\n};\n```\nANALYSIS :-\n* **Time Complexity :-** It will be **`O(row + column)`** because we are traversing every row & column only once\n\n* **Space Complexity :-** It will be **`O(1)`** as we are not using any extra memory OR space
['C', 'Java']