CareerCup

enter each element in hash table and store starting and ending index. first time inserting an element in hash table starting and ending index is same, after that for duplicate elements update the ending index...

for each element the max distance will be (end index - start index + 1)

Time: O(N)
Space: O(N)

public static Map<Integer, Integer> calcularteMaxDistance( int[] arr ){
		
		Map<Integer, Integer> distance = new HashMap<>();		
		Map<Integer, Integer> firstOccurrence = new HashMap<>();
				
		for( int i = 0; i < arr.length; i++ ){
			
			if( firstOccurrence.containsKey( arr[i]) ){
				int firstIndex = firstOccurrence.get( arr[i] );
				distance.put( arr[i], i - firstIndex);
			}
			else {
				// first time occurrence
				firstOccurrence.put( arr[i], i );
				distance.put( arr[i], 0);
			}
		}
		
		
		return distance;
	}

Use a Self-Balanced Binary Search Tree. Let each node have 2 fields - start_index and end_index.

Insert elements into the BST along with the below operations.
If the element is not found in BST, create a node in BST using a[i]. Let start_index=end_index=i
If element is already found, then end_index=i

After inserting all the elements, traverse the BST to find the node with maximum distance.

Time Complexity Analysis
------------------------
Insert Operation= O(logN)
Inserting N elements = O(NlogN)
Other operations = O(1)

Time Complexity - O(NlogN)
Space Complexity - O(N)

One more solution:
Find the last occurrence of element by traversing from end.

Code:

public void maxDistance(int a[]) {
		TreeSet<Integer> t = new TreeSet<Integer>();
		for (int i = 0; i < a.length; i++) {
			if (!t.contains(a[i])) {
				int j = a.length - 1;
				while (j >= i) {
					if (a[i] == a[j]) {
						t.add(a[i]);
						System.out.println("Max(" + a[i] + ")= " + (j - i));
						break;
					}
					j--;
				}
			}
		}
	}

a = [1,2,3,4,1,1,7,4]
max_dist = {}

for i,e in enumerate(a):
    if e in max_dist:
        max_dist[e][-1] = i
    else:
        max_dist[e] = [i,i]
for k,v in max_dist.items():
    print '{0}:{1}'.format(k,v[-1]-v[0])

c++ code:

#include <cstdio>
#include <map>
#include <vector>
#include <cstring>

using namespace std;

int main()
{
    int i = 0;
    int t = 0;
    int n = 0;
    map<int, vector<int> > position;
    scanf("%d", &n);
    for(i = 0; i < n; i++)
    {
        scanf("%d", &t);
        position[t].push_back(i);
    }
    for(map<int, vector<int> >::iterator it = position.begin(); it != position.end(); it++)
    {
        t = 0;
        if(it->second.size() > 0)
        {
            t = it->second[it->second.size() - 1] - it->second[0];
        }
        printf("max(%d)=%d\n", it->first, t);
    }
    return 0;
}

public static HashMap<Integer, Integer> findAllMaxDistance(int[] arr){
	HashMap<Integer, Integer> hashFirst = new HashMap<Integer, Integer>();
	HashMap<Integer, Integer> hashLast = new HashMap<Integer, Integer>();
	HashMap<Integer, Integer> result = new HashMap<Integer, Integer>();
	
	/* Record the first index for all the characters */
	for(int i = 0; i < arr.length; i++){
		if(!hashFirst.containsKey(arr[i])){
			hashFirst.put(arr[i], i);
		}
	}
	/* Record the last index for all the characters */
	for(int i = arr.length - 1; i >= 0; i--){
		if(!hashLast.containsKey(arr[i])){
			hashLast.put(arr[i], i);
		}
	}
	/* Compute the max distance for all the characters */
	for(int i = 0; i < arr.length; i++){
		if(!result.containsKey(arr[i])){
			result.put(arr[i], hashLast.get(arr[i]) - hashFirst.get(arr[i]));
		}
	}
	
	return result;
}

