{"id":"645af132-53e3-4fa4-bbef-0de1bd72ffd6","name":"Search A 2d Matrix - 2","description":"1. Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:\r\na). Integers in each row are sorted in ascending from left to right.\r\nb). Integers in each column are sorted in ascending from top to bottom.","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;= n, m &lt;= 300\r\n-10^9 &lt;= matix[i][j] &lt;= 10^9\r\n-10^9 &lt;= target &lt;= 10^9","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nbool search(vector<vector<int>>& matrix, int target){\n // write your code here\n \n}\n\nint main(){\n int n, m, target;\n cin >> m;\n cin >> n;\n \n vector<vector<int>> matrix(m, vector<int> (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 cin >> target;\n \n bool isFound = search(matrix, target);\n if(isFound == 0){\n cout << \"false\" << endl;\n }else{\n cout << \"true\" << endl;\n }\n\n return 0;\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 5\r\n1 4 7 11 15\r\n2 5 8 12 20\r\n4 6 9 16 22\r\n10 13 14 17 24\r\n18 21 23 26 30\r\n12","sampleOutput":"true","questionVideo":"https://www.youtube.com/embed/iZ4xURJa0oQ","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":"e6abe9fb-3923-4483-9249-57247f97b6ff","name":"Search A 2d Matrix - 2","slug":"search-a-2d-matrix-2","type":1}],"next":{"id":"68845a7d-caf5-4521-b7d3-40d7c4f12578","name":"Search A 2d Matrix - 2","type":3,"slug":"search-a-2d-matrix-2"},"prev":{"id":"ed391dfa-9e82-4b8c-af4d-2020479c450f","name":"Search A 2d Matrix MCQ","type":0,"slug":"search-a-2d-matrix-mcq"}}}

Search A 2d Matrix - 2

1. Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties: a). Integers in each row are sorted in ascending from left to right. b). Integers in each column are sorted in ascending from top to bottom.

{"id":"645af132-53e3-4fa4-bbef-0de1bd72ffd6","name":"Search A 2d Matrix - 2","description":"1. Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties:\r\na). Integers in each row are sorted in ascending from left to right.\r\nb). Integers in each column are sorted in ascending from top to bottom.","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;= n, m &lt;= 300\r\n-10^9 &lt;= matix[i][j] &lt;= 10^9\r\n-10^9 &lt;= target &lt;= 10^9","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nbool search(vector<vector<int>>& matrix, int target){\n // write your code here\n \n}\n\nint main(){\n int n, m, target;\n cin >> m;\n cin >> n;\n \n vector<vector<int>> matrix(m, vector<int> (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 cin >> target;\n \n bool isFound = search(matrix, target);\n if(isFound == 0){\n cout << \"false\" << endl;\n }else{\n cout << \"true\" << endl;\n }\n\n return 0;\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 5\r\n1 4 7 11 15\r\n2 5 8 12 20\r\n4 6 9 16 22\r\n10 13 14 17 24\r\n18 21 23 26 30\r\n12","sampleOutput":"true","questionVideo":"https://www.youtube.com/embed/iZ4xURJa0oQ","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":"e6abe9fb-3923-4483-9249-57247f97b6ff","name":"Search A 2d Matrix - 2","slug":"search-a-2d-matrix-2","type":1}],"next":{"id":"68845a7d-caf5-4521-b7d3-40d7c4f12578","name":"Search A 2d Matrix - 2","type":3,"slug":"search-a-2d-matrix-2"},"prev":{"id":"ed391dfa-9e82-4b8c-af4d-2020479c450f","name":"Search A 2d Matrix MCQ","type":0,"slug":"search-a-2d-matrix-mcq"}}}
plane

Editor

Loading...

Search A 2d Matrix - 2

medium

1. Write an efficient algorithm that searches for a target value in an m x n integer matrix. The matrix has the following properties: a). Integers in each row are sorted in ascending from left to right. b). Integers in each column are sorted in ascending from top to bottom.

Constraints

m == matrix.length n == matrix[i].length 1 <= n, m <= 300 -10^9 <= matix[i][j] <= 10^9 -10^9 <= target <= 10^9

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

5 5 1 4 7 11 15 2 5 8 12 20 4 6 9 16 22 10 13 14 17 24 18 21 23 26 30 12

Sample Output

true

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode