Missing Test Case - 41. First Missing Positive

[kkandukuri]

Your LeetCode username

Category of the bug

• [ ] Question
• [x] Solution
• [x] Language
• [ ] Missing Test Cases

Description of the bug

Code you used for Submit/Run operation

// Two Sum
class Solution {
    public int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int missing = 1;

        for(int i=0;i<nums.length;i++){
            if(nums[i]==missing){
                missing++;
            }
        }
        return missing;
    }
};

Language used for code

JAVA

Expected behavior

Screenshots

Additional context

[LC-Sue]

Hi @kkandukuri , Thank you for reaching out. Could you please provide more details on your missing test case report. The test case and the code that you've used for submission.

[JLozensky]

Hi @LC-Sue, It appears as though @kkandukuri has intended to convey what I also came here to file a report about, which is that in this question the description states "You must implement an algorithm that runs in O(n) time and uses constant extra space." In Java (as well as Python which is what I was using) the sort() method's algorithm uses Timsort which has a time complexity of O( n log(n) ) which is not linear time. The fact that the code above works and indeed most all of the top accepted solutions I saw used sort() means that the expected behavior of the problem is not being met as non-linear solutions should be rejected.

[LC-Sue]

Hi @JLozensky, Thank you for the clarification, I have relayed this issue over to our team to investigate.

[LC-Sue]

Hi @kkandukuri @JLozensky Thank you for your time, our team has looked into the problem. We know that nlogn can pass and there is no way to fail this complexity. nlogn is fast and good but in the interview, you are asked to find an O(n) solution.