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
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.04.2026 02:30:18 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
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.
Note that this is O(1) in space and O(n) time complexity.
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.
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
This assumes all the elements are distinct.
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?