import java.util.HashMap;
import java.util.Map;
public class MaxDistance {
    public static Map<Integer, Integer> getMaxDists(int a[]) {
        Map<Integer, Integer> ret = new HashMap<Integer, Integer>();
        Map<Integer, Integer> firstOccurance = new HashMap<Integer, Integer>();
        int maxDist = 0;
        for (int i = 0; i < a.length; ++i) {
            Integer j = firstOccurance.get(a[i]);
            if (j == null) {
                firstOccurance.put(a[i], i);
                j = i;
            }
            ret.put(a[i], i - j);
        }
        return ret;
    }
    public static void main(String args[]) {
        int a[] = new int[] {1, 2, 3, 4, 1, 1, 7, 4};
        Map<Integer, Integer> ans = getMaxDists(a);
        for (Map.Entry<Integer, Integer> entry : ans.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }
}

not understood

Logic:
-Search the first occurrence of element from left side say elementLeftIndex
-Search the first occurrence of element from right side say elementRightIndex
-now [elementLeftIndex-elementRightIndex+1] is the max length as asked in qus
-apply logic for all elements

Correct me if I'm wrong, but isn't the max distance the position of the last occurrence subtracted from the position of the first occurrence?

In C#

static uint FindDistance( List<int> numberList, int target ) {

	uint lastPos = ~0;
	uint firstPos= ~0;

	for( int i = 0; i < numberList.Count; ++i ) {
		if( numberList[ i ] == target ) {
			if( firstPos == ~0 ) 
				firstPos = i;

			lastPos = i;
		}	
	}

	return lastPos - firstPos;
}

HashMap l_DistMap = new HashMap();
		
		for (int i = 0 ; i < input.length; i++)
		{
			if(! l_DistMap.containsKey(input[i]))
				l_DistMap.put(input[i],i);
		}
		
		int l_minIndex;
		
		for (int i = input.length - 1 ; i >= 0; i--)
		{
			if(l_DistMap.containsKey(input[i]))
			{
				l_minIndex = Integer.parseInt(l_DistMap.get(input[i]).toString());
				System.out.println(input[i] + ":" + i + " - " + l_minIndex + " = " + (i - l_minIndex));
				l_DistMap.remove(input[i]);
			}
		}

HashMap l_DistMap = new HashMap();
		
		for (int i = 0 ; i < input.length; i++)
		{
			if(! l_DistMap.containsKey(input[i]))
				l_DistMap.put(input[i],i);
		}
		
		int l_minIndex;
		
		for (int i = input.length - 1 ; i >= 0; i--)
		{
			if(l_DistMap.containsKey(input[i]))
			{
				l_minIndex = Integer.parseInt(l_DistMap.get(input[i]).toString());
				System.out.println(input[i] + ":" + i + " - " + l_minIndex + " = " + (i - l_minIndex));
				l_DistMap.remove(input[i]);
			}
		}

HashMap l_DistMap = new HashMap();
		
		for (int i = 0 ; i < input.length; i++)
		{
			if(! l_DistMap.containsKey(input[i]))
				l_DistMap.put(input[i],i);
		}
		
		int l_minIndex;
		
		for (int i = input.length - 1 ; i >= 0; i--)
		{
			if(l_DistMap.containsKey(input[i]))
			{
				l_minIndex = Integer.parseInt(l_DistMap.get(input[i]).toString());
				System.out.println(input[i] + ":" + i + " - " + l_minIndex + " = " + (i - l_minIndex));
				l_DistMap.remove(input[i]);
			}
		}

1. Create an array called index array which stores the indexes of elements of input array. Initialize index[i]=i for i=0 to n-1
2. Now sort the input array and while sorting also maintain the order of indexes in index array corresponds to the each element in the input array. This can be done using O(nlogn) sorting algorithm
3. Now traverse both the input and index arrays and calculate the max length for each element. This can be done on O(n) time.

Time Complexity: O(nlogn)
Space: O(n)

Hope this won't be considered cheating ;)

import re

def max_distance(elements):
    merged = ''.join([str(x) for x in elements])
    for item in elements:
        try:
            k = re.search(r'(%s.+%s)' % (item, item), merged).group(1)
        except:
            k = ' '
        print 'for %s: %s' % (item,(len(k)-1))

for 1: 5
for 2: 0
for 3: 0
for 4: 4
for 1: 5
for 1: 5
for 7: 0
for 4: 4

Iterate over an array from start to end for a given number, find out its first and last position in an array

int low=size;
int hight=-1;

for(i=0;i<size;i++)
{
	if( a[i] == x) / *x is input number */
		if( i < low )
			low = i;
		if( i > high )
			high = i;
}
if( high < low )
	return 0;

return high-low;

time complexity is O(n).