Given a sorted array, find the maximum subarray of duplicate values

Question

Another question about the interview asked me to find the maximum possible subset of duplicate values ​​given the sorted array in the shortest possible time.

Let input array be A[1 ... n] Find an array B of consecutive integers in A such that: for x in range(len(B)-1): B[x] == B[x+1] 

I believe that the best algorithm divides the array in half and goes from the middle to the outside and compares the integers from the middle with each other and finds the longest voltage of the same integers from the middle. Then I would call the method recursively, dividing the array in half and calling the method on both halves.

My interviewer said that my algorithm is good, but my analysis of the fact that the O (logn) algorithm is incorrect, but never reached the point of telling me what the correct answer is. My first question is what is the Big-O analysis of this algorithm? (Show as much work as possible, please, Big-O is not my forte.) And my second question is solely for my curiosity, is there an even more time-efficient algorithm?

Answer 1

The best you can do for this problem is O(n) solution, so your algorithm cannot be both correct and O(lg n) .

Consider, for example, the case when the array does not contain duplicate elements. To determine this, we need to study each element and study each element of O(n) .

This is a simple algorithm that will find the longest subsequence of a repeating element:

 start = end = 0 maxLength = 0 i = 0 while i + maxLength < a.length: if a[i] == a[i + maxLength]: while i + maxLength < a.length and a[i] == a[i + maxLength]: maxLength += 1 start = i end = i + maxLength i += maxLength return a[start:end] 

If you have reason to believe that the subsequence will be long, you can set the initial value of maxLength to some heuristic value to speed things up, and then only look for shorter sequences if you don't find them (i.e. you get end == 0 after the first pass.)

Answer 2

I think we all agree that in the worst case, when all A unique or where all A same, you need to examine each element of the array to determine if there are duplicates or to determine the whole array contains one number. Like other posters, this will be O(N) . I'm not sure separation and victory will help you with the algorithmic complexity on this, although you can simplify the code a bit using recursion. To split and win really helps to cut Big O when you can throw away large parts of the input (e.g. binary search), but in the case when you potentially need to examine all the input data, it will not be much different.

I assume the result is that you are simply returning the size of the largest B you found, although you can easily change this to return B.

So, at the front of the algorithm, given that A is sorted, I'm not sure if the answer will be faster / simpler than just going through the array in order. It seems that the simplest answer is to have 2 pointers, one starting at index 0 and one starting at index 1. Compare them and then increase both of them; every time they are the same, you point the counter up to give you the current size B , and when they differ from you reset, which corresponds to zero. You also save the variable for the maximum size B that you have found so far, and update it every time you find a larger B

Answer 3

In this algorithm, elements n visited with a constant number of calculations for each element visited, so the operating time is O(n) .

Given the sorted array A[1..n] :

 max_start = max_end = 1 max_length = 1 start = end = 1 while start < n while A[start] == A[end] && end < n end++ if end - start > max_length max_start = start max_end = end - 1 max_length = end - start start = end 

Answer 4

Assuming that the largest consecutive integers are only 1 in length, you will scan the entire array A of n elements. Thus, complexity is not in terms of n, but in terms of len (B).

Not sure if the complexity is O (n / len (B)).

Check 2x Case

- When n == len (B), you get an instant result (only check A [0] and A [n-1] - When n == 1, you get O (n) by checking all the elements - When the normal case, I'm too lazy to write an algorithm for analysis ...

Edit

Given that len(B) not known in advance, we must take the worst case, i.e. O (n)