Найдите наибольшее положительное целое число x, отсутствующее в несортированном массиве, такое, что min(arr[]) < x < max(arr[])

Дан массив arr[] , содержащий целые числа. Задача состоит в том, чтобы найти наибольшее положительное целое число x , отсутствующее в массиве, такое, что min(arr[]) < x < max(arr[]) .

Примеры

Input: arr[] = {2, 3, 7, 6, 8}
Output: 5
Explanation: 5 is the largest positive integer missing from arr[] and 2 < 5 < 8.

Input: arr[] = { 2, 3, -7, 1, 4 }
Output: -1

Наивный подход: отсортируйте массив по убыванию и верните первое отсутствующее положительное число. Если ничего не пропущено, верните -1 .

Временная сложность: O(N logN)
Временная сложность: O(1)

Эффективный подход: эту проблему можно решить с помощью хеширования. Создайте Hashmap всех положительных элементов в данном массиве. После построения Hashmap просмотрите HashMap с обратной стороны и верните первое отсутствующее положительное число. Если ничего не пропущено, верните -1 .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O(N)