package org.ms.ds.stack;
import java.util.Stack;
/*
https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/
implement a function to find minimum element in stack with push and pop support
*/
public class MinimumElementInStackWithoutExtraSpace {
public static void main(String[] args) {
MinStackWithoutExtraSpace minStack = new MinStackWithoutExtraSpace();
minStack.push(10);
minStack.push(8);
minStack.push(18);
minStack.push(11);
minStack.push(22);
minStack.push(2);
minStack.push(-1);
System.out.println("Min => " + minStack.getMin());
minStack.pop();
System.out.println("Min => " + minStack.getMin());
minStack.pop();
System.out.println("Min => " + minStack.getMin());
}
}
class MinStackWithoutExtraSpace {
Stack<Integer> stack = new Stack();
int min = -1;
//while popping we will check with popped element is lower than minEle means its not actual value but a flag so we will return min instead and calculate min again using 2*min-stack.pop()
int pop() {
if (stack.size() == 0) {
return -1;
}else{
if(stack.peek() >= min) {
return stack.pop();
}else if(stack.peek()< min){
int temp=min;
min=2*min-stack.pop();
return temp;
}else {
return -1;
}
}
}
int top(){
if (stack.size() == 0) {
return -1;
}else{
if(stack.peek() >= min) {
return stack.peek();
}else if(stack.peek()< min){
return min;
}else {
return -1;
}
}
}
//will push flaged values instead of correct minimum
void push(int ele) {
if (stack.size() == 0) {
stack.push(ele);
min = ele;
} else {
if (ele >= min) {
stack.push(ele);
} else if (ele < min) {
stack.push(2*ele-min);
min=ele;
}
}
}
int getMin() {
if (stack.size() == 0) {
return -1;
} else {
return min;
}
}
}
Sunday, 19 July 2020
Minimum Element In Stack Without Extra Space
Minimum Element In Stack
package org.ms.ds.stack;
import java.util.Stack;
/*
https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/
implement a function to find minimum element in stack with push and pop support
1. maintain a supporting array
2. push both array if empty
3. push in main stack and check if element is lower than supporting stack top if yes push in supporting stack also
4. pop from both stack if popped element is equal to supporting top element
5. get min by peeking supporting top
*/
public class MinimumElementInStack {
public static void main(String[] args) {
MinStack minStack = new MinStack();
minStack.push(10);
minStack.push(8);
minStack.push(18);
minStack.push(11);
minStack.push(22);
minStack.push(2);
System.out.println("Min => "+minStack.getMin());
minStack.pop();
System.out.println("Min => "+minStack.getMin());
}
}
class MinStack {
Stack<Integer> stack = new Stack();
Stack<Integer> supportingStack = new Stack();
int pop() {
if (stack.size() == 0) {
return -1;
}
int a = stack.pop();
if (a == supportingStack.peek()) {
supportingStack.pop();
}
return a;
}
void push(int ele) {
stack.push(ele);
if (supportingStack.size() == 0 || supportingStack.peek() >= ele) {
supportingStack.push(ele);
}
}
int getMin() {
if(supportingStack.size()==0){
return -1;
}else{
return supportingStack.peek();
}
}
}
Rain Water Trapping
package org.ms.ds.stack;
import java.util.Arrays;
/*
https://www.geeksforgeeks.org/trapping-rain-water/
Input: arr[] = {3, 0, 2, 0, 4}
Output: 7
Input: arr[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
for each element
1. find max in left subarray and right subarray
2. then apply this formula
water[i] = min(MaxL,MaxR) - array[i]
3. sum water[i]
*/
public class RainWaterTrapping {
Integer getRWT(Integer[] a) {
Integer []maxL=new Integer[a.length];
Integer []maxR=new Integer[a.length];
Integer []water=new Integer[a.length];
Arrays.fill(maxL,0);
Arrays.fill(maxR,0);
maxL[0]=a[0];
for(Integer i=1;i<a.length;i++){
maxL[i]=Integer.max(maxL[i-1],a[i]);
}
maxR[a.length-1]=a[a.length-1];
for(Integer i=a.length-2;i>=0;i--){
maxR[i]=Integer.max(maxR[i+1],a[i]);
}
for(Integer i=0;i<a.length;i++){
water[i]=Integer.min(maxL[i],maxR[i])-a[i];
}
return Arrays.stream(water).mapToInt(Integer::intValue).sum();
}
public static void main(String[] args) {
RainWaterTrapping rainWaterTrapping = new RainWaterTrapping();
Integer[] test = new Integer[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
System.out.println("RainWaterTrapping => " +rainWaterTrapping.getRWT(test));
}
}
Max Area Rectangle In Binary Matrix
package org.ms.ds.stack;
import java.util.Arrays;
import java.util.Collections;
/*
https://www.geeksforgeeks.org/maximum-size-rectangle-binary-sub-matrix-1s/
Please refer Max Area Histogram program to solve this
Input:
0 1 1 0
1 1 1 1
1 1 1 1
1 1 0 0
Output :
1 1 1 1
1 1 1 1
we need to convert this problem into small problem
so we will convert this matrix as 4 histogram
H1:
0 1 1 0
H2:
0 1 1 0
1 1 1 1
H3:
0 1 1 0
1 1 1 1
1 1 1 1
H4: (will not consider histogram with base as 0)
0 1
1 1
1 1
1 1
MARBM answer = max(H1,H2,H3,H4)
*/
public class MaxAreaRectangleInBinaryMatrix {
Integer getMARBM(Integer[][] ba) {
MaxAreaHistogram maxAreaHistogram=new MaxAreaHistogram();
Integer max=Integer.MIN_VALUE;
Integer[] tempArray= new Integer[ba.length];
Arrays.fill(tempArray,0);
for (int i=0;i<ba.length;i++) {
for (int j=0;j<ba[i].length;j++) {
if(ba[i][j] ==0){
tempArray[j]=0;
}else {
tempArray[j] = tempArray[j] + ba[i][j];
}
}
Integer mah=maxAreaHistogram.getMAH(Arrays.asList(tempArray));
max=Integer.max(mah,max);
}
return max;
}
public static void main(String[] args) {
Integer[][] ba = new Integer[][]{{0, 1, 1, 0}, {1, 1, 1, 1}, {1, 1, 1, 1}, {1, 1, 0, 0}};
MaxAreaRectangleInBinaryMatrix maxAreaRectangleInBinaryMatrix=new MaxAreaRectangleInBinaryMatrix();
System.out.println("MaxAreaRectangleInBinaryMatrix " + maxAreaRectangleInBinaryMatrix.getMARBM(ba));
}
}
Max Area Histogram
package org.ms.ds.stack;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
/*
https://www.geeksforgeeks.org/largest-rectangle-under-histogram/
{6, 2, 5, 4, 5, 1, 6} => 12 max area rectangle
A building can be expanded in other building only when other building height >= current building height
here we will apply NSL and NSR
1. find NSR - NSL -1 = M , keep it in temp array
2. array[i] = array[i]*M
3. return max(array[])
note : for edge elements we will keep next/prev index(right) as height as in our case for last element 6 we will keep 7 and for first element 6(left) we will keep -1
*/
public class MaxAreaHistogram {
Integer getMAH(List<Integer> eles){
List<Integer> temp=new ArrayList<>();
List<Integer> nsl=getNSL(eles);
nsl.forEach(item-> System.out.print(item +" "));
System.out.println();
List<Integer> nsr=getNSR(eles);
nsr.forEach(item-> System.out.print(item +" "));
System.out.println();
for(int i=0;i<eles.size();i++){
temp.add(i,(eles.get(i))*(nsr.get(i)-nsl.get(i)-1));
}
return Collections.max(temp);
}
List<Integer> getNSL(List<Integer> eles){
List<Integer> temp=new ArrayList<>();
Stack<MAHPair> stack=new Stack<>();
for(int item=0;item< eles.size();item++){
if(stack.empty()){
temp.add(-1);
}else if(stack.size() > 0 && stack.peek().getNumber() < eles.get(item)){
temp.add(stack.peek().getIndex());
}else if(stack.size() > 0 && stack.peek().getNumber() >= eles.get(item)){
while(stack.size() > 0 && stack.peek().getNumber() >= eles.get(item)){
stack.pop();
}
if(stack.size() ==0){
temp.add(-1);
}else{
temp.add(stack.peek().getIndex());
}
}
stack.push(new MAHPair(eles.get(item),item));
}
return temp;
}
List<Integer> getNSR(List<Integer> eles){
List<Integer> temp=new ArrayList<>();
Stack<MAHPair> stack=new Stack<>();
for(int item=eles.size()-1;item>=0;item--){
if(stack.empty()){
temp.add(eles.size());
}else if(stack.size() > 0 && stack.peek().getNumber() < eles.get(item)){
temp.add(stack.peek().getIndex());
}else if(stack.size() > 0 && stack.peek().getNumber() >= eles.get(item)){
while(stack.size() > 0 && stack.peek().getNumber() >= eles.get(item)){
stack.pop();
}
if(stack.size() ==0){
temp.add(eles.size());
}else{
temp.add(stack.peek().getIndex());
}
}
stack.push(new MAHPair(eles.get(item),item));
}
Collections.reverse(temp);
return temp;
}
public static void main(String[] args) {
MaxAreaHistogram maxAreaHistogram=new MaxAreaHistogram();
List<Integer> sl=new ArrayList<>();
sl.add(6);
sl.add(2);
sl.add(5);
sl.add(4);
sl.add(5);
sl.add(1);
sl.add(6);
System.out.println("MAH : "+maxAreaHistogram.getMAH(sl));
}
}
class MAHPair{
Integer number;
Integer index;
public MAHPair(Integer number, Integer index) {
this.number = number;
this.index = index;
}
public Integer getNumber() {
return number;
}
public void setNumber(Integer number) {
this.number = number;
}
public Integer getIndex() {
return index;
}
public void setIndex(Integer index) {
this.index = index;
}
}
Stock Span Problem
package org.ms.ds.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/*
for any day previous element is consecutive/smaller or equal
{100,80,60,70,60,75,85} => {1, 1, 1, 2, 1, 4, 6}
here again we have to apply same logic as NGL
store element and its index value in stack
store diff b/w element index and stack element (which is gretaer )
*/
public class StockSPanProblem {
List<Integer> getSSp(List<Integer> eles){
List<Integer> temp=new ArrayList<>();
Stack<SSPPair> stack=new Stack<>();
for(int i=0;i<eles.size();i++){
if(stack.empty()){
temp.add(1);
}else if(!stack.empty() && eles.get(i) < stack.peek().getNumber()){
temp.add(i-stack.peek().getIndex());
}else if(!stack.empty() && eles.get(i) >= stack.peek().getNumber()){
while(eles.get(i) > stack.peek().getNumber()){
stack.pop();
}
if(stack.empty()){
temp.add(1);
}else{
temp.add(i-stack.peek().getIndex());
}
}
stack.push(new SSPPair(eles.get(i),i));
}
return temp;
}
public static void main(String[] args) {
StockSPanProblem stockSPanProblem=new StockSPanProblem();
List<Integer> sl=new ArrayList<>();
sl.add(100);
sl.add(80);
sl.add(60);
sl.add(70);
sl.add(60);
sl.add(75);
sl.add(85);
System.out.println(stockSPanProblem.getSSp(sl));
}
}
class SSPPair{
Integer number;
Integer index;
public SSPPair(Integer number, Integer index) {
this.number = number;
this.index = index;
}
public Integer getNumber() {
return number;
}
public void setNumber(Integer number) {
this.number = number;
}
public Integer getIndex() {
return index;
}
public void setIndex(Integer index) {
this.index = index;
}
}
Nearest Smaller To Right
package org.ms.ds.stack;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
/*
Identify : if we have nested loop and i depends on j then think of stack
Example : input array [1,3,2,4] => output [-1,2,-1,-1]
Algorithm: using stack
1. take one temporary list and stack
2. traverse given stack from end of list
3(a). if stack is empty push add -1 in list
3(b). if stack is not empty
if stack top element is smallest than source list element
copy stack top in temp list
else
keep popping element from stack until find smallest and add in temp list and if not found then add -1 in temp list
4. push new element in stack
5. return temp list after reverse
*/
public class NearestSmallerToRight {
List<Integer> getNSR(List<Integer> eles){
List<Integer> temp=new ArrayList<>();
Stack<Integer> stack=new Stack<>();
for(int item=eles.size()-1;item>=0;item--){
if(stack.empty()){
temp.add(-1);
}else if(stack.size() > 0 && stack.peek() < eles.get(item)){
temp.add(stack.peek());
}else if(stack.size() > 0 && stack.peek() >= eles.get(item)){
while(stack.size() > 0 && stack.peek() >= eles.get(item)){
stack.pop();
}
if(stack.size() ==0){
temp.add(-1);
}else{
temp.add(stack.peek());
}
}
stack.push(eles.get(item));
}
Collections.reverse(temp);
return temp;
}
public static void main(String[] args) {
NearestSmallerToRight nearestSmallerToRight=new NearestSmallerToRight();
List<Integer> sl=new ArrayList<>();
sl.add(1);
sl.add(3);
sl.add(2);
sl.add(4);
System.out.println(nearestSmallerToRight.getNSR(sl));
}
}
Nearest Smaller To Left
package org.ms.ds.stack;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/*
Identify : if we have nested loop and i depends on j then think of stack
Example : input array [1,3,2,4] => output [-1,1,1,2]
Algorithm: using stack
1. take one temporary list and stack
2. traverse given stack from start of list
3(a). if stack is empty push add -1 in list
3(b). if stack is not empty
if stack top element is lesser than source list element
copy stack top in temp list
else
keep popping element from stack until find lesser and add in temp list and if not found then add -1 in temp list
4. push new element in stack
5. return temp list
*/
public class NearestSmallerToLeft {
List<Integer> getNSL(List<Integer> eles){
List<Integer> temp=new ArrayList<>();
Stack<Integer> stack=new Stack<>();
for(int item=0;item< eles.size();item++){
if(stack.empty()){
temp.add(-1);
}else if(stack.size() > 0 && stack.peek() < eles.get(item)){
temp.add(stack.peek());
}else if(stack.size() > 0 && stack.peek() >= eles.get(item)){
while(stack.size() > 0 && stack.peek() >= eles.get(item)){
stack.pop();
}
if(stack.size() ==0){
temp.add(-1);
}else{
temp.add(stack.peek());
}
}
stack.push(eles.get(item));
}
return temp;
}
public static void main(String[] args) {
NearestSmallerToLeft nearestSmallerToLeft=new NearestSmallerToLeft();
List<Integer> sl=new ArrayList<>();
sl.add(1);
sl.add(3);
sl.add(2);
sl.add(4);
System.out.println(nearestSmallerToLeft.getNSL(sl));
}
}
Nearest Greater to Left
package org.ms.ds.stack;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
/*
Identify : if we have nested loop and i depends on j then think of stack
Example : input array [1,3,2,4] => output [-1,-1,3,-1]
Algorithm: using stack
1. take one temporary list and stack
2. traverse given stack from start of list
3(a). if stack is empty push add -1 in list
3(b). if stack is not empty
if stack top element is greater than source list element
copy stack top in temp list
else
keep popping element from stack until find greater and add in temp list and if not found then add -1 in temp list
4. push new element in stack
5. return temp list
*/
public class NearestGreaterToLeft {
List<Integer> getNGL(List<Integer> eles){
List<Integer> temp=new ArrayList<>();
Stack<Integer> stack=new Stack<>();
for(int item=0;item< eles.size();item++){
if(stack.empty()){
temp.add(-1);
}else if(stack.size() > 0 && stack.peek() > eles.get(item)){
temp.add(stack.peek());
}else if(stack.size() > 0 && stack.peek() <= eles.get(item)){
while(stack.size() > 0 && stack.peek() <= eles.get(item)){
stack.pop();
}
if(stack.size() ==0){
temp.add(-1);
}else{
temp.add(stack.peek());
}
}
stack.push(eles.get(item));
}
return temp;
}
public static void main(String[] args) {
NearestGreaterToLeft nearestGreaterToRight=new NearestGreaterToLeft();
List<Integer> sl=new ArrayList<>();
sl.add(1);
sl.add(3);
sl.add(2);
sl.add(4);
System.out.println(nearestGreaterToRight.getNGL(sl));
}
}
Thursday, 9 July 2020
Nearest Greater to right | Next Largest Element
package org.ms.ds.stack;
import java.util.*;
/*
Identify : if we have nested loop and i depends on j then think of stack
Example : input array [1,3,2,4] => output [3,4,4,-1]
Algorithm: using stack
1. take one temporary list and stack
2. traverse given stack from end of list
3(a). if stack is empty push add -1 in list
3(b). if stack is not empty
if stack top element is greater than source list element
copy stack top in temp list
else
keep popping element from stack until find greater and add in temp list and if not found then add -1 in temp list
4. push new element in stack
5. return temp list after reverse
*/
public class NearestGreaterToRight {
List<Integer> getNGR(List<Integer> eles){
List<Integer> temp=new ArrayList<>();
Stack<Integer> stack=new Stack<>();
for(int item=eles.size()-1;item>=0;item--){
if(stack.empty()){
temp.add(-1);
}else if(stack.size() > 0 && stack.peek() > eles.get(item)){
temp.add(stack.peek());
}else if(stack.size() > 0 && stack.peek() <= eles.get(item)){
while(stack.size() > 0 && stack.peek() <= eles.get(item)){
stack.pop();
}
if(stack.size() ==0){
temp.add(-1);
}else{
temp.add(stack.peek());
}
}
stack.push(eles.get(item));
}
Collections.reverse(temp);
return temp;
}
public static void main(String[] args) {
NearestGreaterToRight nearestGreaterToRight=new NearestGreaterToRight();
List<Integer> sl=new ArrayList<>();
sl.add(1);
sl.add(3);
sl.add(2);
sl.add(4);
System.out.println(nearestGreaterToRight.getNGR(sl));
}
}
Wednesday, 1 July 2020
find maximum length sub-array having equal number of 0's and 1's
package org.ms.ds.hashing;
import java.util.HashMap;
import java.util.Map;
class FindMaximumLengthSubArrayHavingEqualNumberOf0And1
{
public static void maxLenSubarray(int[] A)
{
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int maxLen = 0;
int ending_index = -1;
int sum = 0;
for (int i = 0; i < A.length; i++)
{
// sum of elements so far (replace 0 with -1)
sum += (A[i] == 0)? -1: 1;
if (map.containsKey(sum))
{
if (maxLen < i - map.get(sum))
{
maxLen = i - map.get(sum);
ending_index = i;
}
}
else {
map.put(sum, i);
}
}
if (ending_index != -1) {
System.out.println("Max length : "+maxLen);
System.out.println("[" + (ending_index - maxLen + 1) + ", " +
ending_index + "]");
}
else {
System.out.println("No sub-array exists");
}
}
public static void main (String[] args)
{
int[] A = { 0, 0, 1, 0, 1, 0, 0 };
maxLenSubarray(A);
}
}
Longest Sub-Array with Sum K
package org.ms.ds.hashing;
import java.util.HashMap;
import java.util.Map;
class FindMaximumLengthSubArrayHavingGivenSum
{
public static void maxLengthSubArray(int[] A, int K)
{
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int sum = 0;
int maxLen = 0;
int ending_index = -1;
for (int i = 0; i < A.length; i++)
{
sum = sum + A[i];
map.putIfAbsent(sum, i);
if (map.containsKey(sum - K) )
{
if(i-map.get(sum-K) > maxLen) {
maxLen = i - map.get(sum - K);
ending_index = i;
}
}
}
// print the max length
System.out.println("Array with max length for given sum is "+ maxLen);
// print the sub-array
System.out.println("[" + (ending_index - maxLen + 1) + ", " + ending_index + "]");
}
public static void main (String[] args)
{
int[] A = { 5, 6, -5, 5, 3, 5, 3, -2, 0 };
int sum = 8;
maxLengthSubArray(A, sum);
}
}
Subscribe to:
Posts (Atom)