CODEWITHSUNDEEP
javaalgorithmlanguage-agnostic
user2039136
user2039136

Reputation: 55

finding time and space complexity of the given java code

hi i need to find the time and space complexity of the program, pls help, if possible please suggest the optimization that can be performed, .........................................................................................................................................................................................

public class Sol {
    public int findMaxRectangleArea(int [][] as) {
        if(as.length == 0)
       return 0;
    int[][] auxillary = new int[as.length][as[0].length];
        for(int i = 0; i < as.length; ++i) {
            for(int j = 0; j < as[i].length; ++j) {
            auxillary[i][j] = Character.getNumericValue(as[i][j]);
        }
        }
        for(int i = 1; i < auxillary.length; ++i) {
        for(int j = 0; j < auxillary[i].length; ++j) {
            if(auxillary[i][j] == 1)
                    auxillary[i][j] = auxillary[i-1][j] + 1;
            }
        }

    int max = 0;
        for(int i = 0; i < auxillary.length; ++i) {
            max = Math.max(max, largestRectangleArea(auxillary[i]));
        }
        return max;
    }

    private int largestRectangleArea(int[] height) {
        Stack<Integer> stack =
        new Stack<Integer>();
        int max = 0;
        int i = 0;
        while(i < height.length) {
            if(stack.isEmpty() ||
                height[i] >= stack.peek()) {
                stack.push(height[i]);
            i++;
            }
            else {
            int count = 0;
            while(!stack.isEmpty() &&
                stack.peek() > height[i]) {
                    count++;
                    int top = stack.pop();
                max = Math.max(max, top * count);
                }
            for(int j = 0; j < count + 1; ++j) {
                    stack.push(height[i]);
                }
                i++;
            }
        }

        int count = 0;
        while(!stack.isEmpty()) {
            count++;
            max = Math.max(max, stack.pop() * count);
        }
        return max;
    }

thank you in advance

Upvotes: 0

Views: 1392

Answers (1)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 71009

To find the space complexity take a look at the variables you declare and are larger than a single primitive variable. In fact I believe your space complexity will be determined my the array auxilary and the Stack stack. The size of the first one is pretty clear and I don't completely understand the second one but I see it's size will never be greater than the one of the array. So I would say the space complexity is O(size of(auxilary)) or O(N * M) where N=as.length() and M = as[0].length.

Now the time complexity is a bit trickier. You have two cycles over the whole auxilary array so for sure time complexity is at least O( N * M). You also have another cycle that invokes largestRectangleArea for each row of auxilary. If I get the code in this function correctly it seems this function is again linear, but I am not sure here. Since you know the logic better probably you will be able to compute its complexity better.

Hope this helps.

Upvotes: 1

Related Questions