Skip to main content

Day 13: Largest Rectangle in Histogram: stack - leetcode - Python3

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

 

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

 

Constraints:

  • 1 <= heights.length <= 105
  • 0 <= heights[i] <= 104
SOLUTION:
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack: List[int] = []
        maxarea: int = 0

        for i, h in  enumerate(heights):
            start = i
            while stack and stack[-1][1] > h:
                index, height= stack.pop()
                maxarea = max(maxarea, height * (i-index))
                start = index
           
            stack.append((start, h))
       
        for i, h in stack:
            maxarea = max(maxarea, h * (len(heights)-i) )
        return maxarea
   

Time Complexity: O(n) ->The for loop iterates over the list heights once. The while loop iterates over the stack at most once for each bar. Therefore, the total time complexity of the code is O(n).

Space Complexity: O(n) -> The stack can store at most n elements, where n is the number of bars in the histogram. Therefore, the space complexity of the code is O(n).

How it works:

  1. The for loop iterates over the list heights. For each iteration, the current bar is stored in the variable h.
  2. The variable start is initialized to the current index i.
  3. The while loop checks if the stack is not empty and the top bar on the stack is taller than the current bar. If it is, we pop the top bar off the stack and update the variable start to the index of the popped bar.
  4. The stack.append((start, h)) line appends the current index i and the current bar h to the stack.
  5. The for loop iterates over the stack. For each iteration, the current index and height are stored in the variables i and h.
  6. The maxarea = max(maxarea, h * (len(heights)-i) ) line calculates the area of the rectangle formed by the current bar and the bars that are stacked below it.
  7. The return maxarea line returns the maximum area found.

The algorithm works by maintaining a stack of indices of the bars that form the top of the largest rectangle. The stack is initialized with the index of the first bar. For each subsequent bar, we check if it is taller than the top bar on the stack. If it is, we pop the top bar off the stack and add the new bar to the stack. We continue this process until we reach the end of the list.

Once we have processed all of the bars, we can calculate the area of the largest rectangle by multiplying the height of the top bar on the stack by the width of the rectangle. The width of the rectangle is the number of bars that are stacked below the top bar.

Comments

Popular posts from this blog

Bug Boundy Methodology, Tools & Resources

Start by defining a clear objective, such as exploiting a remote code execution (RCE) vulnerability or bypassing authentication on your target. Then, consider how you can achieve this goal using various attack vectors like XSS, SSRF, or others - these are simply tools to help you reach your objective. Use the target as how a normal user would, while browsing keep these questions in mind: 1)How does the app pass data? 2)How/where does the app talk about users? 3)Does the app have multi-tenancy or user levels? 4)Does the app have a unique threat model? 5)Has there been past security research & vulnerabilities? 6)How does the app handle XSS, CSRF, and code injection?

Install & set up mitmweb or mitmproxy in Linux

Step 1: Go to the mitmproxy page and download the binaries. Step 2: Install the downloaded tar file with the command " tar -xzf <filename>.tar.gz " Step 3: In the FoxyProxy add the proxy 127.0.0.1:8080  and turn it on. Step 4 : In the terminal run command " ./mitmweb " Step 5: Go to the page  http://mitm.it/   and download the mitmproxy's Certificate. Step 6: If you downloaded the certificate for Firefox, then go to " settings -> Privacy & Security -> Click View Certificates -> Click  Import ", then import the certificate.  Step 7: Now you are ready to capture the web traffic. Step 8 : In terminal run " ./mitmweb"

API Bug Bounty Hunting: Reconnaissance and Reverse Engineering an API

  In order to target APIs, you must first be able to find them.APIs meant for consumer use are meant to be easily discovered. Typically, the API provider will market their API to developers who want to be consumers. So, it will often be very easy to find APIs, just by using a web application as an end-user. The goal here is to find APIs to attack and this can be accomplished by discovering the API itself or the API documentation. Bug Boundy Methodology, Tools & Resources Start by defining a clear objective, such as exploiting a remote code execution (RCE) vulnerability or bypassing… adithyakrishnav.blogspot.com Reconnaissance Passive Reconnaissance It is obtaining information about a target without directly interacting with the target’s systems. Google Dorking Firstly, google search for “<app name> API”. intitle:” api” site:”google.com” inurl:”/api/v2" site:”google.com” inurl:”/api/v1" intext:”index of /” inurl:json site:”google.com” intitle:”index.of” intext:”api.t...