# UNDF: UNDF-2026-000000691
# UNDF: (pending)
# pandas-0002: _get_level_lengths — hidden_elements list scan O(R×L×H)

## CWE-407 — Algorithmic Complexity: O(R×L×H) list-contains in DataFrame styler render

| Field | Value |
|-------|-------|
| ID | pandas-0002 |
| Severity | MEDIUM |
| Ecosystem | pandas |
| Package | `pandas` |
| File | `pandas/io/formats/style_render.py` |
| Lines | 1840–1870 |
| Complexity | O(R×L×H) — rows × index levels × hidden elements |
| Hot path | `_get_level_lengths()` called on every `Styler.render()` / `to_html()` |

## Background

`_get_level_lengths(index, sparsify, max_index, hidden_elements)` computes span
lengths for rendering a (Multi)Index in HTML/LaTeX output.  It is called twice
per render: once for row index, once for column index.  `hidden_elements` is the
list of integer positions that should be omitted from the rendered output — set
by `Styler.hide(rows)` or `Styler.hide(columns)`.

## Defect

```python
# pandas/io/formats/style_render.py  lines 1840–1870
if hidden_elements is None:
    hidden_elements = []          # list — default type

# ...
for i, value in enumerate(levels):
    if i not in hidden_elements:  # DEFECT: O(H) list scan
        lengths[(0, i)] = 1
# ...

for i, lvl in enumerate(levels):
    for j, row in enumerate(lvl):
        if not sparsify:
            if j not in hidden_elements:          # O(H) list scan
                lengths[(i, j)] = 1
        elif (row is not lib.no_default) and (j not in hidden_elements):  # O(H)
            ...
        elif j not in hidden_elements:            # O(H)
            ...
```

`hidden_elements` is declared as `Sequence[int]` and stored as a plain `list`:

```python
# pandas/io/formats/style_render.py  line 131
self.hidden_rows: Sequence[int] = []
self.hidden_columns: Sequence[int] = []
```

Each `j not in hidden_elements` performs a linear scan.  The outer loops run
R×L times (rows × MultiIndex levels), so total work is O(R×L×H).

### When does this matter?

Users calling `styler.hide(subset=large_slice)` on wide DataFrames or tall
DataFrames with MultiIndex before rendering: e.g. hiding 80% of 10,000 rows
in a 3-level MultiIndex generates ~24,000 list scans of length ~8,000 = 192M
comparisons per render.

## Complexity table

| Rows (R) | Hidden (H) | Levels (L) | list ops | set ops | Speedup |
|---------|----------|-----------|---------|---------|---------|
| 1,000 | 500 | 3 | 1,500,000 | 3,000 | 500× |
| 5,000 | 2,500 | 3 | 37,500,000 | 15,000 | 2,500× |
| 10,000 | 8,000 | 3 | 240,000,000 | 30,000 | 8,000× |

## Fix

Convert `hidden_elements` to a `set` at the point of use in
`_get_level_lengths`, or store it as a `frozenset` in `StylerRenderer`:

```python
def _get_level_lengths(
    index: Index,
    sparsify: bool,
    max_index: int,
    hidden_elements: Sequence[int] | None = None,
):
    if hidden_elements is None:
        hidden_elements_set: frozenset[int] = frozenset()
    else:
        hidden_elements_set = frozenset(hidden_elements)  # FIX: O(1) lookup

    # ...
    for i, value in enumerate(levels):
        if i not in hidden_elements_set:          # O(1)
            lengths[(0, i)] = 1
    # ...
    for i, lvl in enumerate(levels):
        for j, row in enumerate(lvl):
            if j not in hidden_elements_set:      # O(1)
                ...
```

Alternatively, store `self.hidden_rows` and `self.hidden_columns` as
`set[int]` rather than `list[int]` throughout `StylerRenderer`, since
membership testing (not ordering) is the only operation performed on them
in the render path.
