Why most people solve this problem under the assumption A[i] <= n

  • 11

    I find that most solutions online assume that array A itself as a hashtable.

    My question is how can you guarantee all element in A is not greater than n,which is the array's size.


    for example

    A = { 7, 8 , 9, 11,12 }, n = 5

    all A[i] is greater than n

  • 2

    In your case, the first missing positive integer is 1. It is ok to use array as hash table in this problem. I think it is an elegant solution to solve it.

  • 0

    Since the question does not explicitly state and the examples seem like a sorted rotated array. If this is the case, the missing value is as good as find the rotation point and then checking the leftmost and rightmost indexes to judge the missing value.

    Wanted to clarify the same?

  • 0

    No, there is no guarantee that array is sorted.

  • 22

    We only have n numbers, and the answer must be in [1, n + 1].

    1. If n numbers are 1, 2, 3, ..., n, then the answer is n + 1.
    2. use a number x (x <= 0 || x > n) to replace a number in 1, 2, 3, ..., n. There must be a number less than n+1.

  • 2

    It doesn't matter whether A[i] is greater than n or not. In you example, the answer is 1, which is between 1 and n + 1(include).

  • -1

    Agreed your reasonable argument.

    A = { 7, 8 , 9, 11,12 }, n = 5

    Your missing integer is 10. However, your problem can be converted into the problem of [1, ..., n+1] by subtracting 6 = (7-1). 7 is minimum number in your case. Now you should be able to find the missing positive 4, add back 6 to get 10. The overall complexity is still O(N), since finding the minimum is O(N).

  • 0

    I agree with your argument and i think this problem needs better description.

  • 0

    In this case, the first missing positive integer is 1.

  • 1

    I absolutely know the missing positive number is 1. I just want to provide an another angle to see the problem. You can treat it an extensional discuss.

    Given A = { 7, 8 , 9, 11,12 }, n = 5, people would like to see the missing number is 10 that is more reasonable actually. Who will care the missing number is 1 in this case, realistically?

    ngcl, please read through my whole comment and cast your vote.

  • 0

    @enze98 I have the same thought.

Log in to reply

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