Подсчитайте элементы в массиве, имеющие строго меньший и строго больший элемент

Учитывая массив arr[] , задача состоит в том, чтобы найти количество элементов в данном массиве, так что существует элемент строго меньшего и элемента строго большего, чем он.

Примеры:

Input: arr [] = {11, 7, 2, 15}
Output: 2
Explanation: For arr[1] = 7, arr[0] is strictly greater than it and arr[2] is strictly smaller than it. Similarly for arr[1], arr[3] is strictly greater than it and arr[2] is strictly smaller than it. Hence, the required count is 2.

Input: arr[] = {1, 1, 1, 3}
Output: 0

Наивный подход: Данную проблему можно решить, перебирая каждый элемент массива arr[] и проверяя, существует ли строго больший и строго меньший элемент, чем он.

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

Эффективный подход: описанный выше подход можно оптимизировать, найдя минимальный и максимальный элемент данного массива, пройдя по данному массиву arr[] и проверив, строго ли arr[i] больше минимума и строго меньше максимума. Сохраните количество таких индексов в переменной, которая является требуемым ответом.

Ниже приведена реализация вышеуказанного подхода:

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