Special Subarray

Moderate
0/80
profile
Contributed by
21 upvotes
Asked in companies
Expedia GroupWalmartMathworks

Problem statement

You are given an array ‘ARR’ of size ‘N’. Your task is to find the special subarray of ‘ARR’. A special subarray is the smallest contiguous part of an array that contains all the occurrences of the most frequent element of the array.

For example: 
You are given ‘ARR’ = {1, 3, 4, 3, 5}. Then our answer will be {3, 4, 3} because the most frequent element is 3, and the subarray {3, 4, 3} contains all the occurrences of 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains an integer 'N' denoting the size of the ‘arr’.

The second contains ‘N’ space-separated integers representing the elements of the array ‘arr’.
Output Format: 
For each test case, print the elements of the special subarray separated a space.

The output of each test case will be printed in a separate line.
Constraints: 
1 <= T <= 10 
1 <= N  <= 5000
0 <= ARR[i] <= 10 ^ 6

Time limit: 1 sec
Note: 
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Sample Input 1:
2
5
1 3 4 3 5
5
0 2 4 4 7
Sample Output 1:
3 4 3
4 4
Explanation:
For the first test case, you are given arr = {1, 3, 4, 3, 5}. Then our answer will be {3, 4, 3} because the most frequent element is 3, and the subarray {3, 4, 3} contains all the occurrences of 3.

For the second test case, you are given arr = {0, 2, 4, 4, 7}. Then our answer will be {4, 4} because the most frequent element is 3, and the subarray {4, 4} contains all the occurrences of 4.
Sample Input 2:
2
4
1 2 1 1 
6
4 5 6 8 8 8
Sample Output 2:
1 2 1 1
8 8 8
Hint

Keep track of the most frequent element.

Approaches (1)
Hashing

In this approach, we will keep track of the most frequent element using a HashMap. HashMap will contain key-value pairs where the key will be the distinct element of the ‘ARR’ and value will be its frequency.  Now, suppose X is the most frequent element. In that case, the special subarray will look like {X, …, X} because we can just remove any other preceding or succeeding element without affecting our answer as we want our special subarray to be the smallest possible. To obtain this subarray, we can just find the index of the first and the last occurrence of the most frequent element. We also have to keep track of the size of the subarrays for the case when the ‘ARR’ contains more than one element with maximum frequency.
 

Algorithm:

  • Initialize a map 'LEFT' to store left most occurrence of every element.
  • Initialize a map 'FREQMAP' to store the frequency of every element.
  • Initialize a variable 'MAXFREQ' to store the maximum frequency.
  • Initialize a variable 'MINLEN' to store the length of the smallest result subarray.
  • Initialize a variable 'STARTIDX' to store starting index of the smallest result subarray.
  • Iterate 'I' in 0 to 'N':
    • Set 'X' as 'ARR[I]'.
    • If the current element is not present in 'FREQMAP':
      • Put ('X', 'I') key-value pair in 'LEFT'.
      • Put ('X', 1) key-value pair in 'FREQMAP'.
    • Otherwise, increase the frequency of the current element in 'FREQMAP'.
    • If frequency of current element is greater than 'MAXFREQ':
      • Set 'MAXFREQ' as 'FREQMAP.GET(X)'.
      • Set 'MINLEN' as ('I' - 'LEFT.GET(X)' + 1).
      • Set 'STARTIDX' as 'LEFT.GET(X)'
    • If frequency of current element is equal to 'MAXFREQ' and ('I' - 'LEFT.GET(X)' + 1) is less than 'MINLENGTH':
      • Set 'MINLEN' as ('I' - 'LEFT.GET(X)' + 1).
      • Set 'STARTIDX' as 'LEFT.GET(X)'.
  • Initialize an integer array 'ANS' to store the output.
  • Initialize a variable 'IDX' to iterate through 'ANS'.
  • Iterate 'I' in 'STARTIDX' to 'STARTIDX' + 'MINLEN':
    • Set 'ANS[IDX]' as 'ARR[I]' and increment 'IDX' by 1.
  • Return 'ANS'.
Time Complexity

O(N), where N is the size of the input array ‘ARR’.
 

We have to iterate through the input array ‘ARR’ only twice in the worst case. Hence, the overall time complexity is O(N).

Space Complexity

O(N). where N is the size of the input array ‘ARR’.
 

The HashMaps ‘LEFT’ and ‘FREQMAP’ take O(N) space in the worst case. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Special Subarray
Full screen
Console