Rust | 82ms | 100% | random
Intuition\nRandomly pick an element in range and check if occurs threshold times.\n\n# Approach\nFor each number present in the array, store all the indices it 
# Intuition\nRandomly pick an element in range and check if occurs threshold times.\n\n# Approach\nFor each number present in the array, store all the indices it occurs in. In the input range pick a random index, binary search indices of number in that index to find how many indices fall within `[left, right]`, if the count exceed threshold return that number else check it few `times` and no such number exists return `-1`.\n\nFor number appearing more than `n/2` times in an array, the probability of finding that number at any random index is `>= 0.5`, so probability of not finding that number is $$1/2^{times}$$. If we make $$times=log(n)$$, the probability of not finding the majority element goes to $$1/n$$. For a given large `n`, this will be close to zero.\n\n# Complexity\n- Time complexity: $$O(n)$$ for building, $$O(logn)$$ per query.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nuse std::collections::HashMap;\nstruct MajorityChecker {\n    arr: Vec<i32>,\n    indices: HashMap<i32,Vec<usize>>,\n    times: usize,\n}\n\n\n/** \n * `&self` means the method takes an immutable reference.\n * If you need a mutable reference, change it to `&mut self` instead.\n */\nimpl MajorityChecker {\n\n    fn new(arr: Vec<i32>) -> Self {\n        let mut times = 0;\n        while (1 << times) < arr.len() {\n            times += 1;\n        }\n        let mut indices = HashMap::new();\n        for (i, &n) in arr.iter().enumerate() {\n            indices.entry(n).or_insert(Vec::new()).push(i);\n        }\n        Self {\n            arr, indices, times\n        }\n    }\n    \n    fn query(&self, left: i32, right: i32, threshold: i32) -> i32 {\n        let (left, right) = (left as usize, right as usize);\n        let diff = right - left + 1;\n        let threshold = threshold as usize;\n        for _ in 0..self.times {\n            let index = (rand::random::<usize>() % (diff) + left);\n            let num = self.arr[index];\n            let indices = self.indices.get(&num).unwrap();\n            let l = match indices.binary_search(&left) {\n                Ok(idx) => idx,\n                Err(idx) => idx,\n            };\n            let r = match indices.binary_search(&right) {\n                Ok(idx) => idx+1,\n                Err(idx) => idx,\n            };\n            if r - l >= threshold {\n                return num;\n            }\n        }\n        -1\n    }\n}\n\n/**\n * Your MajorityChecker object will be instantiated and called as such:\n * let obj = MajorityChecker::new(arr);\n * let ret_1: i32 = obj.query(left, right, threshold);\n */\n```
['Rust']