Finding second maximum in an array in most efficient way

Finding second maximum in an array in most efficient way

I am trying to find the second maximum in an array in the most efficient
way both in terms of space and time complexity, but I have two major
problems:
1. Time Complexity:
The naive or brute force approach will take two passes to find the
smallest element so O(n) complexity, If I sort the array then it would
take O(n2).
2. Space Complexity:
I can always use BST for O(log(n)) sorting but they will require
additional space for maintaining a tree, I can also create a heap and do
two deletes and I would get the second largest element but here also heap
is created and stored in memory.
What options do I have here?