Java solution with comments
Time complexity: O(log(n)) for query, O(n) in pre-processing (ctor).\nSpace complexity: O(n)\n\nI tried to figure out what other people did, then changed it a l
Time complexity: **O(log(n))** for query, O(n) in pre-processing (ctor).\nSpace complexity: O(n)\n\nI tried to figure out what other people did, then changed it a little so it\'ll make sense to me.\nI added **a lot** of comments, so if you\'re struggling (like I did) this might help you.\nPlease let me know if you have any comments / corrections.\n\n(I followed mainly this solution, so take a look: https://leetcode.com/problems/online-majority-element-in-subarray/discuss/617295/Java-O(logN)-for-each-query-with-bit-manipulation-and-binary-search )\n\n```\n    private Map<Integer, List<Integer>> valToInd;\n    private static final int numOfBits = 15;\n    private int[][] bitCount;\n    \n    public MajorityChecker(int[] arr) {\n        // create a map of: value --> all indexes with that value\n        valToInd = new HashMap<>();\n        // number of occurrences of each bit, cumulative\n        bitCount = new int[arr.length+1][numOfBits];\n        \n        for (int i=0; i<arr.length; i++) {\n            // add to valToInd\n            int val = arr[i];\n            List<Integer> indList = valToInd.get(val);\n            if (indList == null) {\n                indList = new ArrayList<>();\n                valToInd.put(val, indList);\n            }\n            indList.add(i);\n            \n            // add to bitCount\n            for (int j=0; j<numOfBits; j++) {\n                bitCount[i+1][j] = bitCount[i][j] + (val & 1);\n                val >>= 1; // remove last bit\n            }\n        }\n    }\n    \n    // query part will be in O(lon(n))\n    public int query(int left, int right, int threshold) {\n        // construct candidate value\n        int candidateVal = 0;\n        for (int i=numOfBits-1; i>=0; i--) {\n            int curBit = bitCount[right+1][i] - bitCount[left][i] >= threshold ? 1 : 0;\n            candidateVal = (candidateVal << 1) + curBit;\n        }\n        \n        // check if candidate is indeed majority in [left ... right]\n        List<Integer> indList = valToInd.get(candidateVal);\n        if (indList == null || indList.size() < threshold) {\n            return -1;\n        }\n        // look for the index of left and right in the list of indexes \n        // that contain cantidateVal\n        // binarySearch returns the index of the search key, if it is \n        // contained in the list; otherwise, (-(insertion point) - 1). The \n        // insertion point is defined as the point at which the key would be \n        // inserted into the list: the index of the first element greater than\n        // the key, or list.size() if all elements in the list are less than \n        // the specified key\n        int indOfLeft = Collections.binarySearch(indList, left);\n        if (indOfLeft < 0) {\n            // set it to the insertion point = index of the first element > left\n            indOfLeft = -indOfLeft - 1;\n        }\n        int indOfRight = Collections.binarySearch(indList, right);\n        if (indOfRight < 0) {\n            // set it to the insertion point - 1 = index of the last element < right\n            indOfRight = -indOfRight - 2;\n        }\n        // compare number of elements in [left ... right] with candidateVal to threshold\n        if (indOfRight - indOfLeft + 1 >= threshold) {\n            return candidateVal;\n        } else {\n            return -1;\n        }\n    }\n```\n
[]