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


  • 1
    T

    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 1s 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.


  • 0

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


  • 1
    T

    @1337c0d3r thanks, better later than never :)


Log in to reply
 

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