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

Browse Categories

Table of contents

1.

Introduction

2.

Problem Statement

2.1.

Example

3.

Approach

3.1.

Explanation

3.2.

Time Complexity

3.3.

Auxiliary Space

4.

Frequently Asked Questions

4.1.

What is unordered_map?

4.2.

What is hashing?

4.3.

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”?

4.4.

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”?

4.5.

What is a contiguous Subarray?

5.

Conclusion

Last Updated: Mar 27, 2024

Medium

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

Finding the difference between the first and last index of each number in an array so that the difference is the greatest of all is required to solve the problem "Maximum difference between the first and the last indexes of an element in an array."

Let's see an example to understand the problem:

Example

Input :

{9, 1, 3, 4, 5, 1, 6, 1, 7}

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

Element 1's first and last indices are 1 and 7, respectively.

The difference equals 7 - 1 to 6.

Other elements' first and last index differences are smaller than that of 1.

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^{2}) 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

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.