Test case is way too weak...


  • 1
    E

    The following O(n) algorithm got passed in 1ms. Even though the problem statement requires us to use O(log n) solution, but the running time will mislead us if the test cases are not strong enough. For example, one might be thinking his algorithm is O(log n) because it got passed in 1ms, but the truth might be that it is of O(n). Take a solution posted here as an example.

    public int[] searchRange(int[] nums, int target) {
        int low=-1, high=-1;
        for(int i=0, L=nums.length; i<L; i++) {
            if(nums[i]==target) {
                if(low==-1) {low = i; high=i;}
                else high = i;
            }
            if(high!=-1 && nums[i]!=target) break;
        }
        return new int[]{low, high};
    }
    

Log in to reply
 

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