# Can any one explain this Java Optimal solution? (20170626, not Moore voting)

• This is the code I retrieved from the submission bar graph, currently it's the best-performing Java algorithm. I cleaned the code up a little and re-verified its speed, and it's still 1ms and beats 99.91%.
I am not very experienced with algorithms and I find this code hard to understand, can anyone shed some light? Also, this code looks like tail-recursion, how would one go about rewriting it to an iterative version?

``````public class Solution {
public int majorityElement(int[] nums) {
return maj(nums, nums.length);
}

public int maj(int[] nums, int n) {
if (n == 1 || n == 2) return nums[0];
int p = 0;
for (int i = 0 ; i < n; i = i + 2) {
if (i == n - 1 || nums[i] == nums[i + 1]) {
nums[p++] = nums[i];
}
}
return maj(nums,p);
}
}
``````

Thanks for any help offered.

====update 2017-06-29 16:50:36====
cleared the code a little bit more.

• ### Update

Somebody told me how to relate to this algorithm in general.

The motivation is to reduce the size of the problem by a factor of at least 2 after each iteration(from length `n` to length `p`). In the worst case, there would be `lgn` iterations. In the best case, there can be only 1 iteration: in the case of `[1,2,1,3,1,4,1]` for example.

The invariant is: the overall(original) majority element would stay as the majority element in each iteration's actual argument `nums[0]..nums[n-1]` (length `n`, which comes from the previous iteration's `p`).

The proof is a little verbose, which I thus would omit here. It's not very complicated though.

• This post is deleted!

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