Is there a way to implement it without a temporary sorted array?
Yes - at least not a sorted array of size n, but of size 3.
A single pass through the list only needs to keep track of the 3 largest prior values. So we still have a sorted array of 3.
// Pseudo code
Fill max_list[3] with first 3 array elements.
product = max_list[0] * max_list[1] * max_list[2]
for (i = 3; i < n; i++) {
if (list[i] > max_list[0]) {
max_list[0] = list[i]
sort_list low to high
form product
}
output product to expected array
}
Complexity: O(n).
OP mentions value are non-negative. Even with negatives only short lists are needed.