Day 18 : Maximum Distance

Easy

0/40

Average time to solve is 19m

12 upvotes

Asked in companies

Problem statement

You have been given an array ‘ARR’ that might contain duplicate elements. Your task is to find the maximum possible distance between occurrences of two repeating elements i.e. elements having the same value. If there are no duplicate elements in the array, return 0.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer N denoting the length of the array.

The second line of input contains N integers denoting the elements of the array 'ARR'.

Output Format:

The output prints a single line containing an integer denoting the maximum distance.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

0 <= N <= 10^6    
-10^9 <= ARR[i] <= 10^9

Time Limit: 1sec

Sample Input 1:

9
1 3 1 4 5 6 4 8 3

Sample Output 1:

Explanation for Sample Output 1:

In the above array, the repeating elements are:- (1, 3, 4)
Distance between first and last occurrence of 1 = 2(index2 - index0)
Distance between first and last occurrence of 3 = 7(index8 - index1)
Distance between first and last occurrence of 4 = 3(index6 - index3)

So, for the above array, you must return 7, as this is the maximum possible distance between two repeating elements having the same value.

Sample Input 2:

4
1 3 2 4

Sample Output 2:

Hint 1

Hint 2

Check for all pairs in the array.

Approaches (2)

Approach 1

Approach 2

Brute Force

In the brute force approach, to consider all pairs we will use two nested loops. The outer loop is used to select one element for the pair and the inner loop will select another element. Now if both the elements are equal we will update the maximum distance with the distance between them if the distance between both is greater than the maximum distance.

Time Complexity

O(N^2), where N is the number of elements in the array.

In the worst case, we will be checking all the pairs in the array. The total number of unique pairs for an array of size N is (N * (N - 1)) / 2. Thus the order of time complexity will be O(N^2).

Space Complexity

O(1),

In the worst case, only constant extra space is required.

(100% EXP penalty)

Day 18 : Maximum Distance

Console