Блог пользователя loverBoUy

Mex of the array
Автор loverBoUy, история, 20 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
20 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      20 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        20 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        → Ответить
  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    This assumes all the elements are distinct.

    → Ответить
    • »
      »
      »
      20 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      → Ответить