I am working on leetcode question 84, maximal rectangles. When testing, I come across this bizarre case where the stack seems to add to the tail. I confirmed this using print statements and an iterator object.
The test case is: [4,2,0,3,2,5]
The second to last element in the array, 2, appears to be pushed to the tail, right under 0 (It should be pushed to the top. In my print statements, val:x gap:y appears when an element is popped, x y z appears when an element is pushed, and added: x is what the iterator prints. The whole stack is iterated through at each increment through the array. Code is here. I'm sure just posting a blob of code like this is bad etiquette so feel free to provide some criticism.
class Solution {
public int largestRectangleArea(int[] heights) {
//use a stack
//if element is bigger than top of stack, than add element to stack
//if element is same as top, add element to stack
//if element is less than top, pop all elements and calculate areas, also keep track of area of new top
Deque<Helper> myStack = new ArrayDeque<Helper>();
if (heights.length == 0 || heights == null) return 0;
if (heights.length == 1) return heights[0];
int poppedLength = 0;
int area;
int maxArea = 0;
Helper previous = new Helper(heights[0]);
myStack.push(previous);
for (int i = 1; i < heights.length; i++) { //iterate through input array
Iterator<Helper> myIt = myStack.iterator();
while (myIt.hasNext()) { //iterate through stack, for testing purposes
System.out.print(myIt.next().toString());
System.out.println();
}
if (!myStack.isEmpty()) {
if (heights[i] >= myStack.peek().getValue()) {//if curr element is greater than last, push current element
myStack.push(new Helper(heights[i]));
System.out.print("added1: "); //testing print statements
System.out.println(heights[i]);
} else {
while (heights[i] < myStack.peek().getValue()) { //if current element is less than head of stack, pop elements from stack until current is >= head of stack
Helper popped = myStack.pop();
poppedLength++;
area = (poppedLength + popped.getGapLength()) * popped.getValue();
System.out.print(poppedLength + popped.getGapLength()); //print statements for testing
System.out.print(" ");
System.out.print(popped.getValue());
System.out.print(" ");
System.out.print(area);
System.out.println();
if (area > maxArea) maxArea = area; //update max
if (myStack.isEmpty()) break;
}
if (!myStack.isEmpty()) {
myStack.peek().setGapLength(poppedLength + myStack.peek().getGapLength());
}
myStack.add(new Helper(heights[i], poppedLength)); //push current, THIS IS WHERE THE ERROR IS OCCURING
System.out.print("added2: ");
System.out.println(heights[i]);
poppedLength = 0;
}
} else {//if stack is empty for some reason, this actually should never execute
myStack.push(new Helper(heights[i]));
}
}
while (!myStack.isEmpty()) {//remove rest of elements in the stack
Helper popped = myStack.pop();
poppedLength++;
area = (poppedLength + popped.getGapLength()) * popped.getValue();
if (area > maxArea) maxArea = area;
System.out.print(poppedLength + popped.getGapLength());
System.out.print(" ");
System.out.print(popped.getValue());
System.out.print(" ");
System.out.print(area);
System.out.println();
}
return maxArea;
}
class Helper {//the elements of the stack
private int value;
private int gapLength;
public Helper(int val) {
value = val;
gapLength = 0;
}
public Helper(int val, int gap) {
value = val;
gapLength = gap;
}
public int getValue() {
return value;
}
public int getGapLength() {
return gapLength;
}
public void setGapLength(int length) {
gapLength = length;
}
public String toString() {
String retStr = "Val: " + Integer.toString(value) + " Gap:" + Integer.toString(gapLength) + " ";
return retStr;
}
}
}
The way you're approaching the problem, by breaking it into multiple functions, is good. However, it's hard to debug for us.
This'd pass through:
class Solution {
public static int largestRectangleArea(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int[] leftReduce = new int[height.length];
int[] rightReduce = new int[height.length];
rightReduce[height.length - 1] = height.length;
leftReduce[0] = -1;
for (int i = 1; i < height.length; i++) {
int p = i - 1;
while (p >= 0 && height[p] >= height[i]) {
p = leftReduce[p];
}
leftReduce[i] = p;
}
for (int i = height.length - 2; i >= 0; i--) {
int p = i + 1;
while (p < height.length && height[p] >= height[i]) {
p = rightReduce[p];
}
rightReduce[i] = p;
}
int maxArea = 0;
for (int i = 0; i < height.length; i++) {
maxArea = Math.max(maxArea, height[i] * (rightReduce[i] - leftReduce[i] - 1));
}
return maxArea;
}
}
Just like the comments under the question, I'm also a bit puzzled with this line:
Deque<Helper> myStack = new ArrayDeque<Helper>();
We would want to write bug-free and clean codes based on standards and conventions (e.g., c1, 2, c++1, 2, java1, 2, c#1, 2, python1, javascript1, go1, rust1).
The time to implement a solution during the interview is pretty limited. Make sure to not run out of time by complicating the design of your codes.