Find Repeating Element in Array| Leetcode #287

This article will discuss various approaches to find the element repeating more than once in an array, from naive to most efficient.

Problem statement: Given an array of size n where each element is in the range [1,n-1], exactly one element repeats any no. of times in the array. Find that repeating element.

Input: arr = {1, 3, 4, 2, 4, 3, 3}
Output: 3
Input: arr = {1,1}
Output: 1

Brute Force approach: Find Repeating Element in Array

This is the brute force approach where we compare every possible pair of the elements in the array using two for loops. And once we get a pair with equal elements, we break the loop and print the corresponding element. Note that at least once this condition will be true, as there is exactly one element repeating at least one time. Below is the C++ implementation to find repeating element in Array using Brute Force.

//Brute force approch to find repeating element in array
for(int i =0;i<n;i++)
{ 
  for(int j = i+1; j<n; j++)
    {
      if(arr[i] == arr[j])
           return arr[i];
    }
}

Naive: Find Repeating Element in Array by sorting

How about sorting? We can optimize the solution by first sorting the elements. This will result in the same elements occurring together. Then we can simply traverse the array and compare each element with its right neighbour i.e. check for every index i,  if A[i]==A[i+1]. Once the condition is satisfied, return the corresponding element.

// Sort the array using any sorting algorithm
// After sorting compare each element with its right neighbour
for( int i = 0; i < n-1; i++)
{
   if(arr[i] == arr[i+1])
	  return arr[i];
}

Time complexity: O(n log n) time, as we have to sort the array and then traverse once.
Auxiliary space: O(1). 

Efficient approach: Find Repeating Element in Array using Visited array

As all the elements are positive we can use the hash map technique or array to keep a record of the visited element, by using a boolean array=” Visited”. We traverse the array and make the corresponding visited index true. Once we approach an element whose corresponding Visited flag is already true, this means that this element is the repeated one. The implementation is shown below.

// Create a boolean array of size n
bool Visited[n] = {F, F, F, F, F, F}
for(int i = 0;i < n;i++)
{
 if(visited (arr[i])
   return arr[i];
 Visited arr[i]= true;
}

Time complexity: O(n) time, as single traversal is needed.
Auxiliary space: O(n). As we use extra space for storing visited flag for each element.
Though we largely optimized the solution from O(n²) to O(n) time complexity. But the drawback is that it requires O(n) auxiliary space. What if u are required to use only O(1) space complexity ?? Solution exist for that also!!

Most efficient:  Find Repeating Element in Array using two pointer approach

We use the idea of two pointer approach, similar to slow and fast pointer for cycle detection in a linked list . As the elements are in the range 1 to n-1 and the size of the array is n. We can use indexes for pointing to the next element. We will traverse the array from left to right using slow and fast pointer. Where  slow pointer takes 1 step and fast pointer takes 2 steps at a time.

The solution consists of two phases. In the first phase, we initialize the slow and fast pointer as the first element and traverse the slow and fast pointer according to their steps until slow pointer is not equal to the fast pointer.  In this phase, we get the meeting point of both the pointer as the cycle will always exist.

In the second phase, we using this meeting point to find the duplicate element. When the slow and fast pointer collide in the previous phase, we stop and place the slow pointer to the first element. To get the duplicate element, we traverse once again the array, but this time changing the initial position and steps at a time will move both the pointers equally as slow = arr[slow] and fast = arr[fast]. The element at which the pointer collides will be the repeating element in the array. Below is the C++ Implementation to find repeating element in an array. The same logic can be applied to other languages as well.
 

// Two pointer approach to find repeating element in array
int findRepeating(int arr[ ], int n )
{          
    //first phase to get the initial meeting point of slow and fast pointer
	int slow = arr[0], fast = arr[0];
 	do
    {
         slow = arr[slow]; // update slow pointer by 1 step
         fast = arr[arr[fast]];  // update fast pointer by 2 step
    }
    while(slow!= fast)

    //second phase to get the duplicate element
    slow = arr[0]; //update slow pointer to first position
    while(slow != fast)
    {    
        //move both the pointer by 1 step
	    slow = arr[slow];
	    fast = arr[fast];
    }

    return slow; // the duplicate element
}

Dry run on input : Arr= {1, 3, 2, 4, 6, 5, 7, 3}

• (1st phase) Initialize slow = arr[0]= 1, fast = arr[0];
• Iteration 1: slow =  arr[0]= 1,  arr[0]=fast = 1
• Iteration 2: slow =  arr[1]=3, fast = arr[arr[1]]= 4
• Iteration 3: slow =  arr[3]= 4, fast = arr[arr[4]]= 7
• Iteration 4: slow =  arr[4]= 6, fast =  arr[arr[7]]= 4
• Iteration 5: slow =  arr[6]= 7, fast =  arr[arr[4]]= 7

• (2nd phase) slow pointer placed  to first element : slow = 1 and fast pointer position from previous phase : fast = 7. Update till slow != fast.
• Iteration 1: slow = arr[1]= 3, fast = arr[7]= 3. 
• Return slow = 3 (which is the element repeating in the array).

Time complexity: O(n). As we linearly traverse the array.
Auxiliary space: O(1). As we use constant space.

Solve the problem here: https://leetcode.com/problems/find-the-duplicate-number/
Check out similar articles: maximum-sum-circular-subarray-leetcode-918