I was given this question for an amazon interview

"""
Given an array, for each element find the value of the nearest element to the
right which is having a frequency greater than as that of the current element.
If there does not exist an answer for a position, then make the value ‘-1’.

Input : a[] = [1, 1, 2, 3, 4, 2, 1]

1 = 3
2 = 2
3 = 1
4 = 1

Output : [-1, -1, 1, 2, 2, 1, -1]
"""

The interviewer then asked me about how I would design the solution in O(n)

My solution was:
1. put the freques of the number in an array of pos belonging to the number:
ex: for the array [1, 1, 2, 3, 4, 2, 1]
the frequencies array would be : [3, 3, 2, 1, 1, 2, 3]
2. now look for the right most higer number from the frequecy array starting from the position of the present element that is being chehcked and if there is a number that is greater than the frequency of the present element put the position of that number from the frequency array to the result array or put -1

howver the interviewer started cutting me off saying to get the positon of the next higer frequency you have to use a loop, and that is why this is not a o(n) solution.
I asked him for the solution, and even he couldnot find one and asked me to just google it. However beyond thatm I want to know, is that if he was right is saying the solution that I was making was not in O(n) !