TheAlgorithms/Python · error · IndexError

list index out of range

Error message

list index out of range

What it means

Raised by query() in data_structures/arrays/sparse_table.py when left_bound < 0 or right_bound >= len(sparse_table[0]) — i.e. the query range falls outside the array the table was built from. It raises IndexError with the message 'list index out of range', deliberately mimicking a native list indexing failure. Bounds are inclusive on both ends.

Source

Thrown at data_structures/arrays/sparse_table.py:81

    >>> query(build_sparse_table([8, 1, 0, 3, 4, 9, 3]), 0, 4)
    0
    >>> query(build_sparse_table([8, 1, 0, 3, 4, 9, 3]), 4, 6)
    3
    >>> query(build_sparse_table([3, 1, 9]), 2, 2)
    9
    >>> query(build_sparse_table([3, 1, 9]), 0, 1)
    1
    >>> query(build_sparse_table([8, 1, 0, 3, 4, 9, 3]), 0, 11)
    Traceback (most recent call last):
    ...
    IndexError: list index out of range
    >>> query(build_sparse_table([]), 0, 0)
    Traceback (most recent call last):
    ...
    ValueError: empty number list not allowed
    """
    if left_bound < 0 or right_bound >= len(sparse_table[0]):
        raise IndexError("list index out of range")

    # highest subset length of power of 2 that is within range [left_bound, right_bound]
    j = int(log2(right_bound - left_bound + 1))

    # minimum of 2 overlapping smaller subsets:
    # [left_bound, left_bound + 2 ** j - 1] and [right_bound - 2 ** j + 1, right_bound]
    return min(sparse_table[j][right_bound - (1 << j) + 1], sparse_table[j][left_bound])


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    print(f"{query(build_sparse_table([3, 1, 9]), 2, 2) = }")

View on GitHub (pinned to f5988cc097)

Solutions

1. Clamp/validate bounds against the source array length: 0 <= left <= right < len(arr).
2. Remember both bounds are inclusive — the last valid right_bound is len(arr) - 1.
3. Build the table and compute query bounds from the same array variable to avoid size drift.

Example fix

# before
query(table, 0, 11)  # table built from 7 elements

# after
query(table, 0, 6)  # inclusive bounds within 0..6

n = len(values)  # the array the table was built from
if not 0 <= left <= right < n:
    raise ValueError(f'bounds outside 0..{n-1}')
result = query(table, left, right)

When it happens

Trigger: Calling query(build_sparse_table([8,1,0,3,4,9,3]), 0, 11) where the table has 7 elements (valid range 0..6), or any negative left_bound.

Common situations: Inclusive-vs-exclusive bound confusion (passing right_bound == n), ranges from user input or coordinate math not clamped to the array, or reusing a table built for one array with bounds computed against another.

Related errors

• The parameter idx_original_string must be lower than len(bwt
• index out of range
• empty number list not allowed
• The parameter idx_original_string must not be lower than 0.
• Invalid value of 'position'

AI-assisted analysis of TheAlgorithms/Python@f5988cc097 (2026-08-14). Data as JSON: /api/errors/100a67ab558ecf9c. Report an issue: GitHub.