Construct four auxiliary vectors of size n and initialize them by - 1
int [ ] leftMin = new int [ n ] ; int [ ] rightMin = new int [ n ] ; int [ ] leftMax = new int [ n ] ; int [ ] rightMax = new int [ n ] ; Arrays . fill ( leftMin , - 1 ) ; Arrays . fill ( leftMax , - 1 ) ; Arrays . fill ( rightMax , - 1 ) ; Arrays . fill ( rightMin , - 1 ) ;