Why does this O(n) stack-based solution get TLE?


  • 0
    B

    My solution got TLE on a test case contains thousands of 1. But I cannot figure out why. The time complexity is O(n), and the stack size keeps only 1 in this test case. It's strange that it got TLE.

    public class Solution {
        public int largestRectangleArea(int[] height) {
            int max = 0, i = 0;
            Stack<Integer> stack = new Stack<Integer>();
            
            while (i < height.length) {
                if (stack.empty() || height[i] > height[stack.peek()]) {
                    stack.push(i++);
                } else if (height[i] < height[stack.peek()]) {
                    int top = stack.pop();
                    max = Math.max(max, height[top] * (stack.empty() ? i : i-stack.peek()-1));
                } else {
                    i++;
                }
            }
            while (!stack.empty()) {
                int top = stack.pop();
                max = Math.max(max, height[top] * (stack.empty() ? i : i-stack.peek()-1));
            }
            
            return max;
        }
    }

  • 0
    M

    The reason could be class stack which is implemented internally as a growing array. Try replacing stack with LinkedList and use addFirst getFirst and removeFirst and see if it solves the problem. Mine passed the second time. There is also some randomness in the judging I guess.


  • 0
    J

    Because your max function is not a linear time function.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.