32 Evaluate Reverse Polish Notation
public int evalRPN(String[] tokens) {
// digitStack - if symbol.. pop to digits.. operate .. push in stack
String symbols = "+-*/";
Stack<String> digitStack = new Stack<>();
for(String s: tokens) {
// if digits
if(!symbols.contains(s)) {
digitStack.push(s);
}
else {
// operator.. so operate
int num1 = Integer.valueOf(digitStack.pop());
int num2 = Integer.valueOf(digitStack.pop());
if(s.equals("+")) {
digitStack.push(String.valueOf(num1+num2));
}
if(s.equals("-")) {
digitStack.push(String.valueOf(num2-num1));
}
if(s.equals("*")) {
digitStack.push(String.valueOf(num1*num2));
}
if(s.equals("/")) {
digitStack.push(String.valueOf(num2/num1));
}
}
}
return Integer.valueOf(digitStack.pop());
}
37_38 Largest Rectangle in Histogram/2D array
public int maximalRectangle(char[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
return -1;
int rows = matrix.length;
int cols = matrix[0].length;
int[][] dp = new int[rows][cols+1];
for(int r = 0 ; r < rows; r++) {
for(int c = 0; c < cols; c++) {
if(matrix[r][c] == '0') {
dp[r][c] = 0;
}
else {
// first row 1.. else add 1 to prev
dp[r][c] = (r == 0) ? 1 : dp[r-1][c] + 1;
}
}
}
int resultArea = 0;
int currMaxHistogramArea = 0;
for(int[] eachRow: dp) {
currMaxHistogramArea = getMaxAreaInHistogram(eachRow);
resultArea = Math.max(resultArea, currMaxHistogramArea);
}
return resultArea;
}
public int getMaxAreaInHistogram(int[] eachRow) {
int result = 0;
int n = eachRow.length;
Stack<Integer> hs = new Stack<Integer>();
hs.push(-1);
for(int i = 0; i < eachRow.length; ++i) {
while(hs.peek() != -1 && eachRow[hs.peek()] >= eachRow[i] )
result = Math.max(result, eachRow[hs.pop()] * (i -
hs.peek() - 1));
hs.push(i);
}
while(hs.peek() != -1) {
result = Math.max(result, eachRow[hs.pop()] * (n - hs.peek() -
1));
}
return result;
}
}
33 Valid Parentheses
public boolean isValid(String s) {
Map<Character, Character> hm = new HashMap<>();
hm.put('(',')'); hm.put('{','}'); hm.put('[',']');
Stack<Character> st = new Stack<>();
for(Character c: s.toCharArray()){
if(hm.keySet().contains(c)) {
st.push(c);
}
else { // closing brace
if(hm.values().contains(c)) { // if brace in values
if(st.isEmpty() || hm.get(st.pop()) != c)
return false;
}
else {
return false;
}
}
}
return st.isEmpty();
}
34 Longest Valid Parentheses (Two Pointers)
public int longestValidParentheses(String s) {
// Scan Left -> Right.. Count openBraces/ closedBraces..
// openBraces == closedBraces .. res = max(res, openBraces+closedBraces)
int openBraces = 0; int closedBraces = 0; int result = 0;
for(int i = 0; i < s.length(); i++) { // Scan Left -> Right
if(s.charAt(i) == '(') openBraces++;
else closedBraces++;
if(openBraces == closedBraces)
result = Math.max(result, openBraces + closedBraces);
else if(closedBraces >= openBraces) // *****IMP
openBraces = closedBraces = 0;
}
// Scan Right-> Left.. Count openBraces/ closedBraces..
// openBraces == closedBraces .. res = max(res, openBraces+closedBraces)
openBraces = 0; closedBraces = 0;
for(int i = s.length()-1; i >=0; i--) { // Scan Left -> Right
if(s.charAt(i) == '(') openBraces++;
else closedBraces++;
if(openBraces == closedBraces)
result = Math.max(result, openBraces + closedBraces);
else if(openBraces >= closedBraces ) // *****IMPORTANT
openBraces = closedBraces = 0;
}
return result;
35 Valid Palindrome (Two Pointers)
public boolean isPalindrome_removingSpacesDigitsNumbers(String s) {
int left = 0; int right = s.length()-1;
while(left < right) {
while(left < right && !Character.isLetterOrDigit(s.charAt(left)))
left++;
while(left < right && !Character.isLetterOrDigit(s.charAt(right)))
right--;
if(s.charAt(left) != s.charAt(right)) // Character.toLowerCase
return false;
left++; right--;
}
return true;
}
public boolean isPalindrome_removingOneCharacter(String s) {
// traverse from both ends..
// if diff && !foundDiff then foundDiff = true and remaining isPalindrome
int left = 0;
int right = s.length() -1;
boolean foundDiff = false;
while(left< right) {
if(s.charAt(left) != s.charAt(right)) {
if(!foundDiff) {
foundDiff = true;
if(isPalindrome(s, left+1, right))
left++;
else if( isPalindrome(s, left, right-1))
right--;
else
return false;
}
else {
return false;
}
}
else {
left++; right--;
}
}
return true;
}
private boolean isPalindrome(String s, int left, int right) {
while(left<right){
if(s.charAt(left) != s.charAt(right))
return false;
left++; right--;
}
return true;
}
