Right Smaller Than

Tags

Right Smaller Than

Category

Binary Search Trees

Difficulty

Hard

Problem Statement

Given an array of integers, return a new array where each element represents the number of integers to the right of that element that are strictly smaller than it. For example, given [8, 5, 11, -1, 3, 4, 2], the output would be [5, 4, 4, 0, 1, 1, 0].

Intuition

A brute-force approach checking all pairs is O(n^2). We can do better by processing the array from right to left and inserting each element into a self-balancing BST. At each insertion, we can count how many previously inserted elements (elements to the right in the original array) are smaller. By augmenting each BST node with the size of its left subtree, we can compute this count during insertion in O(h) time per element.

Approach

  1. Initialize an empty result array of the same length as the input.
  2. Iterate through the input array from right to left.
  3. For each element, insert it into an augmented BST where each node tracks leftSubtreeSize (count of nodes in its left subtree).
  4. During insertion, whenever we go right (the new value is greater than or equal to the current node), add leftSubtreeSize + 1 to a running count (these are all the nodes smaller than the new value at this point).
  5. When we go left, increment the current node's leftSubtreeSize.
  6. Store the running count as the result for this position.
  7. Return the result array.

Pseudocode

function rightSmallerThan(array):
    if array is empty:
        return []

    result = array of same length
    bstRoot = null

    for i from length - 1 down to 0:
        bstRoot = insertAndCount(bstRoot, array[i], 0, result, i)

    return result

function insertAndCount(node, value, numSmaller, result, index):
    if node is null:
        result[index] = numSmaller
        return new BSTNode(value)

    if value < node.value:
        node.leftSubtreeSize += 1
        node.left = insertAndCount(node.left, value, numSmaller, result, index)
    else:
        numSmaller += node.leftSubtreeSize
        if value > node.value:
            numSmaller += 1
        node.right = insertAndCount(node.right, value, numSmaller, result, index)

    return node

class BSTNode:
    value
    leftSubtreeSize = 0
    left = null
    right = null

Time & Space Complexity

  • Time: O(n log n) on average, where n is the length of the array. Each insertion into the BST takes O(h) time. For a balanced BST, h = O(log n). In the worst case (sorted input), the BST degenerates to O(n) height, making the total O(n^2). Using a self-balancing BST (AVL, Red-Black) guarantees O(n log n).
  • Space: O(n) for the BST and the result array.

Key Insights

  • Processing right to left ensures that when we insert an element, all elements to its right have already been inserted.
  • The leftSubtreeSize augmentation is the key optimization — it allows counting smaller elements without traversing the entire left subtree.
  • When going right during insertion, we add leftSubtreeSize + 1 because all nodes in the left subtree plus the current node are smaller.
  • When the value equals the current node's value, we do NOT add 1 for the current node (strictly smaller), but we DO add the leftSubtreeSize.
  • Alternative approaches include merge sort (counting inversions), Binary Indexed Trees (BIT/Fenwick trees), or segment trees.

Edge Cases

  • Empty array — return an empty array.
  • Array with one element — return [0].
  • Array sorted in ascending order — the BST degenerates to a linked list; every result is 0.
  • Array sorted in descending order — the BST also degenerates; results are [n-1, n-2, ..., 1, 0].
  • Array with duplicate values — handled correctly by the strict less-than comparison during insertion.
  • All elements are the same — every result is 0.

Linked mentions