{"id":"38c6e70d-120d-4bb1-8426-3edac65ca06c","name":"Search In A Sorted 2d Array","description":"1. You are given a number n, representing the number of rows and columns of a square matrix.\r\n2. You are given n * n numbers, representing elements of 2d array a. \r\nNote - Each row and column is sorted in increasing order.\r\n3. You are given a number x.\r\n4. You are required to find x in the matrix and print it's location int (row, col) format as discussed in output format below.\r\n5. In case element is not found, print \"Not Found\".","inputFormat":"A number n\r\ne11\r\ne12..\r\ne21\r\ne22..\r\n.. n * n number of elements of array a\r\nA number x","outputFormat":"row\r\ncol of the location where element is found or \"Not Found\" if element is not in the matrix","constraints":"1 &lt;= n &lt;= 10^2\r\n-10^9 &lt;= e11, e12, .. n * m elements &lt;= 10^9\r\nAll rows and columns are sorted in increasing order","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\nusing namespace std;\n\nbool searchMatrix(vector<vector<int>>& matrix, int target) \n{\n // write your code here\n}\n\nint main() \n{\n int n, target;\n cin>>n;\n vector<vector<int>> mat(n, vector<int> (n));\n for(int i = 0; i < n; i++)\n for(int j = 0; j < n; j++)\n cin>>mat[i][j];\n cin>>target;\n\n if(!searchMatrix(mat, target)) cout<<\"Not Found\\n\";\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"def search(mat, n, x):\n #write your code here\n\n\n\nn= int(input())\narr = []\nfor i in range(n): \n a=[]\n for j in range(n):\n a.append(int(input()));\n arr.append(a)\nx=int(input()) \n \nsearch(arr,n,x)"}},"points":10,"difficulty":"medium","sampleInput":"4\r\n11\r\n12\r\n13\r\n14\r\n21\r\n22\r\n23\r\n24\r\n31\r\n32\r\n33\r\n34\r\n41\r\n42\r\n43\r\n44\r\n43","sampleOutput":"3\r\n2","questionVideo":"https://www.youtube.com/embed/N1RyGhXJ7Zc","hints":[],"associated":[{"id":"46438cc9-8c4a-4898-9de1-ef37308141e9","name":"(search2d) From which corner person should start to get the correct solution?","slug":"search2d-from-which-corner-person-should-start-to-get-the-correct-solution","type":4},{"id":"53cdea06-b0cc-47c9-b076-a115152d600c","name":"(search2d) What is the Space Comlexity of this question?","slug":"search2d-what-is-the-space-comlexity-of-this-question","type":4},{"id":"bec5ccef-8a6d-4a91-9b3d-45c9ba81e2b1","name":"(search2d) What can be the best Time Complexity of this question?","slug":"search2d-what-can-be-the-best-time-complexity-of-this-question","type":4}],"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":"f185374c-5448-476e-93e8-c4a4e9d1d520","name":"2D Arrays","slug":"2d-arrays-9999","type":0},{"id":"80fd7310-d6fc-4ff2-be20-a8ed56b8f04a","name":"Search In A Sorted 2d Array","slug":"search-in-a-sorted-2d-array","type":1}],"next":{"id":"b2894db9-f169-4777-898f-6a56905ac7ab","name":"Search in a 2D sorted array","type":3,"slug":"search-in-a-2d-sorted-array"},"prev":{"id":"49933746-05dd-4fad-950f-b14b28ded5b3","name":"Saddle Price","type":3,"slug":"saddle-price"}}}

Search In A Sorted 2d Array

1. You are given a number n, representing the number of rows and columns of a square matrix. 2. You are given n * n numbers, representing elements of 2d array a. Note - Each row and column is sorted in increasing order. 3. You are given a number x. 4. You are required to find x in the matrix and print it's location int (row, col) format as discussed in output format below. 5. In case element is not found, print "Not Found".

{"id":"38c6e70d-120d-4bb1-8426-3edac65ca06c","name":"Search In A Sorted 2d Array","description":"1. You are given a number n, representing the number of rows and columns of a square matrix.\r\n2. You are given n * n numbers, representing elements of 2d array a. \r\nNote - Each row and column is sorted in increasing order.\r\n3. You are given a number x.\r\n4. You are required to find x in the matrix and print it's location int (row, col) format as discussed in output format below.\r\n5. In case element is not found, print \"Not Found\".","inputFormat":"A number n\r\ne11\r\ne12..\r\ne21\r\ne22..\r\n.. n * n number of elements of array a\r\nA number x","outputFormat":"row\r\ncol of the location where element is found or \"Not Found\" if element is not in the matrix","constraints":"1 &lt;= n &lt;= 10^2\r\n-10^9 &lt;= e11, e12, .. n * m elements &lt;= 10^9\r\nAll rows and columns are sorted in increasing order","sampleCode":{"cpp":{"code":"#include <iostream>\n#include <vector>\nusing namespace std;\n\nbool searchMatrix(vector<vector<int>>& matrix, int target) \n{\n // write your code here\n}\n\nint main() \n{\n int n, target;\n cin>>n;\n vector<vector<int>> mat(n, vector<int> (n));\n for(int i = 0; i < n; i++)\n for(int j = 0; j < n; j++)\n cin>>mat[i][j];\n cin>>target;\n\n if(!searchMatrix(mat, target)) cout<<\"Not Found\\n\";\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"def search(mat, n, x):\n #write your code here\n\n\n\nn= int(input())\narr = []\nfor i in range(n): \n a=[]\n for j in range(n):\n a.append(int(input()));\n arr.append(a)\nx=int(input()) \n \nsearch(arr,n,x)"}},"points":10,"difficulty":"medium","sampleInput":"4\r\n11\r\n12\r\n13\r\n14\r\n21\r\n22\r\n23\r\n24\r\n31\r\n32\r\n33\r\n34\r\n41\r\n42\r\n43\r\n44\r\n43","sampleOutput":"3\r\n2","questionVideo":"https://www.youtube.com/embed/N1RyGhXJ7Zc","hints":[],"associated":[{"id":"46438cc9-8c4a-4898-9de1-ef37308141e9","name":"(search2d) From which corner person should start to get the correct solution?","slug":"search2d-from-which-corner-person-should-start-to-get-the-correct-solution","type":4},{"id":"53cdea06-b0cc-47c9-b076-a115152d600c","name":"(search2d) What is the Space Comlexity of this question?","slug":"search2d-what-is-the-space-comlexity-of-this-question","type":4},{"id":"bec5ccef-8a6d-4a91-9b3d-45c9ba81e2b1","name":"(search2d) What can be the best Time Complexity of this question?","slug":"search2d-what-can-be-the-best-time-complexity-of-this-question","type":4}],"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":"f185374c-5448-476e-93e8-c4a4e9d1d520","name":"2D Arrays","slug":"2d-arrays-9999","type":0},{"id":"80fd7310-d6fc-4ff2-be20-a8ed56b8f04a","name":"Search In A Sorted 2d Array","slug":"search-in-a-sorted-2d-array","type":1}],"next":{"id":"b2894db9-f169-4777-898f-6a56905ac7ab","name":"Search in a 2D sorted array","type":3,"slug":"search-in-a-2d-sorted-array"},"prev":{"id":"49933746-05dd-4fad-950f-b14b28ded5b3","name":"Saddle Price","type":3,"slug":"saddle-price"}}}
plane

Editor

Loading...

Search In A Sorted 2d Array

medium

1. You are given a number n, representing the number of rows and columns of a square matrix. 2. You are given n * n numbers, representing elements of 2d array a. Note - Each row and column is sorted in increasing order. 3. You are given a number x. 4. You are required to find x in the matrix and print it's location int (row, col) format as discussed in output format below. 5. In case element is not found, print "Not Found".

Constraints

1 <= n <= 10^2 -10^9 <= e11, e12, .. n * m elements <= 10^9 All rows and columns are sorted in increasing order

Format

Input

A number n e11 e12.. e21 e22.. .. n * n number of elements of array a A number x

Output

row col of the location where element is found or "Not Found" if element is not in the matrix

Example

Sample Input

4 11 12 13 14 21 22 23 24 31 32 33 34 41 42 43 44 43

Sample Output

3 2

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode