2
\$\begingroup\$

Here's my solution but I am looking for ways to improve the time complexity of solution. Also this question is categorized as being solved by stack so I would like to know how to approach it using stacks?

Problem statement: Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. enter image description here

class Solution:
    # @param A : list of integers
    # @return an integer
    def largestRectangleArea(self, A):
        global_max_sum = 0
        if len(A) == 0:
            return None
        for i in range(len(A)):
            count = 1
            round_max_sum = 0
            while i+count  <= len(A)-1:
                sum = min(A[i:i+count+1]) *  (count+1)
                count += 1
                if sum >= round_max_sum:
                    round_max_sum = sum
                if round_max_sum > global_max_sum:
                    global_max_sum = round_max_sum
        return max(global_max_sum, max(A))

s = Solution()
#list = []
#list = [1]
#list = [ 2, 82, 11, 89, 7, 21, 92, 13, 11, 94, 4, 96, 3 ]
#list = [ 90, 58, 69, 70, 82, 100, 13, 57, 47, 18 ]
"""
list =  [ 65, 19, 8, 39, 14, 21, 83, 87, 95, 11, 14,
          58, 11, 90,34, 96, 34, 62, 96, 38, 58, 57,
          12, 78, 57, 60, 7, 58,56, 49, 36, 67, 69,
          30, 74, 46, 97, 62, 47, 42, 43, 98,60, 32,
          39, 75, 69, 28, 35, 52, 89, 78, 4, 26, 65,
          21,39, 89, 87, 69, 48, 60, 6, 21, 5, 98, 52, 59 ]
"""
#list = [51,33]
list = [ 6, 2, 5, 4, 5, 1, 6 ]

print(s.largestRectangleArea(list))
\$\endgroup\$
5
  • 2
    \$\begingroup\$ stackoverflow.com/a/4690790/4480692 \$\endgroup\$ – Curt F. Jun 3 '16 at 2:58
  • \$\begingroup\$ @MonaJalal as I have indicated that the "time complexity" you are looking for has nothing to do with your code, all to do with how fast you are able to give the website an answer, see my answer here... you seem to take questions from the "interview bit" website and post them here, but the "time complexity" is not your code, but how quickly you come up with code, type it in, and hit the submit button. Good Luck ! \$\endgroup\$ – Edwin van Mierlo Jun 3 '16 at 8:20
  • \$\begingroup\$ @EdwinvanMierlo Do you have any evidence to back up this claim? Many such sites (Project Euler, Google Code Jam) tune their timeouts so that slower algorithms can not finish in the correct time limit, and you really need to find the best solution - O(n) using a stack here - to validate everything. "Time complexity" is a well defined term in computer science. \$\endgroup\$ – Quentin Pradet Sep 8 '16 at 4:39
  • \$\begingroup\$ @QuentinPradet at the time of the OP's first post (linked in my comment) I did check out that particular website with the original code using two logins. One I typed slowly and missed the mark. Two I copied/paste the code, and got the mark. So that prompted me for highlighting this in the first post, and commenting/referencing this in the comments here. Hope that explains it. However I did not down-vote or flagged the post, as someone may go through the review exercise if they want to. \$\endgroup\$ – Edwin van Mierlo Sep 8 '16 at 7:53
  • \$\begingroup\$ @EdwinvanMierlo OK, Thanks. Very surprising. \$\endgroup\$ – Quentin Pradet Sep 8 '16 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.