# O(rn) time, O(n) space; find mode, not just majority element

• One could use a radix sort to approach this problem.

Technically it's O(n) time.

It also takes O(n) space. In return, we can find any mode of the array, not only the mode that happens to occur in more than half of the cases.

``````class Solution {

private static final int RADIX = 2;

public int majorityElement(int[] nums) {
return mode(nums);
}

private int mode(int[] nums) {
int n = nums[0];
int maxN = n;
int count = 1;
int maxCount = count;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == n) {
count++;
if (count > maxCount) {
maxCount = count;
maxN = n;
}
} else {
count = 1;
n = nums[i];
}
}

return maxN;
}

int[] helper = new int[nums.length];
for (int i = 0; i < 32; i++) {
sort(nums, helper, i);
int[] t = nums;
nums = helper;
helper = t;
}
}

private void sort(int[] nums, int[] helper, int i) {
for (int num : nums) {
int digit = getDigit(num, i);
arr[digit]++;
}

for (int j = 1; j < RADIX; j++) {
arr[j] += arr[j - 1];
}

for (int k = nums.length - 1; k >= 0; k--) {
int digit = getDigit(nums[k], i);
helper[--arr[digit]] = nums[k];
}
}

private int getDigit(int num, int i) {
return (num >> i) & 1;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.