Return to Revisions

That's a nice simple solution, with two problems:

1. It will give incorrect result when A contains all the values in the ranges [1..1000000] or [1..999999], returning undefined instead of 1000001 and 1000000, respectively.
2. It doesn't meet the time complexity requirement, being \$O(n^2)\$ instead of \$O(n)\$.

The first problem is easy to fix by adjusting the end condition of the loop.

The second problem is trickier, and the interesting part of the exercise. Consider this algorithm:

• Loop over the elements of A from the start, and for each value A[i], if A[i] - 1 is a valid index in the array, then recursively swap A[i] and A[A[i] - 1] until A[i] is in its correct place (value equal to i + 1), or A[i] and A[A[i] - 1] are equal.
  • This should order the values to their right places such that A[i] == i + 1, when possible
• Loop over the elements again to find an index where A[i] != i + 1, if exists then the missing value is i + 1
• If the end of the loop is reached without returning a value, then the missing value is A.length + 1.