Maximum difference between first and last indexes of an element in array

Suppose, you have an array of integers. The problem “Maximum difference between first and last indexes of an element in array” asks to find out the difference between the first and last index of each number present in an array such that the difference is being maximum of all.

Example

arr[] =  {2, 3, 5, 1, 4, 6, 2, 5};

6

Explanation

2’s first index → 0

2’s last index → 6

Maximum difference (6-0) = 6

arr[] =  {2, 3, 6, 5, 4, 5, 1, 4};

3

Explanation

4’s first index → 4

4’s last index → 7

Maximum difference (7-4) = 3

Algorithm

1. Traverse the whole array.
2. Pick each element of an array and get its first and last element and store it into the HashTable.
3. Traverse the map:
   1. Find out the difference between the first and the last index of each element.
   2. Store the maximum difference into some variable and keep updating it whenever you find the maximum value than the previous value.
4. Return maximum difference.

Explanation

We are given an integer array, we need to find out the difference between the first index and last index of each value of an array. Find out the maximum difference for any number between its first and last index. For this, we are going to use Hashing. We will take an array element and will find out its first index and last index or when it occurs firstly and last.

Traverse the map after putting all the elements and their first and last index into the map. Now pick each element and then take their first and last index and will find out the difference such that it should be maximum of all. We can use a variable maximumDifference to keep an eye on the maximum difference. We will use a class and its object to store the first and the last index of every element.

Let us consider an example:

Example

Arr[]={2, 3, 5, 1, 4, 6, 2, 5}

We have an array input. To solve this we will use a class. We will look for every element if it is being traversed for the first time. Then we will be storing its index as the first index and when that same element comes again. Then each time we will be storing its index as second index. Using this method, we have a map as:

Map:1-> 3:null,

2-> 0:6,

3-> 1, null,

4-> 4:null,

5-> 2:7,

6-> 5:null

We will traverse the Map, and we will take each value and check the differences of their indices. We are going to neglect all the values that have null values. So we have 2 and 5 and out of which 2 has a maximum difference (6) between its first and last index than 5 which has a difference (5). So we are going to return the 6 as maximum difference and that would be our answer.

C++ code to find maximum difference between first and last indexes of an element in array

#include<bits/stdc++.h>

using namespace std;

int maxDifference(int arr[], int n)
{
    struct IndexValue
    {
        int fir, last;
    };
    unordered_map<int, IndexValue> MAP;
    for (int i=0; i<n; i++)
    {
        if (MAP.find(arr[i]) == MAP.end())
            MAP[arr[i]].fir = i;

        MAP[arr[i]].last = i;
    }

    int difference, differenceIndex = INT_MIN;

    unordered_map<int, IndexValue>::iterator itr;
    for (itr=MAP.begin(); itr != MAP.end(); itr++)
    {
        difference = (itr->second).last - (itr->second).fir;
        if (differenceIndex < difference)
            differenceIndex = difference;
    }
    return differenceIndex;
}
int main()
{
    int arr[] = {2, 3, 5, 1, 4, 6, 2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference b/w the first and last index of a number= "<<maxDifference(arr, n);
    return 0;
}

Maximum difference b/w the first and last index of a number= 6

Java code to find maximum difference between first and last indexes of an element in array

import java.util.HashMap;
import java.util.Map;

class IndexValue
{
    int first;
    int second;
    public IndexValue()
    {
        super();
    }
}
class DifferenceOfIndexes
{
    private static int getIndexesDifferent(int[] arr)
    {
        int n = arr.length;
        int differenceIndex = 0;
        Map<Integer, IndexValue> MAP = new HashMap<Integer, IndexValue>();

        for (int i = 0; i < n; i++)
        {
            if (MAP.containsKey(arr[i]))
            {
                IndexValue iv = MAP.get(arr[i]);
                iv.second = i;
            }
            else
            {
                IndexValue iv = new IndexValue();
                iv.first = i;
                MAP.put(arr[i], iv);
            }
        }
        for (Map.Entry<Integer, IndexValue> entry : MAP.entrySet())
        {
            IndexValue iv = entry.getValue();
            if ((iv.second - iv.first) > differenceIndex)
            {
                differenceIndex = iv.second - iv.first;
            }
        }
        return differenceIndex;
    }
    public static void main(String[] args)
    {
        int arr[]= {2,3,5,1,4,6,2,5};
        System.out.println("Maximum difference b/w the first and last index of a number= "+ getIndexesDifferent(arr));
    }
}

Maximum difference b/w the first and last index of a number= 6

Complexity Analysis

Time Complexity

O(n) where “n’ is the number of elements in the array

Space Complexity

O(n) where “n’ is the number of elements in the array