The "Hanging Line" (or "Suspension Line") method is an efficient technique for identifying the largest rectangular area within a histogram or a grid of binary values. It optimizes the naive brute-force approach from O(N²) to O(N) complexity.

Core Concept

Consider a histogram of bars with varying heights. For any bar at index i with height h[i], we define a "hanging line" as a vertical segment extending upward from the base to the top of the bar. To maximize the area of a rectangle anchored by this bar, we must extend the segment as far as possible to the left and right, ensuring no surrounding bars are shorter than the current bar.

Histogram Maximum Rectangle

To compute the left boundary (L) and right boundary (R) for each position, we use a jumping mechanism. If a neighbor is taller than or equal to the current height, we can skip over that neighbor's precomputed boundary, effectively compressing the search.

long long calculate_max_area(int n, const vector<int>& heights) {
    vector<int> left_limit(n), right_limit(n);
    for (int i = 0; i < n; ++i) {
        left_limit[i] = i;
        while (left_limit[i] > 0 && heights[i] <= heights[left_limit[i] - 1]) {
            left_limit[i] = left_limit[left_limit[i] - 1];
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        right_limit[i] = i;
        while (right_limit[i] < n - 1 && heights[i] <= heights[right_limit[i] + 1]) {
            right_limit[i] = right_limit[right_limit[i] + 1];
        }
    }

    long long max_area = 0;
    for (int i = 0; i < n; ++i) {
        max_area = max(max_area, (long long)(right_limit[i] - left_limit[i] + 1) * heights[i]);
    }
    return max_area;
}

Grid-Based Subrectangle Problems

The method extends naturally to 2D grid problems (e.g., finding the largest all-'F' subrectangle). We treat each row as a histogram base. For every cell (i, j), we maintain a height value representing the continuous veritcal accumulation of valid cells ending at that row. As we iterate through rows, we update the current histogram heights and apply the 1D hanging line logic.

// Example for grid height updates
for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < cols; ++j) {
        if (grid[i][j] == 'R') {
            heights[j] = 0;
        } else {
            heights[j]++;
        }
    }
    // Update boundaries and calculate area using logic similar to the histogram approach
    update_boundaries_and_max(heights);
}

The complexity analysis relies on amortization: since each pointer jump in the while loops moves to a previously validated boundary, each index is processed a constant number of times, resulting in a total time complexity of O(N*M) for a grid of size N x M.