Algorithm to find out the number of times a number occurs consecutively in an array in a range specified

I have an array say

8 3 5 4 4 4 4 4 3 2 7 11 12 7 7 7 7 1 2


total =17 elements now you are given a range say [2,11] both included ,now you have o find out the element that has occurred the max number of times and the number of times it has occurred

A simple traversing through the array in the range and keeping the track of the each element is one solution but time complexity is O(N) and if we are given N queries time complexity = O(N^2). Any faster algo than this ?

migrated from stackoverflow.comMar 17 '17 at 12:02

This question came from our site for professional and enthusiast programmers.

• Why do you think there is a better algorithm that O(n)? – Andy Turner Mar 17 '17 at 11:55
• Is it possible for the arrays to be nested? If not, what's the problem? – ForInfinity Mar 17 '17 at 11:58
• if you will not touch any of elements, the count cant be accurate, because that element can be any of already existing or another one... so you need to touch all, this is already O(n), so I believe O(n) is fastest – Arsen Mkrtchyan Mar 17 '17 at 11:59
• Are you promised that the values in the array will be from only a small set (fewer than N different values in the array)? If so, then there are better algorithms. If not, then we'll need different techniques. What's the context in which you encountered this problem? It looks like an intriguing exercise -- it would be helpful to credit the source of the exercise. – D.W. Mar 17 '17 at 15:52
• Also, are you more interested in the cost of a single query, or of the cumulative cost of N queries? The last line seems to imply the latter, in which case it might be possible to build a data structure to support N queries in less than O(N^2). For the former, as others have said, it is impossible to generate a solution for less than O(N). – shiri Mar 17 '17 at 16:29