Count Smaller Elements to the Right in Python

Return a list where each index counts how many elements to its right are smaller than that element using a clean O(n²) nested-loop approach.

Easy Python 3.9+ Aug 9, 2026 Algorithms & data structures 14 views 0 copies

brute-force nested-loops counting arrays

Python code

19 lines

Python 3.9+

def count_smaller_elements(arr):
    """
    Return a list where result[i] is the number of elements 
    to the right of arr[i] that are smaller than arr[i].
    """
    result = []
    for i in range(len(arr)):
        count = 0
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[i]:
                count += 1
        result.append(count)
    return result

if __name__ == "__main__":
    nums = [5, 2, 6, 1]
    counts = count_smaller_elements(nums)
    print(f"Input: {nums}")
    print(f"Smaller counts to the right: {counts}")

Output

stdout

Input: [5, 2, 6, 1]
Smaller counts to the right: [2, 1, 1, 0]

How it works

For each element at index i, the inner loop scans every element to its right (j > i) and increments a counter whenever arr[j] is strictly smaller than arr[i]. The per-element count is appended to the result list, giving exactly what the problem asks for. The algorithm runs in O(n²) time because each of the n elements triggers a scan of up to n−i−1 right-side items. The complexity is fine for small-to-medium inputs (up to a few thousand elements) but becomes slow for large arrays. Since only the standard library is needed and no imports are used, this snippet runs in any Python 3 environment without extra setup.

Common mistakes

Using <= instead of < , which incorrectly counts equal elements as smaller
Off-by-one errors by scanning j from i instead of i+1, counting the element itself
Returning a mutable list without copying when the input is modified later

Variations

Use a Fenwick tree (Binary Indexed Tree) to solve the problem in O(n log n) for large inputs
Coerce the input to a list before iterating if the caller passes a tuple or other iterable

Real-world use cases

Analyzing stock price trends to count how many later trading days closed below the current day's price.
Building recommendation features where each item's score is compared to subsequent items in a ranked list.
Computing inversion counts in a dataset to measure how sorted an array is for load-balancing heuristics.

Count Smaller Elements to the Right in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes