{"id":"69150b55-dcdd-4853-9925-3efb64f882c9","name":"Search A 2d Matrix","description":"1. Write an efficient algorithm that searches for a value in a m x n matrix. This matrix has the following properties:\r\na). Integers in each row are sorted from left to right.\r\nb). The first integer of each row is greater than the last integer of the previous row.\r\n","inputFormat":"Input is managed for you\r\n","outputFormat":"Output is managed for you\r\n","constraints":"m == matrix.length\r\nn == matrix[i].length\r\n1 &lt;= m, n &lt;= 100\r\n-10^4 &lt;= matrix[i][j], target &lt;= 10^4\r\n","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n \nbool search(vector<vector<int>> &matrix,int target) {\n //write your code here\n}\n\nint main()\n{\n int m;\n cin>>m;\n int n;\n cin>>n;\n \n vector<vector<int>> matrix(m,vector<int>(n));\n \n for(int i=0; i < m;i++) {\n for(int j=0; j < n;j++) {\n cin>>matrix[i][j];\n }\n }\n \n int target;\n cin>>target;\n \n bool isFound = search(matrix,target);\n \n if(isFound == 0)\n cout<<\"false\";\n else if(isFound == 1)\n cout<<\"true\";\n}"},"java":{"code":"import java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n\r\n /*your task is to complete this function which returns true if target exists in the matrix\r\n else return false*/\r\n public static boolean search(int[][]matrix,int target) {\r\n //write your code here\r\n return false;\r\n }\r\n\r\n public static void main(String[]args) {\r\n //input work\r\n Scanner scn = new Scanner(System.in);\r\n int m = scn.nextInt();\r\n int n = scn.nextInt();\r\n\r\n int[][]matrix = new int[m][n];\r\n\r\n for(int i=0; i < m;i++) {\r\n for(int j=0; j < n;j++) {\r\n matrix[i][j] = scn.nextInt();\r\n }\r\n }\r\n\r\n int target = scn.nextInt();\r\n\r\n boolean isFound = search(matrix,target);\r\n System.out.println(isFound);\r\n\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5 4\r\n1 3 5 7\r\n10 11 16 20\r\n23 30 34 60\r\n62 63 65 68\r\n71 72 74 80\r\n65","sampleOutput":"true","questionVideo":"https://www.youtube.com/embed/EmpwQ4C6WJs","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"cb36811c-9cd7-4d80-aa52-ae9b8409862a","name":"Searching And Sorting For Intermediate","slug":"searching-and-sorting-for-intermediate-10001","type":0},{"id":"6863d922-ad9b-4e10-a08a-5248f0fd943f","name":"Search A 2d Matrix","slug":"search-a-2d-matrix","type":1}],"next":{"id":"4be0c4cb-1680-4740-a02a-b72b0d8d4a1d","name":"Search a 2D Matrix","type":3,"slug":"search-a-2d-matrix"},"prev":{"id":"66bc1624-9c2f-4de7-b610-27f4f6c13b2e","name":"Marks Of Pcm MCQ","type":0,"slug":"marks-of-pcm-mcq"}}}

Search A 2d Matrix

1. Write an efficient algorithm that searches for a value in a m x n matrix. This matrix has the following properties: a). Integers in each row are sorted from left to right. b). The first integer of each row is greater than the last integer of the previous row.

{"id":"69150b55-dcdd-4853-9925-3efb64f882c9","name":"Search A 2d Matrix","description":"1. Write an efficient algorithm that searches for a value in a m x n matrix. This matrix has the following properties:\r\na). Integers in each row are sorted from left to right.\r\nb). The first integer of each row is greater than the last integer of the previous row.\r\n","inputFormat":"Input is managed for you\r\n","outputFormat":"Output is managed for you\r\n","constraints":"m == matrix.length\r\nn == matrix[i].length\r\n1 &lt;= m, n &lt;= 100\r\n-10^4 &lt;= matrix[i][j], target &lt;= 10^4\r\n","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n \nbool search(vector<vector<int>> &matrix,int target) {\n //write your code here\n}\n\nint main()\n{\n int m;\n cin>>m;\n int n;\n cin>>n;\n \n vector<vector<int>> matrix(m,vector<int>(n));\n \n for(int i=0; i < m;i++) {\n for(int j=0; j < n;j++) {\n cin>>matrix[i][j];\n }\n }\n \n int target;\n cin>>target;\n \n bool isFound = search(matrix,target);\n \n if(isFound == 0)\n cout<<\"false\";\n else if(isFound == 1)\n cout<<\"true\";\n}"},"java":{"code":"import java.util.*;\r\nimport java.io.*;\r\n\r\npublic class Main {\r\n\r\n /*your task is to complete this function which returns true if target exists in the matrix\r\n else return false*/\r\n public static boolean search(int[][]matrix,int target) {\r\n //write your code here\r\n return false;\r\n }\r\n\r\n public static void main(String[]args) {\r\n //input work\r\n Scanner scn = new Scanner(System.in);\r\n int m = scn.nextInt();\r\n int n = scn.nextInt();\r\n\r\n int[][]matrix = new int[m][n];\r\n\r\n for(int i=0; i < m;i++) {\r\n for(int j=0; j < n;j++) {\r\n matrix[i][j] = scn.nextInt();\r\n }\r\n }\r\n\r\n int target = scn.nextInt();\r\n\r\n boolean isFound = search(matrix,target);\r\n System.out.println(isFound);\r\n\r\n }\r\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5 4\r\n1 3 5 7\r\n10 11 16 20\r\n23 30 34 60\r\n62 63 65 68\r\n71 72 74 80\r\n65","sampleOutput":"true","questionVideo":"https://www.youtube.com/embed/EmpwQ4C6WJs","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"cb36811c-9cd7-4d80-aa52-ae9b8409862a","name":"Searching And Sorting For Intermediate","slug":"searching-and-sorting-for-intermediate-10001","type":0},{"id":"6863d922-ad9b-4e10-a08a-5248f0fd943f","name":"Search A 2d Matrix","slug":"search-a-2d-matrix","type":1}],"next":{"id":"4be0c4cb-1680-4740-a02a-b72b0d8d4a1d","name":"Search a 2D Matrix","type":3,"slug":"search-a-2d-matrix"},"prev":{"id":"66bc1624-9c2f-4de7-b610-27f4f6c13b2e","name":"Marks Of Pcm MCQ","type":0,"slug":"marks-of-pcm-mcq"}}}
plane

Editor


Loading...

Search A 2d Matrix

medium

1. Write an efficient algorithm that searches for a value in a m x n matrix. This matrix has the following properties: a). Integers in each row are sorted from left to right. b). The first integer of each row is greater than the last integer of the previous row.

Constraints

m == matrix.length n == matrix[i].length 1 <= m, n <= 100 -10^4 <= matrix[i][j], target <= 10^4

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

5 4 1 3 5 7 10 11 16 20 23 30 34 60 62 63 65 68 71 72 74 80 65

Sample Output

true

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode