Yash
BAN USERokay here is an explanation:
Logic here is that each element in the hashtable keeps track of the sequence. So boundary elements of the sequence are important as the end element of the sequence points to beginning element of the sequence and beginning element of the sequence points to the end element. So whenever a new element is to be added to the sequence it picks up the boundary value and becomes the new boundary. Check how 8 is added to the table below:
Array a: [1, 6, 10, 4, 7, 8]
i: 1 Table: {1=1}
i: 6 Table: {1=1, 6=6}
i: 10 Table: {1=1, 6=6, 10=10}
i: 4 Table: {1=1, 4=4, 6=6, 10=10}
i: 7 Table: {1=1, 4=4, 6=7, 7=6, 10=10}
i: 8 Table: {1=1, 4=4, 6=8, 7=6, 8=6, 10=10}
straight out of cracking the coding interview. Copy pasting from the book directly:
Assumptions:
»»Rows are sorted left to right in ascending order. Columns are sorted top to bottom in ascending order.
»»Matrix is of size MxN.
This algorithm works by elimination. Every move to the left (--col) eliminates all the elements below the current cell in that column. Likewise, every move down eliminates all the elements to the left of the cell in that row.
1 boolean FindElem(int[][] mat, int elem, int M, int N) {
2 int row = 0;
3 int col = N-1;
4 while (row < M && col >= 0) {
5 if (mat[row][col] == elem) {
6 return true;
7 } else if (mat[row][col] > elem) {
8 col--;
9 } else {
10 row++;
11 }
12 }
13 return false;
14 }
Below is a code in Java with O(n) time complexity and O(m) space complexity
- Yash May 09, 2014