If ans is O(n) with space O(n) then,
I think question should also mention that all elements are non-negative. right ?
If the Given Array is Sorted than it is pretty easy
U can look into solution here
If Not Sorted than there is Moore's Voting Algorithm Which can be Done in O(n)
In d link mentioned below. Yeah. :)