Max distance between same elements

Given an array arr[] with repeated elements, the task is to find the maximum distance between two occurrences of an element.

Note: You may assume that every input array has repetitions.

Examples:

Input: arr = [1, 1, 2, 2, 2, 1]
Output: 5
Explanation: distance for 1 is: 5-0 = 5, distance for 2 is : 4-2 = 2, So max distance is 5.

Input: arr = [3, 2, 1, 2, 1, 4, 5, 8, 6, 7, 4, 2]
Output: 10
Explanation: maximum distance for 2 is 11-1 = 10, maximum distance for 1 is 4-2 = 2 ,maximum distance for 4 is 10-5 = 5, So max distance is 10.

Expected Time Complexity : O(n)
Expected Auxilliary Space : O(n)

Constraints:
1 <= arr.size() <= 10⁶
1 <= arr[i] <= 10⁹

Approach 01:

#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxDistance(vector<int>& numbers) {
        unordered_map<int, int> indexMap;
        int arraySize = numbers.size();
        int maxDist = 0;

        for (int i = 0; i < arraySize; ++i) {
            if (indexMap.find(numbers[i]) != indexMap.end()) {
                int firstIndex = indexMap[numbers[i]];
                int currentDist = i - firstIndex;
                maxDist = max(maxDist, currentDist);
            } else {
                indexMap[numbers[i]] = i;
            }
        }

        return maxDist;
    }
};

class Solution:
    def maxDistance(self, numbers):
        indexMap = {}
        maxDist = 0

        for i, currentNum in enumerate(numbers):
            if currentNum in indexMap:
                firstIndex = indexMap[currentNum]
                currentDist = i - firstIndex
                maxDist = max(maxDist, currentDist)
            else:
                indexMap[currentNum] = i

        return maxDist

Time Complexity

• Iterating through the array:

  The function iterates through the input vector exactly once to record the first occurrence of each element and compute the maximum distance between duplicate elements. This takes \(O(n)\), where \(n\) is the size of the input vector.

• Hash map operations:

  Inserting elements into and looking up elements from an unordered map takes \(O(1)\) on average. Since these operations are performed for each element in the array, the overall time complexity remains \(O(n)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n)\), where \(n\) is the size of the input vector.

Space Complexity

• Auxiliary Space:

  The function uses an unordered map indexMap to store the first occurrence of each element in the input vector. In the worst case, where all elements are unique, the map will store \(n\) elements. Thus, the space complexity is \(O(n)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where \(n\) is the size of the input vector.