ankit.hbtik
BAN USER//We will maintain one auxiliary stack which will store
//only the minimum value from the main stack.
//Also, the element from top of the auxiliary stack will
//be removed when we do pop operation and the top element
//from both the stacks are same.
public class Stack {
private int size;
private int[] arr;
private int[] minArr;
private int top;
private int topMin;
public Stack(int size){
this.size=size;
top=-1;
topMin=-1;
arr=new int[size];
minArr=new int[size];
}
public void push(int val){
if(top==size-1){
System.out.println("Stack full !! Cannot do PUSH operation.");
return;
}
arr[top++]=val;
if(topMin!=-1){
if(minArr[topMin]<=val){
minArr[topMin++]=val;
}
}
else{
minArr[topMin++]=val;
}
}
public int pop(){
if(top==-1){
System.out.println("Stack empty !! Cannot do POP operation.");
return 0;
}
if(arr[top]==minArr[topMin]){
topMin--;
}
return arr[top--];
}
public int min(){
return minArr[topMin];
}
}
//Considering 'n' a global variable representing size of matrix
//Considering matrix to be in the form of double dimension array of size (nXn )
public int maxDiffInMatrix(int arr[][]){
int max=arr[1][1];
int min=arr[0][0];
int a=0,b=0,c=1,d=1;
//Finding maximum arr[c][d].....complexity n^2
for(int i=1;i<n;i++){
for(int j=1;j<n;j++){
if(arr[i][j]>max){
max=arr[i][j];
c=i;
d=j;
}
}
}
//Finding minimum arr[a][b]........complexity n^2
for(int m=0;m<c;m++){
for(int n=0;n<d;n++){
if(arr[m][n]<min){
min=arr[m][n];
a=m;
b=n;
}
}
}
//Returning desired value.....final complexity: (n^2)+(n^2)= O(n^2)
return (arr[c][d]-arr[a][b]);
}
- ankit.hbtik October 26, 2013