Binary Search + Segment Tree
Easy Part\nWe first create a map of element to sorted indices of that element.\nThen using this, we can calculate no of occurences of any element (say val) in a
**Easy Part**\nWe first create a map of element to sorted indices of that element.\nThen using this, we can calculate no of occurences of any element (say val) in a range [left, right] in O(logn) TC using Binary Search (Find left & right against indices of val using Binary Search).\nSo basically we are ready with a method isMajority = count > (right - left + 1) / 2 & a method "count" which will give us count from any [left, right] for a value val.\nThis has been implemented in the "isMajority" method in the code. Now we will use this later.\n\n**Hard Part**\nWell we plan to use a Segment Tree to store Majority Elements, but Segment Tree Property must be valid so we can query any range [left, right]. A lot of people give up on the problem here since the property is not exactly satisfied for querying from the segment tree. And it won\'t be. But we are not going to use the Segment Tree to query. We will only use it to divide our range into logN ranges that we will further query.\n\nSo, first we do a proof of a simple property.\nFor an array of say N elements with a Maj Element x and rest assuming worst case, say all elements are y. Now since x is Maj Element, it must be present > N / 2 times. So say that its present N / 2 + r times (r > 0).\nNow if we divide this into just 2 Groups, say we put ANY b elements in first group and rest N - b in second group. This is the state of the both ranges:\nR1: a * x, (b - a) * y\nR2: (N / 2 + r - a) * x, (N / 2 - b - r + a) * y\nNow if either x is maj element or y of each range.\nNow property = x should be majority element in EXACTLY 1 of the subsets. \nNow proving by contradiction. Assume x is majority element of both. Then solve the inequalities and we get a contradiction.\nSo, now by Induction, we can break any Range into any number of Ranges of any size. And still, the majority element will be maj element in atleast 1 of the subsets. But we can\'t find which one is the majority element. Well, We have our "isMajority" method :)\n\nWe basically build a segment tree now. Each node is a range. And at each Node, we are storing the maj element & its count. While building, suppose we have maj element = m & its count = mc for both left & right children. We can get maj element for parent by first get total count of m in both left & right ranges/children (using our "count" method we build in the start), say lc & rc. Then if lc > len(range of parent) / 2 or rc > same, this is the maj element of our parent node. We build the entire tree like this from bottom-up. This is the "fillMaj" method in code.\n\nNow comes the query part, max no of ranges that are touched to query any [left, right] in a segment tree is 4 * logN. So we can imagine that we can break any range into these number of ranges. Then, we can safely query all of these ranges and check if their majority element is the ans by calling our "isMajority" method. If it is, we simply return that node\'s value. Otherwise, we recur for left & right. Please note that we only check isMajority if the range has total overlap, otherwise we recur. This is the "findMaj" method in code.\n\nOverall TC = NlogN to build Segment Tree + N to build EleToIndices Map + logN number of ranges * logN for count method for Query = O(logN * logN).\nThis is the best TC for this solution.\n\n```\nimport java.util.ArrayList;\nimport java.util.HashMap;\nimport java.util.List;\nimport java.util.Map;\n\nclass MajorityChecker {\n\n    private int log2(int x) {\n        return (int) (Math.log(x) / Math.log(2) + 1e-10);\n    }\n\n    // RETURN VAL IN L >= VAL WITH MIN INDEX\n    private int gte(List<Integer> l, int s, int e, int val) {\n        if (s > e) {\n            return -1;\n        }\n\n        int mid = (s + e) / 2;\n        if (l.get(mid) >= val) {\n            int x = gte(l, s, mid - 1, val);\n            if (x != -1) {\n                return x;\n            }\n            return mid;\n        }\n        return gte(l, mid + 1, e, val);\n    }\n\n    // RETURN VAL IN L <= VAL WITH MAX INDEX\n    private int lte(List<Integer> l, int s, int e, int val) {\n        if (s > e) {\n            return -1;\n        }\n\n        int mid = (s + e) / 2;\n        if (l.get(mid) <= val) {\n            int x = lte(l, mid + 1, e, val);\n            if (x != -1) {\n                return x;\n            }\n            return mid;\n        }\n        return lte(l, s, mid - 1, val);\n    }\n\n    // RETURN NO OF TIMES VAL EXISTS BETWEEN L & R\n    private int count(int l, int r, int val) {\n        if (!eleToIndices.containsKey(val)) {\n            return 0;\n        }\n\n        List<Integer> indices = eleToIndices.get(val);\n        int start = gte(indices, 0, indices.size() - 1, l);\n        int end = lte(indices, 0, indices.size() - 1, r);\n        return (start == -1 || end == -1) ? 0 : end - start + 1;\n    }\n\n    // RETURN IF VAL OCCURS >= THRESHOLD TIMES BETWEEN L & R\n    private boolean isMajority(int l, int r, int val, int threshold) {\n        int count = count(l, r, val);\n        return count >= threshold;\n    }\n\n    // STREE NODE\n    static class Node {\n        private int s;\n        private int e;\n        private int m;\n        private int mc;\n\n        Node(int s, int e) {\n            this.s = s;\n            this.e = e;\n            this.m = -1;\n            this.mc = 0;\n        }\n\n        @Override\n        public String toString() {\n            return "( s: " + s + ", e: " + e + ", m: " + m + ", mc: " + mc + " )";\n        }\n    }\n\n    // FILL STREE WITH MAJ ELEMENTS\n    private Node fillMaj(int i, int s, int e) {\n        if (i >= sTree.length) {\n            return null;\n        }\n\n        // SINGLE NODE = MAJ OF ITSELF\n        if (s == e) {\n            sTree[i] = new Node(s, e);\n            sTree[i].m = A[s];\n            sTree[i].mc = 1;\n            return sTree[i];\n        }\n\n        // CREATE NEW NODE\n        int len = e - s + 1;\n        int mid = (s + e) / 2;\n        sTree[i] = new Node(s, e);\n\n        Node left = fillMaj(2 * i + 1, s, mid);\n        Node right = fillMaj(2 * i + 2, mid + 1, e);\n\n        // CHECK LEFT IS MAJ\n        if (left != null) {\n            int lcr = count(mid + 1, e, left.m);\n            int lc = lcr + left.mc;\n            if (lc > len / 2) {\n                sTree[i].m = left.m;\n                sTree[i].mc = lc;\n            }\n        }\n\n        // CHECK RIGHT IS MAJ\n        if (sTree[i].m == -1 && right != null) {\n            int rcl = count(s, mid, right.m);\n            int rc = rcl + right.mc;\n            if (rc > len / 2) {\n                sTree[i].m = right.m;\n                sTree[i].mc = rc;\n            }\n        }\n        return sTree[i];\n    }\n\n    // FIND MAJ ELEMENT BETWEEN L & R WITH COUNT >= THRESHOLD\n    private Node findMaj(int i, int s, int e, int l, int r, int rl, int rr, int threshold) {\n        if (i >= sTree.length) {\n            return null;\n        }\n\n        Node node = sTree[i];\n\n        // COMPLETE OVERLAP, CHECK MAJ\n        if (node.s == l && node.e == r) {\n            if (node.m != -1 && isMajority(rl, rr, node.m, threshold)) {\n                return node;\n            }\n            return null;\n        }\n\n        int mid = (node.s + node.e) / 2;\n        if (l > mid && r > mid) {\n\n            // ONLY OVERLAP WITH RIGHT\n            return findMaj(2 * i + 2, mid + 1, e, l, r, rl, rr, threshold);\n        } else if (l <= mid && r <= mid) {\n\n            // ONLY OVERLAP WITH LEFT\n            return findMaj(2 * i + 1, s, mid, l, r, rl, rr, threshold);\n        } else {\n\n            // PARTIAL OVERLAP WITH BOTH\n            Node left = findMaj(2 * i + 1, s, mid, l, mid, rl, rr, threshold);\n            Node right = findMaj(2 * i + 2, mid + 1, e, mid + 1, r, rl, rr, threshold);\n            if (left != null) {\n                return left;\n            }\n            return right;\n        }\n    }\n\n    private int N;\n    private int[] A;\n    private Map<Integer, List<Integer>> eleToIndices;\n    private Node[] sTree;\n\n    // INIT\n    public MajorityChecker(int[] A) {\n\n        this.A = A;\n        this.N = A.length;\n\n        // BUILD ELE TO INDICES\n        eleToIndices = new HashMap<>();\n        for (int i = 0; i < N; i++) {\n            if (!eleToIndices.containsKey(A[i])) {\n                eleToIndices.put(A[i], new ArrayList<>());\n            }\n            eleToIndices.get(A[i]).add(i);\n        }\n\n        // BUILD STREE\n        int l = log2(N);\n        int x = Math.pow(2, l) == N ? N : (int) Math.pow(2, l + 1);\n        this.sTree = new Node[2 * x - 1];\n        fillMaj(0, 0, N - 1);\n    }\n\n    // MAIN QUERY FUNCTION\n    public int query(int left, int right, int threshold) {\n        Node maj = findMaj(0, 0, N - 1, left, right, left, right, threshold);\n        return (maj != null && maj.m != -1) ? maj.m : -1;\n    }\n}\n```
[]