1
$\begingroup$

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 ?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Why do you think there is a better algorithm that O(n)? $\endgroup$ – Andy Turner Mar 17 '17 at 11:55
  • $\begingroup$ Is it possible for the arrays to be nested? If not, what's the problem? $\endgroup$ – ForInfinity Mar 17 '17 at 11:58
  • $\begingroup$ 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 $\endgroup$ – Arsen Mkrtchyan Mar 17 '17 at 11:59
  • $\begingroup$ 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. $\endgroup$ – D.W.♦ Mar 17 '17 at 15:52
  • $\begingroup$ 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). $\endgroup$ – shiri Mar 17 '17 at 16:29
-1
$\begingroup$

Define a sub problem solution as the range of longest sub series. If there are more than one we solution is 2 at most. The once at the tips of the range. and there are exactly (n^2-n)/2 sub problems here. You can solve each sub problem in o(n).

If you were to remember the results of problems you solved. You can remember all in o(n*(n^2-n)/2) and it's fine.

But, If you consider Dynamic programming. There is a bottom up series to solve each sub problem in o(1) time.

when trying to solve(i,j) two cases are to consider:

the range is at the tip. so consider increasing the result. the range is at the tip. just return the longest. again up to 2 ranges.

Improve this answer
$\endgroup$
  • $\begingroup$ Who voted down? Care to leave a comment? $\endgroup$ – Dolev Mar 17 '17 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.