Given an array arr[] consisting of N integers, the task is to check if all subarrays of the array have at least one unique element in it or not. If found to be true, then print “Yes”. Otherwise, print “No”.
Examples:
Input: arr[] = {1, 2, 1}
Output: Yes
Explanation:
For Subarrays of size 1: {1}, {2}, {1}, the condition will always be true.
For Subarrays of size 2: {1, 2}, {2, 1}, each subarray has at least one unique element.
For Subarrays of size 3 = {1, 2, 1}, in this subarray we have 2 as the only unique element.
Since each subarray has at least one unique element, print “Yes”.Input: arr[] = {1, 2, 3, 1, 2, 3}
Output: No
Explanation:
Subarrays of size 6: {1, 2, 3, 1, 2, 3} contains no unique element. Therefore, print “No”.
Naive Approach: The simplest approach is to generate all subarrays and use HashMap for each subarray to store the frequency of each element of that subarray. If any subarray does not have at least one unique element, then print “No”. Otherwise, print “Yes”.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include<bits/stdc++.h> using namespace std; // Function to check if all subarrays // of array have at least one unique element string check(int arr[], int n) { // Stores frequency of subarray // elements map<int, int> hm; // Generate all subarrays for(int i = 0; i < n; i++) { // Insert first element in map hm[arr[i]] = 1; for(int j = i + 1; j < n; j++) { // Update frequency of current // subarray in the HashMap hm[arr[j]]++; bool flag = false; // Check if at least one element // occurs once in current subarray for(auto x : hm) { if (x.second == 1) { flag = true; break; } } // If any subarray doesn't // have unique element if (!flag) return "No"; } // Clear map for next subarray hm.clear(); } // Return Yes if all subarray // having at least 1 unique element return "Yes"; } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 2, 1 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call cout << check(arr, N); } // This code is contributed by bgangwar59 |
Java
// Java program for above approach import java.util.*; import java.lang.*; class GFG { // Function to check if all subarrays // of array have at least one unique element static String check(int arr[], int n) { // Stores frequency of subarray // elements Map<Integer, Integer> hm = new HashMap<>(); // Generate all subarrays for (int i = 0; i < n; i++) { // Insert first element in map hm.put(arr[i], 1); for (int j = i + 1; j < n; j++) { // Update frequency of current // subarray in the HashMap hm.put( arr[j], hm.getOrDefault(arr[j], 0) + 1); boolean flag = false; // Check if at least one element // occurs once in current subarray for (Integer k : hm.values()) { if (k == 1) { flag = true; break; } } // If any subarray doesn't // have unique element if (!flag) return "No"; } // Clear map for next subarray hm.clear(); } // Return Yes if all subarray // having at least 1 unique element return "Yes"; } // Driver Code public static void main(String[] args) { // Given array arr[] int[] arr = { 1, 2, 1 }; int N = arr.length; // Function Call System.out.println(check(arr, N)); } } |
Python3
# Python3 program for # the above approach from collections import defaultdict # Function to check if # all subarrays of array # have at least one unique # element def check(arr, n): # Stores frequency of # subarray elements hm = defaultdict (int) # Generate all subarrays for i in range(n): # Insert first element # in map hm[arr[i]] += 1 for j in range(i + 1, n): # Update frequency of # current subarray in # the HashMap hm[arr[j]] += 1 flag = False # Check if at least one # element occurs once in # current subarray for k in hm.values(): if (k == 1): flag = True break # If any subarray doesn't # have unique element if (not flag): return "No" # Clear map for next # subarray hm.clear() # Return Yes if all # subarray having at # least 1 unique element return "Yes" # Driver Code if __name__ == "__main__": # Given array arr[] arr = [1, 2, 1] N = len(arr) # Function Call print(check(arr, N)) # This code is contributed by Chitranayal |
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG{ // Function to check if all // subarrays of array have at // least one unique element static String check(int []arr, int n) { // Stores frequency of // subarray elements Dictionary<int, int> hm = new Dictionary<int, int>(); // Generate all subarrays for (int i = 0; i < n; i++) { // Insert first element // in map hm.Add(arr[i], 1); for (int j = i + 1; j < n; j++) { // Update frequency of current // subarray in the Dictionary if(hm.ContainsKey(arr[j])) hm[arr[j]]++; else hm.Add(arr[j], 1); bool flag = false; // Check if at least one // element occurs once // in current subarray foreach (int k in hm.Values) { if (k == 1) { flag = true; break; } } // If any subarray doesn't // have unique element if (!flag) return "No"; } // Clear map for next // subarray hm.Clear(); } // Return Yes if all subarray // having at least 1 unique // element return "Yes"; } // Driver Code public static void Main(String[] args) { // Given array []arr int[] arr = {1, 2, 1}; int N = arr.Length; // Function Call Console.WriteLine(check(arr, N)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program for above approach // Function to check if all subarrays // of array have at least one unique element function check(arr, n) { // Stores frequency of subarray // elements var hm = new Map(); // Generate all subarrays for(var i = 0; i < n; i++) { // Insert first element in map hm.set(arr[i], 1); for(var j = i + 1; j < n; j++) { // Update frequency of current // subarray in the HashMap if(hm.has(arr[j])) hm.set(arr[j], hm.get(arr[j])+1); else hm.set(arr[j], 1) var flag = false; // Check if at least one element // occurs once in current subarray hm.forEach((value, key) => { if (value == 1) { flag = true; } }); // If any subarray doesn't // have unique element if (!flag) return "No"; } // Clear map for next subarray hm = new Map(); } // Return Yes if all subarray // having at least 1 unique element return "Yes"; } // Driver Code // Given array arr[] var arr = [1, 2, 1]; var N = arr.length; // Function Call document.write( check(arr, N)); </script> |
Output
Yes
Time Complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach: Follow the steps below to optimize the above approach:
- Iterate a loop over the range [0, N – 1] and create a map to store the frequency of each character present in the current subarray.
- Create a variable count to check that subarray has at least one element with frequency 1 or not.
- Traverse the array arr[] and update the frequency of each element in the map and update the count as:
- If the frequency of element is 1 then increment the count.
- If the frequency of element is 2 then decrement the count.
- In the above steps, if the value of count is 0, then print “No” as there exists a subarray who doesn’t have any unique element in it.
- After all the iteration if the value of count is always positive, then print “Yes”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include<bits/stdc++.h> using namespace std; // Function to check if all subarrays // have at least one unique element string check(int arr[], int n) { // Generate all subarray for(int i = 0; i < n; i++) { // Store frequency of // subarray's elements map<int, int> hm; int count = 0; // Traverse the array over // the range [i, N] for(int j = i; j < n; j++) { // Update frequency of // current subarray in map hm[arr[j]]++; // Increment count if (hm[arr[j]] == 1) count++; // Decrement count if (hm[arr[j]] == 2) count--; if (count == 0) return "No"; } } // If all subarrays have at // least 1 unique element return "Yes"; } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 2, 1 }; int N = sizeof(arr) / sizeof(arr[0]); // Function Call cout << check(arr, N); } // This code is contributed by SURENDRA_GANGWAR |
Java
// Java program for the above approach import java.util.*; import java.lang.*; class GFG { // Function to check if all subarrays // have at least one unique element static String check(int arr[], int n) { // Generate all subarray for (int i = 0; i < n; i++) { // Store frequency of // subarray's elements Map<Integer, Integer> hm = new HashMap<>(); int count = 0; // Traverse the array over // the range [i, N] for (int j = i; j < n; j++) { // Update frequency of // current subarray in map hm.put(arr[j], hm.getOrDefault(arr[j], 0) + 1); // Increment count if (hm.get(arr[j]) == 1) count++; // Decrement count if (hm.get(arr[j]) == 2) count--; if (count == 0) return "No"; } } // If all subarrays have at // least 1 unique element return "Yes"; } // Driver Code public static void main(String[] args) { // Given array arr[] int[] arr = { 1, 2, 1 }; int N = arr.length; // Function Call System.out.println(check(arr, N)); } } |
Python3
# Python3 program for the above approach # Function to check if all subarrays # have at least one unique element def check(arr, n): # Generate all subarray for i in range(n): # Store frequency of # subarray's elements hm = {} count = 0 # Traverse the array over # the range [i, N] for j in range(i, n): # Update frequency of # current subarray in map hm[arr[j]] = hm.get(arr[j], 0) + 1 # Increment count if (hm[arr[j]] == 1): count += 1 # Decrement count if (hm[arr[j]] == 2): count -= 1 if (count == 0): return "No" # If all subarrays have at # least 1 unique element return "Yes" # Driver Code if __name__ == '__main__': # Given array arr[] arr = [ 1, 2, 1 ] N = len(arr) # Function Call print(check(arr, N)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG { // Function to check if all // subarrays have at least // one unique element static String check(int []arr, int n) { // Generate all subarray for (int i = 0; i < n; i++) { // Store frequency of // subarray's elements Dictionary<int, int> hm = new Dictionary<int, int>(); int count = 0; // Traverse the array over // the range [i, N] for (int j = i; j < n; j++) { // Update frequency of // current subarray in map if(hm.ContainsKey((arr[j]))) hm[arr[j]]++; else hm.Add(arr[j], 1); // Increment count if (hm[arr[j]] == 1) count++; // Decrement count if (hm[arr[j]] == 2) count--; if (count == 0) return "No"; } } // If all subarrays have at // least 1 unique element return "Yes"; } // Driver Code public static void Main(String[] args) { // Given array []arr int[] arr = {1, 2, 1}; int N = arr.Length; // Function Call Console.WriteLine(check(arr, N)); } } // This code is contributed by gauravrajput1 |
Javascript
<script> //Javascript program for the above approach // Function to check if all subarrays // have at least one unique element function check(arr, n) { // Generate all subarray for(var i = 0; i < n; i++) { // Store frequency of // subarray's elements //map<int, int> hm; var hm= new Map(); var count = 0; // Traverse the array over // the range [i, N] for(var j = i; j < n; j++) { // Update frequency of // current subarray in map //hm[arr[j]]++; if(hm.has(arr[j])) hm.set(arr[j], hm.get(arr[j])+1) else hm.set(arr[j], 1) // Increment count if (hm.get(arr[j])==1) count++; // Decrement count if (hm.get(arr[j]) == 2) count--; if (count == 0) return "No"; } } // If all subarrays have at // least 1 unique element return "Yes"; } var arr = [ 1, 2, 1 ]; var N = arr.length; // Function Call document.write(check(arr, N)); // This code is contributed by SoumikMondal </script> |
Output
Yes
Time Complexity: O(N2)
Auxiliary Space: O(N)
Related Topic: Subarrays, Subsequences, and Subsets in Array
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!
