Brute force
- Use a dictionary to store element indices.
- Initialize max distance as -1.
- Iterate through the array.
- Update max distance when encountering the same element.
- Return the maximum distance found.
Example: Below are implementations of the idea.
Javascript
function maxDistance(arr) { let dict = {}; let maxD = -1; for (let i = 0; i < arr.length; i++) { if (dict[arr[i]] !== undefined) { maxD = Math.max(maxD, i - dict[arr[i]]); } else { dict[arr[i]] = i; } } return maxD; } let arr = [1, 2, 4, 1, 3, 4, 2, 5, 6, 5]; console.log( "Max distance between occurrences of same element: " + maxDistance(arr)); |
Output
Max distance between occurrences of same element: 5
Time Complexity: O(N^2)
Space Complexity: O(1)
JavaScript Program to find Maximum Distance Between two Occurrences of Same Element in Array
Given an array of repeated elements, the task is to find the maximum distance between two occurrences of an element.
Example:
Input : arr[] = {3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2}
Output: 10
// maximum distance for 2 is 11-1 = 10
// maximum distance for 1 is 4-2 = 2
// maximum distance for 4 is 10-5 = 5
Table of Content
- Brute force:
- Optimal Solution: