4ms C++ solution, does MAX_INTEGER * n consider as O(n) ?

  • -1

    Does this consider as an O(n) solution? It will at most run MAX_INTEGER * nums.size() times, and usually it does not since we stop when we find that number. But if

    1. all numbers in the array are positive numbers (say n numbers)

    2. the missing positive integer is max(all numbers in the array) + 1 (denote by K)

    then the time complexity is K * n, but it can also be wrote as sum_{1}^{n+1}, there is a n square in it...

    class Solution {
        int firstMissingPositive(vector<int>& nums) {
            int missing = 1;
            while(true) {
                bool find = false;
                for(int i = 0; i < nums.size(); i++) {
                    if (nums[i] - missing == 0) { // find that positive integer
                        missing ++;
                        find = true;
                if (!find) return missing;

  • 0

    This is O(n^2).

    Consider the input n, n-1, n-2, ..., 1

  • 0

    Yes I see, thanks.

Log in to reply

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