Nearest elements in the array

Question

Suppose you have an unsorted array, as you find 2 equal elements so that they are the farthest in the array. For example, 8 7 3 4 7 5 3 9 3 7 9 0 ans would be 7(9) - 7(1) = 8 . I thought about the following

 initialise max = 0 using hashing, store the elements along with its index whenever there is a collision, compare the current index with the hashed one if it is greater, set max = current index - hashed one and copy element along with index to some other location. 

executed in time - O (n) and space - O (n). It's right? There is a better solution.

Answer 1

O (n) operating time and O (n) space seems to be optimal AFAIK.

Here's the python implementation:

 #!/usr/bin/python hashindex = {} l = [8,7,3,4,7,5,3,9,3,7,9,0] max_diff = 0 value = 0 for i in range(len(l)): indices = hashindex.get(l[i], None) if indices: hashindex[l[i]] = (indices[0], i) else: hashindex[l[i]] = (i, i) diff = hashindex[l[i]][1] - hashindex[l[i]][0] if diff > max_diff: max_diff = diff value = l[i] print max_diff, value 

Answer 2

I doubt very much that this is the correct answer, but if I were given this problem at work, I would do a quick sort by sort type by value, and then by index. Then I will go through my ordered array and for each value I will take the first and last index. This will be the maximum distance of the candidate. Each time I came across a new value, I would compare it with my current maximum distance, and then save only the max. So the runtime will be

sort + walk = total N Log N + N = N Log N

Example: Values ​​in an unordered array: 1,2,3,1,5,3,3,3

1,1,2,3,3,3,3,5 = Value 0,3,1,2,5,6,7,4 = Index

1 = max 3-0 = 3

2 = x

3 = max 7-2 = 5

Max 5

Remember that this is probably NOT the answer of the tutorial, but it still works in N Log N, so I would use it when working without any problems for anything under a million elements.

Do you find any other potential answers to the problem? How about ways to improve this?

Answer 3

Here is my idea for a better solution:

Since the two elements will be the most distant from each other, I would make a loop that looks at the beginning of the array and at the end of the array at the same time, and looks inward, the first corresponding elements that they find will be the most distant.

For instance:

 8 7 3 4 7 5 3 9 3 7 9 0 First look at 8, 0, and store them in set A, and in set B respectively. Look at 7, 9, and store them in the same sets fashion. Look at 3, 7, and same as above. Now this 7 is already in the opposite set, A. Therefore they must be the farthest apart. Just calculate the distance between the the 7 elements. 

Now, when I think about it, you just need to do some kind of check to make sure that the farthest elements are now in the set itself.

So, if any of the sets has 1/3 of all elements, you should also start checking to see if the greatest distance is inside the set itself.

Answer 4

My solution in Java: int [] testArr = {1,2,3,5,1,7,5,4,3,1,2,3,2,3}; int maxLen = 0; int minidx = 0; int maxidx = 0; int numVal = testArr [0]; int counter = 0; // Just to check how many times it enters inside the lower condition if

 for (int ii=0;ii<testArr.length-maxidx;ii++) { for (int jj=testArr.length-1;jj>=ii+maxidx;jj--){ if(testArr[ii]==testArr[jj] /*&& maxLen<(jj-ii)*/){ System.out.println(counter++); minidx = ii; maxidx = jj; maxLen = jj-ii; numVal = testArr[ii]; break; } } } System.out.println(maxLen +" "+minidx+" "+maxidx+" "+numVal); 

Answer 5

executed in time - O (n) and space - O (n). Is it correct?

Yes.

Is there a better solution.

I highly doubt it.

JavaScript execution:

 function furthest(a) { const first= {}; return a.reduce((longest, elt, idx) => { if (!(elt in first)) first[elt] = idx; return Math.max(longest, idx - first[elt]); }, Infinity); } 

Answer 6

Solution in obj-c. Must be O (N). Just one pass through the array.

 //NSMutableArray *numbers = [[NSMutableArray alloc] initWithArray:@[@3,@2,@1,@7,@1,@2,@3,@6,@5,@4,@4,@5,@6,@7]]; //int solution = [self maxDistanceBetweenPairs:numbers]; //NSLog(@"%d", solution); - (int)maxDistanceBetweenPairs:(NSMutableArray *)A { NSMutableDictionary *dictionary = [NSMutableDictionary dictionary]; __block int max = 0; int i = 0; for (NSNumber *num in A) { if ([dictionary objectForKey:num]) { int first = [[dictionary objectForKey:num] intValue]; if (i - first > max) { max = i - first; } } else { [dictionary setObject:[NSNumber numberWithInt:i] forKey:num]; } i++; } return max; }