# Java solution using partition, O(1) space

• ``````public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> result = new ArrayList<Integer>();
populate(nums, 0, nums.length - 1, result);
return result;
}

void populate(int []nums, int begin, int end, List<Integer> result) {
int freq = nums.length / 3;
if(result.size() == 2)
return;

int[] range = partition(nums, begin, end);
if(range == null)
return;
if(range[1] - range[0] + 1 > freq)
if(range[0] - begin > freq)
populate(nums, begin, range[0] - 1, result);
if(end - range[1] > freq)
populate(nums, range[1] + 1, end, result);
}

int[] partition(int[] arr, int begin, int end) {
if(begin > end)
return null;
int pivot = arr[end];
int i = begin;
for (int cur = begin; cur < end; cur++) {
if (arr[cur] < pivot) {
swap(arr, i, cur);
i++;
}
}
swap(arr, i, end);

int j = i;
for (int cur = i + 1; cur <= end; cur++) {
if (arr[cur] == arr[i]) {
swap(arr, j + 1, cur);
j++;
}
}

return new int[] { i, j };
}

void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
``````

Explanation:

1. Partition the array into 3 parts (instead of normal 2 parts that is used for QuickSort, etc). Part 1 has all the numbers less than pivot, part 2 has all the number equal to pivot and part 3 has all the numbers greater than pivot
2. If length of part2 is greater than n/3, we add that element.
3. Now, recursively call partition of part1 and part3 only if its size is greater than n/3

I think this solution can be generalized to get all the numbers with more than n/k occurrences for any given k.

This solution does pass all the test cases. However, I am not sure if it is indeed a linear time solution as well. Would appreciate comments on its running time.

• if applied to n/k, I don't think it works well. There are so many choices of pivot for n/k situation.

• My solution is similar and I think it's similar to QuickSort and QuickSelect. Worst time will be O(n^2) but average time should be indeed be considered to be like QuickSelect - (O(n).

• @bu.will.9 : pivot is only for partition. It can be randomly selected to be any of the element between begin to end. Here I am choosing the end element to be pivot. Despite any pivot chosen for partition, it does not affect the main logic

• I think you're right. Suppose the worst case, 1,2,3,... m,m,m... where m appears more than n/3 times. Then each level of recursion will cost n, n-1, n-2, ..., n-m-1 times to put every element to its proper partition, while there should be n-m-1 level of recursion. So I think it should be O(n^2) for worst case. The best case is O(n) definitely.
So maybe the time complexity will be between O(n) to O(n^2).

• Time complexity in O(x) is O(n^2) because we usually look at the worst case to nenote the O-Notation.

But Quicksort is technically also O(n^2) - in the real word though it is in average O(n log(n)) and similarly Quiclselect is in average O(n).

So I think (without proof) the algorithm shown in this thread is technicially O(n^2) but in average (amortized) it should be O(n).

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