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

Дан массив arr[] , состоящий из N различных целых чисел, задача состоит в том, чтобы вывести для каждого элемента массива все старшие элементы слева от него.

Примеры:

Input: arr[] = {5, 3, 9, 0, 16, 12}
Output:
5: 
3: 5
9: 
0: 9 5 3
16: 
12: 16

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

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

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

Эффективный подход. Чтобы оптимизировать описанный выше подход, идея состоит в том, чтобы использовать самобалансирующиеся двоичные деревья поиска. Set в C++ реализован с использованием самобалансирующихся BST и может быть использован для решения этой проблемы. Следуйте инструкциям, чтобы решить проблему:

• Инициализируйте Set s , который хранит элементы в неубывающем порядке.
• Пройдите массив по индексам от 0 до N – 1 и выполните следующие операции:
  • Вставьте arr[i]в множество s .
  • Итерируйте от начала набора до p и распечатайте элементы в наборе.

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

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