Sponsored
Sponsored
The Binary Indexed Tree (BIT) allows us to efficiently update elements and calculate cumulative frequencies in an iterative manner. In this approach, we traverse the input array from right to left, update the BIT with the index of the current number, and use the BIT to find the count of numbers which are smaller.
Time Complexity: O(n log n), where n is the number of elements in nums. Updating the BIT and querying both take O(log n) time.
Space Complexity: O(n) for the BIT and result array.
1import java.util.*;
2
3class Solution {
4 class FenwickTree {
5 private int[] tree;
6 public FenwickTree(int size) {
7 tree = new int[size + 1];
8 }
9 public void update(int index, int value) {
10 while (index < tree.length) {
11 tree[index] += value;
12 index += index & -index;
13 }
14 }
15 public int query(int index) {
16 int sum = 0;
17 while (index > 0) {
18 sum += tree[index];
19 index -= index & -index;
20 }
21 return sum;
22 }
23 }
24 public List<Integer> countSmaller(int[] nums) {
25 int offset = 10000;
26 int size = 20001;
27 FenwickTree bit = new FenwickTree(size);
28 Integer[] result = new Integer[nums.length];
29 for (int i = nums.length - 1; i >= 0; i--) {
30 result[i] = bit.query(nums[i] + offset);
31 bit.update(nums[i] + offset + 1, 1);
32 }
33 return Arrays.asList(result);
34 }
35 public static void main(String[] args) {
36 Solution solution = new Solution();
37 int[] nums = {5, 2, 6, 1};
38 List<Integer> result = solution.countSmaller(nums);
39 System.out.println(result);
40 }
41}This Java solution uses a nested FenwickTree class to manage the BIT operations. We utilize an offset to map negative numbers into a positive index space. For each number, we query the BIT to get the number of smaller elements and then update the BIT with the current number. The result is stored in an Integer list that respects the problem's constraints.
This approach takes advantage of the divide and conquer strategy combined with a binary search tree (BST). As we process each number from right to left, we insert them into the BST, which allows us to compute the count of elements smaller than the current number efficiently.
Time Complexity: O(n log n) on average, assuming balanced inserts into the BST.
Space Complexity: O(n) for storing BST nodes and result array.
The JavaScript solution employs a constructor-based system for creating node instances to facilitates insertions and queries relative to node positioning. Calculating preSum in tandem with node creation encapsulates the overall method necessary for counting smaller elements. The recursive formation of tree branches holds up under problem constraints.