7ms Java solution using Binary Indexed Tree

  • 2

    Before move on to try the solution, I suggest you read about binary indexed tree.

    public class Solution {
        In this solution, we use a binary indexed tree (BIT)
        Our assumption is that all elements in nums are positive
        static int MAX = 11000; //we set max value that can be store in the tree
        int[] tree = new int[MAX];
        public List<Integer> countSmaller(int[] nums) {
            Integer[] result = new Integer[nums.length];
            //make all elements in the array posive while maintaining their order
            for(int i=nums.length-1; i>=0; i--){
                result[i] = get(nums[i]);
                add(nums[i]+1, 1);
            return Arrays.asList(result);
        public void makePositive(int[] nums){
            int min = MAX;
            for(int i=0; i<nums.length; i++)    
                min = Math.min(min, nums[i]);
            if(min < 0){
                min = -min+1;
                for(int i=0; i<nums.length; i++)
                    nums[i] += min;
        public void add(int idx, int val){
                tree[idx] += val;
                idx += (idx & (-idx));
        public int get(int idx){
            int result = 0;
                result += tree[idx];
                idx &= (idx-1);
            return result;

  • 0

    could you please explain the idea of your solution?

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.