Java moore's voting O(n)
\nclass MajorityChecker {\n    int[] arr;\n    public MajorityChecker(int[] arr) {\n        this.arr = arr;\n    }\n    \n    public int query(int left, int rig
```\nclass MajorityChecker {\n    int[] arr;\n    public MajorityChecker(int[] arr) {\n        this.arr = arr;\n    }\n    \n    public int query(int left, int right, int threshold) {\n        int vote = -1; int cnt = 0;\n        for(int i = left; i <= right; i++) {\n            if(cnt == 0) {\n                vote = arr[i];\n            }\n            if(vote == arr[i]){\n                cnt++;\n            } else {\n                cnt--;\n            }\n        }\n        cnt = 0;\n        for(int i = left; i <= right; i++) {\n            if(arr[i] == vote) {\n                cnt++;\n            }\n        }\n       return cnt >= threshold ? vote : -1; \n    }\n}\n```
[]