You are given an integer array nums and you have to return a new array counts. The array counts has the property where counts[i] is the number of smaller elements to the right of nums[i].

Examples

Example 1:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller elements.

Example 2:

Input: nums = [-1]
Output: [0]

Example 3:

Input: nums = [-1,-1]
Output: [0,0]

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Thinking Process

  1. Coordinate Compression: Essential for handling negative numbers and large ranges
  • The search space must shrink monotonically each step.
  • Decide which half still satisfies the predicate, discard the other.
  • Use mid = left + (right - left) / 2 to avoid overflow.
Binary search: shrink [lo … hi] lo mid hi discard half each step → O(log n)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting (this problem) O(n) O(n) Frequency, two-sum variants

Solution

Solution: Fenwick Tree (Binary Indexed Tree) with Coordinate Compression

from bisect import bisect_left

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def lowbit(self, x):
        return x & -x

    # add delta at index x (1-indexed)
    def update(self, x, delta):
        while x <= self.n:
            self.bit[x] += delta
            x += self.lowbit(x)

    # prefix sum 1..x
    def query(self, x):
        s = 0
        while x > 0:
            s += self.bit[x]
            x -= self.lowbit(x)
        return s


class Solution:
    def countSmaller(self, nums):
        n = len(nums)
        res = [0] * n

        # coordinate compression
        sorted_vals = sorted(set(nums))

        fw = Fenwick(len(sorted_vals))

        # process from right to left
        for i in range(n - 1, -1, -1):
            x = bisect_left(sorted_vals, nums[i]) + 1

            res[i] = fw.query(x - 1)
            fw.update(x, 1)

        return res

Solution Explanation

Approach: Hash map counting (this problem)

Key idea: 1. Coordinate Compression: Essential for handling negative numbers and large ranges

How the code works:

  1. Coordinate Compression: Essential for handling negative numbers and large ranges
    • The search space must shrink monotonically each step.
    • Decide which half still satisfies the predicate, discard the other.
    • Use mid = left + (right - left) / 2 to avoid overflow.

Walkthrough — input nums = [5,2,6,1], expected output [2,1,1,0]:

To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller elements.

Algorithm Explanation:

Fenwick Class:

  1. Constructor: Initialize BIT with size n (1-indexed array)
  2. lowbit(): Extract lowest set bit using x & -x
  3. update(x, delta): Add delta to position x and all ancestors
  4. query(x): Get prefix sum from 1 to x

Solution Class:

  1. Coordinate Compression (Lines 20-23):
    • Create sorted, unique array of all values
    • Maps original values to compressed indices [1, k]
    • Handles negative numbers and large ranges
  2. Right-to-Left Processing (Lines 27-33):
    • Process from sz-1 down to 0
    • For each element:
      • Find compressed index x using binary search
      • Query count of elements < current: fw.query(x - 1)
      • Update tree: mark current element as seen

How It Works:

  • Coordinate Compression: [5, 2, 6, 1] → [1, 2, 5, 6] → indices [1, 2, 3, 4]
  • Right-to-Left: Ensures we only count elements to the right
  • Query Before Update: Query counts elements already processed (to the right)
  • Update: Marks current element for future queries

Example Walkthrough:

Input: nums = [5, 2, 6, 1]

Step 1: Coordinate Compression
  sorted = [1, 2, 5, 6]
  Mapping: 1→1, 2→2, 5→3, 6→4

Step 2: Process from right to left
  i=3: nums[3] = 1, x = 1
    query(0) = 0 → res[3] = 0
    update(1, 1) → BIT[1] = 1
    
  i=2: nums[2] = 6, x = 4
    query(3) = BIT[3] + BIT[2] = 0 + 1 = 1 → res[2] = 1
    update(4, 1) → BIT[4] = 1
    
  i=1: nums[1] = 2, x = 2
    query(1) = BIT[1] = 1 → res[1] = 1
    update(2, 1) → BIT[2] = 2
    
  i=0: nums[0] = 5, x = 3
    query(2) = BIT[2] = 2 → res[0] = 2
    update(3, 1) → BIT[3] = 1

Result: [2, 1, 1, 0] ✓

Complexity Analysis:

  • Time Complexity: O(n log n)
    • Coordinate compression: O(n log n) for sorting
    • Binary search for each element: O(n log n)
    • Fenwick Tree operations: O(n log n) for n updates + n queries
    • Overall: O(n log n)
  • Space Complexity: O(n)
    • Result array: O(n)
    • Sorted array: O(n)
    • Fenwick Tree: O(n)
    • Overall: O(n)

      Common Mistakes

  1. Single element: nums = [5] → return [0]
  2. All same: nums = [1, 1, 1] → return [0, 0, 0]
  3. Negative numbers: nums = [-1, -2] → coordinate compression handles it
  4. Descending order: nums = [5, 4, 3, 2, 1] → all counts are 0

  5. Ascending order: nums = [1, 2, 3, 4, 5] → counts increase

  6. Left-to-right processing: Would count elements to the left instead
  7. Forgetting coordinate compression: BIT requires positive indices
  8. Wrong query index: Using query(x) instead of query(x-1) for strictly smaller
  9. Update before query: Should query first, then update
  10. Not handling duplicates: Coordinate compression must preserve uniqueness

Key Takeaways

  1. Coordinate Compression: Essential for handling negative numbers and large ranges
  2. Right-to-Left Processing: Ensures we only count elements to the right
  3. Fenwick Tree Efficiency: O(log n) per operation, better than naive O(n)
  4. Query Before Update: Query counts already-seen elements, then mark current
  5. Binary Search: Use lower_bound for coordinate compression lookup

References

Template Reference