Count Smaller By BST

Published: May 22, 2017

Let’s count smaller on the right in an array. More precisely, the problem is: given an array of integers, count integers smaller than the index i, also, located on the right of index i. So, the answer will be also an array of the integers. Apparently, the answer to the last element is 0.

While trying to solve this algorithm question, I saw a quite neat solution. As far as I googled, most solutions used a merge sort with an additional post processing. However, one of them used a binary search tree (BST) with no extra post processing. Also, the solution was easy to follow and undertandable. It was a so nice idea of using BST. It’s definitely worth adding memo here.

Problem description

Let’s start describing the problem in detail. For example, a given array of integers is [5, 2, 6, 1], the answer will be [2, 1, 1, 0].

  • 5: 2 and 1 are smaller, right side of elements
  • 2: 1 is a smaller, right side of element
  • 6: 1 is a smaller, right side of element

As always, there’s a bruto-force search whose performance is O(n^2). Starting from each index and counting smaller elements to the end will give the solution. The problem of the bruto-force is time out while the solution is testing by massive test cases.

How BST works

The binary search tree (BST) has a property, elements in left subtree are always smaller than the root. While building the BST, in another words, inserting a new node to the BST, it’s easy to count up how many elements are smaller than the new node.

One more neat idea of this solution is building BST from the end of the element. Since the answer to the last element is always zero, it is the good starting point.

The BSTs created from the array [5, 2, 6, 1] and [5, 2, 6, 4, 1, 3] will be formed one by one described below. Values of each node expresses: number (answer to this element, internal count state).


val (answer, count)

1 (0, 1)  1 (0, 1)      1 (0, 1)      1 (0, 1)
           \             \             \
            6 (1, 1)      6 (1, 2)      6 (1, 3)
                         /             /
                        2 (1, 1)      2 (1, 1)
                                       \
                                        5 (2, 1)



3 (0, 1)       3 (0, 2)        3 (0, 2)             3 (0, 2)                3 (0, 3)                3 (0, 3)
              /               / \                  / \                     / \                     / \
      (0, 1) 1        (0, 1) 1   4 (2, 1)   (0, 1) 1  4 (2, 1)     (0, 1) 1   4 (2, 1)     (0, 1) 1   4 (2, 1)
                                                       \                   \    \                  \   \
                                                        6 (3, 1)     (1, 1) 2    6 (3, 1)    (1, 1) 2   6 (3, 2)
                                                                                                       /
                                                                                               (4, 1) 5

As in the above, the root node keeps how many nodes are in the left subtree (including root) when a new node is added to the right subtree.

Java code

Below is the code to count while creating the BST.

The code returns the result:

[2, 1, 1, 0]
[4, 1, 3, 2, 0, 0]

Resources

Latest Posts

Vite + Vue + Bun on Rails

Vue.js is one of frontend frameworks gaining popularity among rapidly emerging JavaScript technologies. The combination of Vue.js and Rails is becoming more popular as well, however, Vue.js development on Rails is not so straightforward. The reason would be that Vue.js relies on Vite for a development environment such as HMR (Hot Module Replacement) and bundling.

Bun + React on Rails

In the frontend world, new technologies keep emerging rapidly these years. Still, React is a well-established and very popular frontend framework, Vue.js, Svelte, Astro and more frameworks are gaining popularity. Not just the frameworks, tools for a transpiler/bundler or sort are also under a rapid development. In JavaScript domain, esbuild, rollup, vite and some more are out.

Ruby on Rails Secrets Management

A web application needs various kinds of values, params and etc which should not be revealed to the public, say GitHub repo. For example, API keys, tokens, passwords, and endpoints, all those should be kept secret. Another important factor is that such secrets should be shared among the team members. Additionally, all those secrets should come along with the deployment.