loverBoUy's blog

Mex of the array
By loverBoUy, history, 2 years ago, In English

Find the mex of the array in o(n) time and constant space complexity; mex = smallest missing element from the array please share your ideas on this tia

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
2 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Say n is the size of the array.

Loop through the array:

Let the element you are currently at be a.

If a > n, then just continue

otherwise, swap the values of the current element, and the a(th) element.

The answer will be the the (first index where the index(th) element of the list is not equal to index + 1) + 1.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Note that this is O(1) in space and O(n) time complexity.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      In input/output problems (like codeforces, the web where he is asking) you will have to create an array for that, so its O(n) space complexity.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I understand that but i was under the impression that storing the input itself doesnt count towards the space complexity because i have seen editorials where this has happened (i think). Also, mex in O(1) space (by your standards) seems like quite a tall order. I feel like its probably impossible

        → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    This assumes all the elements are distinct.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why do you say so? Notice that in this method, after the initial swaps are done, the value at position i will contain i + 1 if i + 1 exists in the array. Also, if the value at position i does not contain i + 1, then we can be confident that i+1 is not in the original array. So finding the first index where value at index does not equal index + 1 should work no?

      → Reply