# Add test case to prevent clever O(n^2) from passing

• Trivial `O(n^2)` solution:

``````for (int i = 0; i < nums.length; ++i) {
int count = 0;
for (int j = i; j < nums.length; ++j) {
if (nums[i] == nums[j]) {
count++;
}
if (count > nums.length / 2) return nums[i];
}
}
``````

This is filtered by a test case that times out: `[24999*1, 25001*2]`, it runs for more than 1 second.

A simple modification to this algorithm which skips the continous `1`s passes all test cases:

``````for (int i = 0; i < nums.length; ++i) {
int count = 0;
int continuous = 0;
boolean mismatch = false;
for (int j = i; j < nums.length; ++j) {
if (nums[i] == nums[j]) {
if (!mismatch) continuous++;
count++;
} else {
mismatch = true;
}
if (count > nums.length / 2) return nums[i];
}
i += continuous; // skip elements that will not be majority for sure
--i; // because the next loop starts by incrementing
}
``````

I propose to add a new test case which looks like this:

``````final int n = 50000; // counts will be {1=12500, 2=12499, 3=25001}
int[] nums = new int[n];
for (int i = 0; i < n / 2; ++i) {
nums[i] = i % 2 + 1;
}
for (int i = n / 2 - 1; i < n; ++i) { // - 1 to have 1 more 3s than 1s and 2s
nums[i] = 3;
}
``````

This will make the modified algorithm choke with ~900 ms runtime.

• @TWiStErRob Thanks, this is a great test. I have added your test case.

• @1337c0d3r thanks, better later than never :)

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