in ,

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 occuring 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

#include

using namespace std;

  

string checkContiguous(int* arr, int& n)

{

    int i;

  

    

    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";

}

  

int main()

{

    int arr[] = { 2, 4, 5, 5, 3, 5 };

    int N = sizeof(arr) / sizeof(arr[0]);

  

    

    cout << checkContiguous(arr, N);

  

    return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(N)

What do you think?

Silver 1

Written by yulica

Leave a Reply

Your email address will not be published.

      Android vs iOS Development: Pros and Cons of Each Platform_61d8c364a6197.jpeg

      Android vs iOS Development: Pros and Cons of Each Platform

      Mobile App Development Trends for 2020_61d8c2bb8874c.jpeg

      Mobile App Development Trends for 2020