Segment tree with array compression. Clean code


  • 0
    A

    To solve this problem I used Segment Tree which will store sum of child values.

    1. we get sum from range [0, nums[i]-1];
    2. we make +1 to nums[i];
      This solution works only for positive and small numbers. We need somehow compress the nums array that segment tree will use memory optimally. We can sort nums array then give unique index for each unique number.
    public class Solution {
        public List<Integer> countSmaller(int[] nums) {
            int n = nums.length;
            ArrayList<Integer> smalls = new ArrayList<Integer>();
            if (n==0) return smalls;
            
            HashMap<Integer, Integer> map = getIndexMap(nums);
            
            SegmentTree tree = new SegmentTree(new int[map.size()],0, map.size()-1);
            
            for (int i=n-1; i>=0; i--) {
                int val = tree.getRangeValue(0,map.get(nums[i])-1);
                tree.update(map.get(nums[i]),1);
                smalls.add(val);
            }
            Collections.reverse(smalls);
            return smalls;
        }
        
        private HashMap<Integer, Integer> getIndexMap(int nums[]) {
            int temp[] = nums.clone();
            HashMap<Integer, Integer> map = new HashMap<>();
            Arrays.sort(temp);
            int cnt = 0;
            for (int val : temp) {
                if (!map.containsKey(val)) {
                    map.put(val, cnt);
                    cnt++;
                }
            }
            return map;
        }
        
        public class SegmentTree {
    
            private SegmentTree leftNode;
            private SegmentTree rightNode;
            private int value;
            private int leftBound, rightBound;
        
            public SegmentTree(int arr[], int leftBound, int rightBound) {
                this.leftBound = leftBound;
                this.rightBound = rightBound;
                if (leftBound == rightBound) {
                    value = arr[leftBound];
                    return;
                }
                int mid = (leftBound + rightBound) / 2;
                leftNode = new SegmentTree(arr, leftBound, mid);
                rightNode = new SegmentTree(arr, mid + 1, rightBound);
                value = rangeValue();
            }
        
            public int getRangeValue(int l, int r) {
                if (l>r) return 0;
                if (rightBound < l || leftBound > r) return 0;
                if (l <= leftBound && rightBound <= r) return value;
                return leftNode.getRangeValue(l, r) + rightNode.getRangeValue(l, r);
            }
        
            public void update(int pos, int val) {
                if (leftBound == rightBound) {
                    value += val;
                    return;
                }
        
                int mid = (leftBound + rightBound) / 2;
        
                if (pos <= mid) leftNode.update(pos, val);
                else rightNode.update(pos, val);
        
                value = rangeValue();
            }
        
            private int getValue() {
                return value;
            }
        
            public int rangeValue() {
                return leftNode.getValue() + rightNode.getValue();
            }
        }
    }
    

Log in to reply
 

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