Coordinate compression

Problem

Given a list of numbers, replace each element in the list with the number of other elements in the list smaller than the element.

This is especially useful when the range of values is wide, but the number of elements is relatively smaller , and only the order relation between elements is relevant.

Algorithm

The algorithm utilises sorting and binary search.

1. Generate a sorted version of the given list.
2. (Depending on the problem) remove duplicates from the list.
3. For each element in the given list, count the number of elements less than the element using binary search.

Below is a rust implementation of the algorithm:

use std::cmp::Ordering;
 
fn coord_compression(coords: &mut Vec<isize>) -> Vec<usize> {
    let mut sorted = coords.clone().to_vec();
    sorted.sort_unstable();
    sorted.dedup();
    coords
        .to_vec()
        .iter()
        .map(|seek| {
            sorted
                .binary_search_by(|probe| match probe.cmp(seek) {
                    Ordering::Equal => Ordering::Greater,
                    ord => ord,
                })
                .unwrap_err()
        })
        .collect::<Vec<usize>>()
}

This requires to first sort the list (time complexity $\mathcal{O}(n\log n)$), and then traverse the list to count the number of elements smaller than it (time complexity $\mathcal{O}(n\log n)$ because binary search is used), hence the overall time complexity is $\mathcal{O}(n\log n)$. Also, the algorithm generates a reference sorted list of legth at most equal to the length of the original list, and its space complexity is $\mathcal{O}(n)$.

References

• What to use instead of std::lower_bound and std::upper_bound in Rust? (March 20, 2023). Stack Overflow. https://stackoverflow.com/a/75790348