Given an array arr[] consisting of N integers from the range [1, N]( repetition allowed ), the task is to find the minimum common element for each possible subarray length. If no such element exists for any particular length of the subarray, then print -1.
Examples:
Input: arr[] = {1, 3, 4, 5, 6, 7}
Output: -1 -1 -1 4 3 1
Explanation:
K = 1: No common element exists. Therefore, print -1.
K = 2: No common element exists. Therefore, print -1.
K = 3: No common element exists. Therefore, print -1.
K = 4: Since 4 is common in all subarrays of size 4, print 4.
K = 5: Since 3 and 4 is common in all subarrays of size 5, print 3 as it is the minimum.
K = 6: Print 1 as it is the minimum element in the array.
Input: arr[]: {1, 2, 2, 2, 1}
Output: -1 2 2 1 1
Approach: Follow the steps below to solve the problem:
- Traverse the array and store the last occurrence of every element in a Map.
- Initialize an array temp[] and store in it for each value, the maximum distance between any pair of consecutive repetitions of it in the array.
- Once the above step is completed, update temp[] by comparing temp[i] with the distance of the last occurrence of i from the end of the array.
- Now, store the minimum comment element for all subarrays of length 1 to N one by one and print them.
Below is the implementation of the above approach:
C++
// C++ Program to implement the// above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum distance// between every two elementvoid max_distance(int a[], int temp[], int n){ // Stores index of last occurrence // of each array element map<int, int> mp; // Initialize temp[] with -1 for (int i = 1; i <= n; i++) { temp[i] = -1; } // Traverse the array for (int i = 0; i < n; i++) { // If array element has // not occurred previously if (mp.find(a[i]) == mp.end()) // Update index in temp temp[a[i]] = i + 1; // Otherwise else // Compare temp[a[i]] with distance // from its previous occurrence and // store the maximum temp[a[i]] = max(temp[a[i]], i - mp[a[i]]); mp[a[i]] = i; } for (int i = 1; i <= n; i++) { // Compare temp[i] with distance // of its last occurrence from the end // of the array and store the maximum if (temp[i] != -1) temp[i] = max(temp[i], n - mp[i]); }}// Function to find the minimum common// element in subarrays of all possible lengthsvoid min_comm_ele(int a[], int ans[], int temp[], int n){ // Function call to find the maximum // distance between every pair of repetition max_distance(a, temp, n); // Initialize ans[] to -1 for (int i = 1; i <= n; i++) { ans[i] = -1; } for (int i = 1; i <= n; i++) { // Check if subarray of length // temp[i] contains i as one // of the common elements if (ans[temp[i]] == -1) ans[temp[i]] = i; } for (int i = 1; i <= n; i++) { // Find the minimum of all // common elements if (i > 1 && ans[i - 1] != -1) { if (ans[i] == -1) ans[i] = ans[i - 1]; else ans[i] = min(ans[i], ans[i - 1]); } cout << ans[i] << " "; }}// Driver Codeint main(){ int N = 6; int a[] = { 1, 3, 4, 5, 6, 7 }; int temp[100], ans[100]; min_comm_ele(a, ans, temp, N); return 0;} |
Java
// Java program to implement the// above approachimport java.util.*;class GFG{ // Function to find maximum distance// between every two elementstatic void max_distance(int a[], int temp[], int n){ // Stores index of last occurrence // of each array element Map<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Initialize temp[] with -1 for(int i = 1; i <= n; i++) { temp[i] = -1; } // Traverse the array for(int i = 0; i < n; i++) { // If array element has // not occurred previously if (mp.get(a[i]) == null) // Update index in temp temp[a[i]] = i + 1; // Otherwise else // Compare temp[a[i]] with distance // from its previous occurrence and // store the maximum temp[a[i]] = Math.max(temp[a[i]], i - mp.getOrDefault(a[i], 0)); mp.put(a[i], i); } for(int i = 1; i <= n; i++) { // Compare temp[i] with distance // of its last occurrence from the end // of the array and store the maximum if (temp[i] != -1) temp[i] = Math.max(temp[i], n - mp.getOrDefault(i, 0)); }}// Function to find the minimum common// element in subarrays of all possible lengthsstatic void min_comm_ele(int a[], int ans[], int temp[], int n){ // Function call to find the maximum // distance between every pair of repetition max_distance(a, temp, n); // Initialize ans[] to -1 for(int i = 1; i <= n; i++) { ans[i] = -1; } for(int i = 1; i <= n; i++) { // Check if subarray of length // temp[i] contains i as one // of the common elements if (temp[i] >= 0 && ans[temp[i]] == -1) ans[temp[i]] = i; } for(int i = 1; i <= n; i++) { // Find the minimum of all // common elements if (i > 1 && ans[i - 1] != -1) { if (ans[i] == -1) ans[i] = ans[i - 1]; else ans[i] = Math.min(ans[i], ans[i - 1]); } System.out.print(ans[i] + " "); }}// Driver Codepublic static void main(String args[]){ int N = 6; int a[] = { 1, 3, 4, 5, 6, 7 }; int []temp = new int[100]; Arrays.fill(temp, 0); int []ans = new int[100]; Arrays.fill(ans, 0); min_comm_ele(a, ans, temp, N);}}// This code is contributed by SURENDRA_GANGWAR |
Python3
# Python3 Program to implement # the above approachdef min_comm_ele(a): n = len(a) seen = {} ans = [-1]*(n+1) temp = {} for i in range(n): # If array element has # not occurred previously if (a[i] not in seen): # Update index in temp temp[a[i]] = i + 1 # Otherwise else: # Compare temp[a[i]] with # distance from its previous # occurrence and store the maximum temp[a[i]] = max(temp[a[i]], i - seen[a[i]]) # Update the latest seen seen[a[i]] = i for i in range(n): # Compare temp[a[i]] with # distance from last occurrence # to the end of the array # and store the maximum if (temp[a[i]] != -1): temp[a[i]] = max(temp[a[i]], n - seen[a[i]]) # We now have a hashmap 'temp' # which contains for all values in A # the smallest size of subarray # for which they will always be visible # ans[i] is the smallest value # visible with subarray size i # We can extract this value # by iterating through temp: for i in temp: if ans[temp[i]] == -1: ans[temp[i]] = i else: ans[temp[i]] = min(ans[temp[i]], i) # If no specific value had # size i as the minimum, # we use the previous subarray's # value (if it exists) for i # If a value is visible in all # subarrays of size n, it must # be visible in subarrays of # size n+1 for i in range(1,n+1): if ans[i] == -1 and ans[i-1] != -1: ans[i] = ans[i-1] # Return the results for 1 to n return ans[1:n+1]# Driver Codeif __name__ == "__main__": a = [1,3,4,5,6,7] res = min_comm_ele(a) for m in res: print(m, end=" ")# This code is contributed by jmcpeak |
C#
// C# program to implement the// above approachusing System;using System.Collections.Generic;class GFG { // Function to find maximum distance // between every two element static void max_distance(int[] a, int[] temp, int n) { // Stores index of last occurrence // of each array element Dictionary<int, int> mp = new Dictionary<int, int>(); // Initialize temp[] with -1 for(int i = 1; i <= n; i++) { temp[i] = -1; } // Traverse the array for(int i = 0; i < n; i++) { // If array element has // not occurred previously if (!mp.ContainsKey(a[i])) // Update index in temp temp[a[i]] = i + 1; // Otherwise else // Compare temp[a[i]] with distance // from its previous occurrence and // store the maximum temp[a[i]] = Math.Max(temp[a[i]], i - mp[a[i]]); if(mp.ContainsKey(a[i])) { mp[a[i]] = i; } else{ mp.Add(a[i], i); } } for(int i = 1; i <= n; i++) { // Compare temp[i] with distance // of its last occurrence from the end // of the array and store the maximum if (temp[i] != -1) { if(mp.ContainsKey(i)) { temp[i] = Math.Max(temp[i], n - mp[i]); } else{ temp[i] = Math.Max(temp[i], n); } } } } // Function to find the minimum common // element in subarrays of all possible lengths static void min_comm_ele(int[] a, int[] ans, int[] temp, int n) { // Function call to find the maximum // distance between every pair of repetition max_distance(a, temp, n); // Initialize ans[] to -1 for(int i = 1; i <= n; i++) { ans[i] = -1; } for(int i = 1; i <= n; i++) { // Check if subarray of length // temp[i] contains i as one // of the common elements if (temp[i] >= 0 && ans[temp[i]] == -1) ans[temp[i]] = i; } for(int i = 1; i <= n; i++) { // Find the minimum of all // common elements if (i > 1 && ans[i - 1] != -1) { if (ans[i] == -1) ans[i] = ans[i - 1]; else ans[i] = Math.Min(ans[i], ans[i - 1]); } Console.Write(ans[i] + " "); } } // Driver code static void Main() { int N = 6; int[] a = { 1, 3, 4, 5, 6, 7 }; int[] temp = new int[100]; Array.Fill(temp, 0); int[] ans = new int[100]; Array.Fill(ans, 0); min_comm_ele(a, ans, temp, N); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script> // JavaScript Program to implement the// above approach// Function to find maximum distance// between every two elementfunction max_distance(a, temp, n){ // Stores index of last occurrence // of each array element var mp = new Map(); // Initialize temp[] with -1 for (var i = 1; i <= n; i++) { temp[i] = -1; } // Traverse the array for (var i = 0; i < n; i++) { // If array element has // not occurred previously if (!mp.has(a[i])) // Update index in temp temp[a[i]] = i + 1; // Otherwise else // Compare temp[a[i]] with distance // from its previous occurrence and // store the maximum temp[a[i]] = Math.max(temp[a[i]], i - mp[a[i]]); mp.set(a[i], i); } for (var i = 1; i <= n; i++) { // Compare temp[i] with distance // of its last occurrence from the end // of the array and store the maximum if (temp[i] != -1) temp[i] = Math.max(temp[i], n - mp.get(i)); }}// Function to find the minimum common// element in subarrays of all possible lengthsfunction min_comm_ele(a, ans, temp, n){ // Function call to find the maximum // distance between every pair of repetition max_distance(a, temp, n); // Initialize ans[] to -1 for (var i = 1; i <= n; i++) { ans[i] = -1; } for (var i = 1; i <= n; i++) { // Check if subarray of length // temp[i] contains i as one // of the common elements if (ans[temp[i]] == -1) ans[temp[i]] = i; } for (var i = 1; i <= n; i++) { // Find the minimum of all // common elements if (i > 1 && ans[i - 1] != -1) { if (ans[i] == -1) ans[i] = ans[i - 1]; else ans[i] = Math.min(ans[i], ans[i - 1]); } document.write( ans[i] + " "); }}// Driver Codevar N = 6;var a = [1, 3, 4, 5, 6, 7];var temp = new Array(100), ans = Array(100);min_comm_ele(a, ans, temp, N);</script> |
Output
-1 -1 -1 4 3 1
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
