https://leetcode.com/problems/online-majority-element-in-subarray/

online-majority-element-in-subarra.java

class MajorityChecker {
    class SegmentTreeNode {
        int major;
        int freq;
        int start;
        int end;
        SegmentTreeNode left;
        SegmentTreeNode right;
        
        public SegmentTreeNode (int start, int end) {
            this.major = 0;
            this.freq = 0;
            this.start = start;
            this.end = end;
        }
        
    }
    
    class SegmentTree {
        Map<Integer, List<Integer>> indexes;
        SegmentTreeNode root;
        
        
        public SegmentTree(int[] arr) {
            this.indexes = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
                if (!indexes.containsKey(arr[i])) {
                    indexes.put(arr[i], new ArrayList<>());
                }
            }
            this.root = buildTree(arr, 0, arr.length - 1);
        }
        
        public SegmentTreeNode buildTree(int[] arr, int start, int end) {
            
            if (start == end) {
                SegmentTreeNode node = new SegmentTreeNode(start, end);
                node.major = arr[start];
                node.freq = 1;
                this.indexes.get(node.major).add(start);
                return node;
            } else {
                int mid = start + (end - start) / 2;
                SegmentTreeNode leftNode = buildTree(arr, start, mid);
                SegmentTreeNode rightNode = buildTree(arr, mid + 1, end);
                return merge(leftNode, rightNode);
            }
           
        }
        
        public SegmentTreeNode merge(SegmentTreeNode leftNode, SegmentTreeNode rightNode) {
            SegmentTreeNode node = new SegmentTreeNode(leftNode.start, rightNode.end);
            node.left = leftNode;
            node.right = rightNode;
            if (leftNode.major == rightNode.major) {
                node.major = leftNode.major;
                node.freq = leftNode.freq + rightNode.freq;
                return node;
            } 
            if (leftNode.freq > rightNode.freq) {
                node.major = leftNode.major;
                node.freq = leftNode.freq - rightNode.freq;
                return node;
            } else {
                node.major = rightNode.major;
                node.freq = rightNode.freq - leftNode.freq;
                
                return node;
            }
        }
        
        public SegmentTreeNode queryRange(SegmentTreeNode node, int start, int end) {
            if (node.start == start && node.end == end) {
                return node;
            }
            int mid = node.start + (node.end - node.start) / 2;
            if (start > mid) {
                return queryRange(node.right, start, end);
            }
            if (end <= mid) {
                return queryRange(node.left, start, end);
            }
            
            SegmentTreeNode fromLeft = queryRange(node.left, start, mid);
            SegmentTreeNode fromRight = queryRange(node.right, mid + 1, end);
            return merge(fromLeft, fromRight);
        }
        
        public int query(int left, int right, int threshold) {
            SegmentTreeNode candidate = this.queryRange(this.root, left, right);
            if (candidate.freq == 0) {
                return -1;
            }
            
            int count = getOccurrence(left, right, candidate.major);
            if (count >= threshold) {
                return candidate.major;
            }
            return -1;
        }
        
        private int getOccurrence(int left, int right, int a) {
            List<Integer> list = this.indexes.get(a);
            
            int i = Collections.binarySearch(list, left);
            if (i < 0) i = ~i;
            if (i == list.size()) return 0;
            int j = Collections.binarySearch(list, right);
            if (j < 0) j = ~j - 1;
            return j - i + 1;
        }

        
    }
    
    SegmentTree segTree;
    public MajorityChecker(int[] arr) {
         this.segTree = new SegmentTree(arr);
    }
    
    public int query(int left, int right, int threshold) {
        return this.segTree.query(left, right, threshold);
    }
}

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * MajorityChecker obj = new MajorityChecker(arr);
 * int param_1 = obj.query(left,right,threshold);
 */