# Randomized solution with O(1) space and linear time

• If there is a number which frequency exceeds n/3 then randomly selecting a number from the array, the probability that we take that number is 33.33 %. It is high enough probability to apply randomized solution. Thus, we take k(int my case k = 10) random numbers from the array, then check only those numbers which frequency exceeds some predefined threshold through traversing the original array. It can be considered as constant space because k is very small in compare to the size of array, and it doesn't depend on input size.

public class Solution {

``````public List<Integer> majorityElement(int[] nums) {
List<Integer> list = new ArrayList<>();

if(nums.length == 0) return list;
int n = nums.length;
int rand[] = new int[10];
for(int i = 0;i<10;i++){
rand[i] = nums[(int)(Math.random()*n)];
}

List<Integer> check = new ArrayList<>();
for(int i = 0;i<10;i++){
int count = 1;
for(int j = i+1;j<10;j++) {
if(rand[i] == rand[j]) count++;
}
}

for(int i = 0;i<check.size();i++){
int count = 0;
for(int j = 0;j<n;j++){
if(nums[j] == check.get(i)) count++;
}
if(count > n/3) {
if(!list.contains(check.get(i)))