Bug Report for largest-rectangle-in-histogram, missing a testcase

[utkarshm12]

Bug Report for: https://neetcode.io/problems/largest-rectangle-in-histogram

I found a missing test case for this problem.

My submitted solution is currently accepted by the judge, but it produces an incorrect result for the following valid input, which appears to be missing from the existing test suite:

Test Case:

heights = [0,1,0,2,1,0,1,3,2,1,2,1]

Expected Output:

6

My Solution's Output:

5

Since this solution is accepted despite failing on this valid test case, it suggests that the current test suite does not cover this scenario, allowing incorrect approaches to pass.

My accepted solution:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int idl = 0, mnl = 0, idr = n - 1, mnr = 0, ans = 0;
        stack<int> st;

        for (int i = 0; i < n; i++) {
            mnl = min(mnl, heights[i]);
            mnr = min(mnr, heights[n - i - 1]);

            int arl = mnl * (i - idl + 1);
            int arr = mnr * (idr - n + i + 2);

            if (arl <= heights[i]) {
                arl = heights[i];
                idl = i;
                mnl = heights[i];
            }

            if (arr <= heights[n - i - 1]) {
                arr = heights[n - i - 1];
                idr = n - i - 1;
                mnr = heights[n - i - 1];
            }

            ans = max(ans, max(arl, arr));
        }

        return ans;
    }
};

This accepted solution is also available on my GitHub profile for reference.

Please verify this test case and consider adding it to the official test suite if appropriate so that solutions with this flaw are correctly rejected.

Thank you.