Home » Data Structure » Hashing Coding Problems

# Maximum distance between two occurrences of same element in array

Here, we are going to see how efficiently we can use a **hash table to find the maximum distance between two occurrences of the same element in the array**?

Submitted by Radib Kar, on July 02, 2020

Prerequisite: Hashing data structure

**Problem statement:**

Find maximum distance between two occurrences of same element in the array.

**Example:**

Input array= [1, 2, 3, 1, 2, 4, 5, 6, 2, 3]

The maximum distance between any two same elements is 7. The leftmost position for key 2 is 1 and the rightmost position for key 2 is 8 and thus the distance is 7 which is maximum. For any other keys, the max distances between their positions are less than 7.

**Solution:**

We can solve this problem using a hash map (hash table). One thing is clear that to achieve maximum distance between two occurrences of the same element, we need to keep track of all positions for the elements (key). So, our target is to find maximum differences between positions for any unique element in the array. For example say, element A has positions 2, 7, 8, and another element B has positions 1, 10. Then the maximum distance for element A is 8-2=6, whereas maximum distance for element B is 10-1=9

So how can we design the problem with the hash table and what will be the hash function?

Okay, so here each element is our key and the hash table is has the size of the range of the array. So, if the range of the array is [0,15] then the hash table size would be 16.

What will be our hash function and how would we map the keys to the corresponding location in the hash table?

The hash function *h(x)=x* here but instead of storing the key itself using linear probing, we will store the positions using linear probing. But in my implementation, I have used vector to store easily instead of a linked list.

So, for example, if we have three 2s as our key, the hash table will store the three unique positions of 2 at location 2.

So, after the hash table is created we can easily find the maximum distance between occurrences for each unique key and can finally achieve the maximum distance between two occurrences for the same element in the array.

So the algorithm will be,

**Step 1:**

Create the hash table like below: Initially hash table is empty For each key in input array: Hash[key].push_back(key_position)

**Step 2:**

Initiallymax_distance=0For each location If(difference(last position-first position)>max_distance) Update max_distance as difference(last position-first position) After this,max_distancecontains the maximum distance between two occurrences of same elements in the array.max_distance= the maximum distance between two occurrences of same elements in the array.

**Dry run with the example:**

Input array is = [1, 2, 3, 1, 2, 4, 5, 6, 2, 3] So hash table size would be (6-1)+1=7 After creating the hash table as step1 we will have, Index Value 1 0->3 2 1->4->8 3 2->9 4 5 5 6 6 7 Somax_distance= 7 for both 2(8-1) and 3(9-2) Thus the answer is7

**C++ implementation:**

// C++ program to find maximum distance between // two occurrences of same element in array #include <bits/stdc++.h> using namespace std; int maximum_distance_bw_occurences(vector<int> arr, int n) { //create a hash table where for each key the //hash function is h(arr[i])=arr[i] //we will use stl map as hash table and //will keep i stored(i of arr[i]) //so say two keys arr[0] and arr[5] are mapping //to the same location, then the location will have value 0,5 //instead of the keys itself map<int, vector<int> > hash; //for each number for (int i = 0; i < arr.size(); i++) { hash[arr[i]].push_back(i); } //now to find max distance b/w two occurrences //we need to check difference b/w first and //last position for each unique keys //maxdiff=max(last-first) for each unique key int maxdiff = 0; for (auto it = hash.begin(); it != hash.end(); it++) { int first = it->second[0]; int last = it->second[it->second.size() - 1]; if (last - first > maxdiff) { maxdiff = last - first; } } //so ans will be updated maxdiff return maxdiff; } int main() { int n; cout << "Enter number of elements\n"; cin >> n; vector<int> arr(n, 0); cout << "Input the array elements\n"; for (int i = 0; i < n; i++) { cin >> arr[i]; } cout << "Minimum number of deletion required to make all elements same is: "; cout << maximum_distance_bw_occurences(arr, n) << endl; return 0; }

**Output:**

Enter number of elements 10 Input the array elements 1 2 3 1 2 4 5 6 2 3 Minimum number of deletion required to make all elements same is: 7

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions