Application Developer

The question boils down to finding the number of connected components in an undirected graph. Now comparing the connected components of an undirected graph with this problem, the node of the graph will be the “1’s” (land) in the matrix. 
BFS or DFS can be used to solve this problem. In each BFS call, a component or a sub-graph is visited. We will call BFS on the next un-visited component. The number of calls to BFS function gives the number of connected components. A cell in 2D matrix has 8 neighbors. So for each cell, we process all its 8 neighbors. We keep track of the visited 1s so that they are not visited again using a visited matrix.
Time Complexity : O(m*n) where m*n is the size of the given matrix
Space Complexity : O(min(m,n))

The brute force solution is to traverse the array and to search elements one by one. Run a nested loop, outer loop for row and inner loop for the column
Check every element with x and if the element is found then print “element found”. If the element is not found, then print “element not found”.
Efficient Approach : The idea here is to remove a row or column in each comparison until an element is found. Start searching from the top-right corner of the matrix. There are three possible cases : 
1. The given number > the current number: This will ensure that all the elements in the current row are smaller than the given number as the pointer is already at the right-most elements and the row is sorted. Thus, the entire row gets eliminated and continues the search for the next row. 
2. The given number < the current number: This will ensure that all the elements in the current column are greater than the given number. Thus, the entire column gets eliminated and continues the search for the previous column, i.e. the column on the immediate left.
3. The given number == the current number: This will end the search.
• Algorithm: 
1. Let the given element be x, create two variable i = 0, j = n-1 as index of row and column
2. Run a loop until i = n
3. Check if the current element is greater than x then decrease the count of j. Exclude the current column.
4. Check if the current element is less than x then increase the count of i. Exclude the current row.
5. If the element is equal, then print the position and end.

The simple approach is to simply count the number of 0’s, 1’s, and 2’s. Then, place all 0’s at the beginning of the array followed by 1’s and 2's. The time complexity of this approach would be O(n) and space complexity O(1). 
However, the approach requires two traversals of the array. The question can also be solved in a single scan of the array by maintaining the correct order of 0’s, 1’s, and 2’s using variables. 
We divide the array into four groups using three pointers. Let us name these pointers as low, mid, and high.
1. a[0…low-1] only zeroes
2. a[low..mid-1] only ones
3. a[mid…high] unknown
4. a[high+1..n-1] only twos
Algorithm : 
1. Initialise three pointers low = 0, mid = 0 and high = n -1
2. Run a while loop until mid<=high : 
2.1 If (a[mid] ==0), then swap the element with the element low and increment low and mid (low++ and mid++).
2.2 If (a[mid] ==1), then increment mid (mid++).
2.3 If (a[mid] ==2), then swap it with an element in high range and decrement high (high--).

Two stacks can be used to implement a min Stack. One stack can be used to store the actual stack elements and the other auxiliary stack is used to store minimum values. The top element of the auxiliary stack will always store the minimum at that point of time. Let us see how push() and pop() operations work.
Push(int x) 
1) push x to the original stack (the stack with actual elements) 
2) compare x with the top element of the auxiliary stack. Let the top element be y. 
…..a) If x < y then push x to the auxiliary stack. 
…..b) If x > y then push y to the auxiliary stack.
int Pop() 
1) pop the top element from the auxiliary stack. This is necessary to update the auxiliary stack. 
2) pop the top element from the original stack and return it.
int getMin() 
1) Return the top element of the auxiliary stack.