Check if all duplicate elements in the Array are adjacent or not
Given an array arr[]. The task is to check whether duplicate elements in arr[] are contiguous or not.
Examples:
Input: arr[] = {1, 2, 3, 4, 5, 6} Output: Yes Explanation: There is no duplicate element in arr[] so there is no need to check anything and answer is Yes.
Input: arr[] = {1, 2, 2, 4} Output: Yes Explanation: 2 is occurring 2 times and it is contiguous. Hence, answer is Yes. Input: arr[] = {1, 2, 3, 2, 4} Output: No Explanation: There is a gap between 2's and 3 is between two 2's. Therefore, the answer is No.
Approach:
This problem can be solved by using HashMaps. Follow the steps below to solve the given problem.
- Use maps to store the visited elements.
- First, mark the first element on the map.
- Traverse the array arr[] from 1 to N-1. where N is the size of arr[].
- If the current element matches the previous element means there is a cycle of one element repeating so simply continue the loop.
- If the current element is already marked in the map return “No”.
- Mark the current element in the map.
- If the function reaches here means there are all contiguous elements so return “Yes”.
Below is the implementation of the above approach.
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check whether duplicate // elements in array arr[] are contiguous or not string checkContiguous( int * arr, int & n) { int i; // Map to keep track of elements unordered_map< int , bool > visited; visited.clear(); visited.insert({ arr[0], 1 }); for (i = 1; i < n; i++) { if (arr[i] == arr[i - 1]) continue ; else if (visited[arr[i]]) return "No" ; visited[arr[i]] = 1; } return "Yes" ; } // Driver Code int main() { int arr[] = { 2, 4, 5, 5, 3, 5 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call cout << checkContiguous(arr, N); return 0; } |
Java
// Java code for the above approach import java.io.*; class GFG { // Function to check whether duplicate // elements in array arr[] are contiguous or not static String checkContiguous( int [] arr, int n) { int i; // Map to keep track of elements int [] visited = new int [n]; for (i = 1 ; i < n; i++) { if (arr[i] == arr[i - 1 ]) continue ; else if (visited[arr[i]] == 0 ) return "No" ; visited[arr[i]] = 1 ; } return "Yes" ; } // Driver Code public static void main(String[] args) { int arr[] = { 2 , 4 , 5 , 5 , 3 , 5 }; int N = arr.length; // Function Call System.out.println(checkContiguous(arr, N)); } } // This code is contributed by Potta Lokesh |
Python3
# Python program for the above approach # Function to check whether duplicate # elements in array arr[] are contiguous or not def checkContiguous (arr, n): i = None # Map to keep track of elements visited = [ 0 ] * n; for i in range ( 1 , n): if (arr[i] = = arr[i - 1 ]): continue ; elif (visited[arr[i]] = = 0 ): return "No" ; visited[arr[i]] = 1 ; return "Yes" ; # Driver Code arr = [ 2 , 4 , 5 , 5 , 3 , 5 ]; N = len (arr) # Function Call print (checkContiguous(arr, N)); # This code is contributed by Saurabh Jaiswal |
C#
// C# code for the above approach using System; class GFG { // Function to check whether duplicate // elements in array arr[] are contiguous or not static String checkContiguous( int [] arr, int n) { int i; // Map to keep track of elements int [] visited = new int [n]; for (i = 1; i < n; i++) { if (arr[i] == arr[i - 1]) continue ; else if (visited[arr[i]] == 0) return "No" ; visited[arr[i]] = 1; } return "Yes" ; } // Driver Code public static void Main() { int [] arr = { 2, 4, 5, 5, 3, 5 }; int N = arr.Length; // Function Call Console.WriteLine(checkContiguous(arr, N)); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript program for the above approach // Function to check whether duplicate // elements in array arr[] are contiguous or not const checkContiguous = (arr, n) => { let i; // Map to keep track of elements let visited = {}; visited[arr[0]] = 1; for (i = 1; i < n; i++) { if (arr[i] == arr[i - 1]) continue ; else if (visited[arr[i]]) return "No" ; visited[arr[i]] = 1; } return "Yes" ; } // Driver Code let arr = [2, 4, 5, 5, 3, 5]; let N = arr.length; // Function Call document.write(checkContiguous(arr, N)); // This code is contributed by rakeshsahni </script> |
Output
No
Time Complexity: O(N) // only one traversal of the array is required
Auxiliary Space: O(N) //unordered map takes space equal to the length of the array N
Contact Us