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 notstring 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 Codeint 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 approachimport 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 notdef 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 Codearr = [2, 4, 5, 5, 3, 5];N = len(arr)# Function Callprint(checkContiguous(arr, N));# This code is contributed by Saurabh Jaiswal |
C#
// C# code for the above approachusing 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
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!
… [Trackback]
[…] Info to that Topic: geeksforgeeks.org/check-if-all-duplicate-elements-in-the-array-are-adjacent-or-not/ […]