Maximum Difference Between the First and Last Indexes of an Element in an Array

Approach

Running two loops to determine the difference for each element and then updating the max diff is a simple brute force method. In this approach, we also need to keep track of the elements that have been visited so that the difference between them is not calculated unnecessarily. It has an O(n²) time complexity.

We can reduce the time complexity by using an efficient approach, i.e. Hashing.  The steps are as follows:

Step 1: We have to traverse the given input array from left to right.

Step 2: Now, map each distinct element's first and last hash indexes.

Step 3: Calculate each element's first and last index difference by iteratively traversing the hash table. Consequently, update max_diff.

Step 4: Return maximum difference.

Explanation

When given an integer array, we must determine how each value's first and last indexes differ from one another. Find the biggest difference between any number's first and last index. We're going to use hashing for this. We will examine an element of an array to determine its first and last indices or the order in which it appears.

Put all the elements and their first and last indexes into the map, then traverse it. Selecting each element now will allow determining the difference between its first and last indices, which should be the greatest of all. To monitor the largest difference, we can use the variable max_diff. 

C++ Code 

#include <bits/stdc++.h>

using namespace std;

int max_Difference(int arr[], int n)
{
       struct index
   {
       int f, l;
   };
   
   unordered_map<int, index> m;
   
   for (int i=0; i<n; i++)
   {
       // storing the first index
       if (m.find(arr[i]) == m.end())
           m[arr[i]].f = i;
       
       // storing the last index   
       m[arr[i]].l = i;   
   }
   
   int diff, max_diff = INT_MIN;
   
   unordered_map<int, index>::iterator it;

   // traversing 'm'
   for (it=m.begin(); it != m.end(); it++)
   {  
       // first and last index difference
     
       diff = (it->second).l - (it->second).f;
       
         if (max_diff < diff)
           max_diff = diff;
   }
   
   return max_diff;
}

int main()
{
   int arr[] = {9, 1, 3, 4, 5, 1, 6, 1, 7};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout  <<max_Difference(arr, n);
   return 0;    
}

You can also try this code with Online C++ Compiler

Run Code

Output:  

6

You can also try this code with Online C++ Compiler

Run Code

Time Complexity

O(n), where "n" is the array's total number of elements. We were able to achieve linear time complexity because we used HashMap.

Auxiliary Space 

O(n), where "n" is the array's element count. This HashMap achieves linear space complexity because the sum was saved as the key.

You can also read about the Longest Consecutive Sequence.

Frequently Asked Questions

What is unordered_map?

An associated container called an unordered_map holds elements created by combining a mapped value with a key-value pair. The element is identified specifically by its key value, and the mapped value is the content related to the key.

What is hashing?

The process of mapping keys and values into a hash table using a hash function is known as hashing.

What is the time complexity of the hashing method solution for the problem “Maximum Difference Between the First and the Last Indexes of an Element in an Array”?

O(n) will be the worst-case time complexity.

What is the space complexity of the hashing method solution for the problem “Maximum Difference Between the First and the Last Indexes of an Element in an Array”?

O(n) will be the worst-case space complexity.

What is a contiguous Subarray?

A contiguous subarray is just a subarray of an array with the requirement that the subarray's elements be in the same exact order as the elements in the parent array.

Conclusion

In this article, we have discussed the famous coding question based on the hash map and its time and space complexity in detail. 

To give an edge to your coding preparation, you can refer to our blog Distribute a maximum number of chocolates amongst X students, Clone a binary tree with random pointers, and Flattening a Multi-level Linked List(Depth Wise). You can also refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, React, JavaScript, System Design, etc. 

Recommended Problems -

• Flattening A Linked List
• Sorted Doubly Linked List
• Linked List Cycle ii