Given an array, A.Let x be an element in the array.x has the maximum frequency in the array.Find the smallest subsegment of the array which also has x as the maximum frequency element.
Examples:
Input : arr[] = {4, 1, 1, 2, 2, 1, 3, 3}
Output : 1, 1, 2, 2, 1
The most frequent element is 1. The smallest
subarray that has all occurrences of it is
1 1 2 2 1
Input : A[] = {1, 2, 2, 3, 1}
Output : 2, 2
Note that there are two elements that appear
two times, 1 and 2. The smallest window for
1 is whole array and smallest window for 2 is
{2, 2}. Since window for 2 is smaller, this is
our output.
Approach:Observe that if X is the maximum repeated element of our subsegment then the sunsegment should look like this [X, ….., X], cause if the subsegment end or begins with another element we can delete it which does not alter our answer.
To solve this problem, let us store for every distinct element in the array three values, index of the first occurrence of the element and the index of the last occurrence the element and the frequency of the element. And at every step for a maximum repeated element minimize the size of our subsegment.
C++
// C++ implementation to find smallest // subarray with all occurrences of // a most frequent element #include <bits/stdc++.h> using namespace std; void smallestSubsegment(int a[], int n) { // To store left most occurrence of elements unordered_map<int, int> left; // To store counts of elements unordered_map<int, int> count; // To store maximum frequency int mx = 0; // To store length and starting index of // smallest result window int mn, strindex; for (int i = 0; i < n; i++) { int x = a[i]; // First occurrence of an element, // store the index if (count[x] == 0) { left[x] = i; count[x] = 1; } // increase the frequency of elements else count[x]++; // Find maximum repeated element and // store its last occurrence and first // occurrence if (count[x] > mx) { mx = count[x]; mn = i - left[x] + 1; // length of subsegment strindex = left[x]; } // select subsegment of smallest size else if (count[x] == mx && i - left[x] + 1 < mn) { mn = i - left[x] + 1; strindex = left[x]; } } // Print the subsegment with all occurrences of // a most frequent element for (int i = strindex; i < strindex + mn; i++) cout << a[i] << " "; } // Driver code int main() { int A[] = { 1, 2, 2, 2, 1 }; int n = sizeof(A) / sizeof(A[0]); smallestSubsegment(A, n); return 0; } |
Java
// Java implementation to find smallest // subarray with all occurrences of // a most frequent element import java.io.*; import java.util.*; class GfG { static void smallestSubsegment(int a[], int n) { // To store left most occurrence of elements HashMap<Integer, Integer> left= new HashMap<Integer, Integer>(); // To store counts of elements HashMap<Integer, Integer> count= new HashMap<Integer, Integer>(); // To store maximum frequency int mx = 0; // To store length and starting index of // smallest result window int mn = -1, strindex = -1; for (int i = 0; i < n; i++) { int x = a[i]; // First occurrence of an element, // store the index if (count.get(x) == null) { left.put(x, i) ; count.put(x, 1); } // increase the frequency of elements else count.put(x, count.get(x) + 1); // Find maximum repeated element and // store its last occurrence and first // occurrence if (count.get(x) > mx) { mx = count.get(x); // length of subsegment mn = i - left.get(x) + 1; strindex = left.get(x); } // select subsegment of smallest size else if ((count.get(x) == mx) && (i - left.get(x) + 1 < mn)) { mn = i - left.get(x) + 1; strindex = left.get(x); } } // Print the subsegment with all occurrences of // a most frequent element for (int i = strindex; i < strindex + mn; i++) System.out.print(a[i] + " "); } // Driver program public static void main (String[] args) { int A[] = { 1, 2, 2, 2, 1 }; int n = A.length; smallestSubsegment(A, n); } } // This code is contributed by Gitanjali. |
Output:
2 2 2
Time Complexity : O(n)
leave a comment
0 Comments