Java ArrayDeque push() seems to add to front/tail of stack [potential bug]

Question

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;
        }
    }
}

I do not understand the question but I can guarantee you that there is no fundamental error in ArrayDeque. Did you intentionally use add instead of push in the marked line? — luk2302
– luk2302, Commented Jul 8, 2020 at 19:13
I did not, but they should have identical functionality right? Other test cases worked fine — valentinocc
– valentinocc, Commented Jul 8, 2020 at 19:16
@valentinocc You can verify it by reading documentation: ArrayDeque — akuzminykh
– akuzminykh, Commented Jul 8, 2020 at 19:17
Wow! That was actually it. For some reason, there seems to be a case where add and push do something different. That's wild. I'll post an answer when I figure out what the exact problem was. Amazing that it passes ~50 cases before failing because of this. @luk2302 — valentinocc
– valentinocc, Commented Jul 8, 2020 at 19:23

Emma Marcier · Accepted Answer · 2020-07-08 19:27:29Z

1

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>();

References

For additional details, you can see the Discussion Board. There are plenty of accepted solutions with a variety of languages and explanations, efficient algorithms, as well as asymptotic time/space complexity analysis^{1, 2} in there.

Since you are preparing for interviews:

We would want to write bug-free and clean codes based on standards and conventions (e.g., c^{1, 2}, c++^{1, 2}, java^{1, 2}, c#^{1, 2}, python¹, javascript¹, go¹, rust¹).
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.

Good luck with your interviews! ˆ_ˆ

edited Jul 8, 2020 at 19:27

answered Jul 8, 2020 at 19:16

Emma Marcier

27.8k12 gold badges49 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

valentinocc Over a year ago

Thanks. I like the discussion board solutions. I was just wondering what was going wrong with my solution. I understand it would take awhile to debug though

valentinocc Over a year ago

Thanks for the interview resources :). I am preparing

valentinocc · Accepted Answer · 2020-07-15 01:22:29Z

0

I was not able to figure out exactly what my bug was but was able to fix the issue by calling the push() method instead of both the push() and add() methods. I suspect that the methods rely on not being used interchangeably.

answered Jul 15, 2020 at 1:22

valentinocc

3211 gold badge3 silver badges12 bronze badges

Collectives™ on Stack Overflow

Java ArrayDeque push() seems to add to front/tail of stack [potential bug]

2 Answers 2

References

Since you are preparing for interviews:

Good luck with your interviews! ˆ_ˆ

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

References

Since you are preparing for interviews:

Good luck with your interviews! ˆ_ˆ

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related