How to detect repeated elements in an integer array?

This is an open ended question so please ask questions about the nature of the data in the array (size of the data, is it sorted or almost sorted, range of the data). Also, ask about any constraints like runtime or memory usage. You selection of the technique will depend on the answers to those questions. I have listed a few techniques below that touch on some of those points. There are more solutions that may be appropriate under different conditions. Feel free to suggest them in the comments.

• Sort the array in-place and loop through to find the duplicate number

          Runtime: O(n log n) for sorting + O(n)
          Pros: no extra memory
          Cons: extra pass over the array is needed to actually find the duplicate
          Code(C#):

  using System;
  using System.Collections.Generic;
  namespace ArrayQuestions.FindDuplicateNumber
  {
    class Program
    {
        static void Main(string[] args)
        {
            int[] array = new int[]{3, 2, 4, 5, 3, 2, 9, 6, 3, 6, 9, 9, 9};
            Array.Sort(array); 

            // note: this is a O(n square) sort but one could use a O(n log n) 

            // sort easily.
            // expected output: 2, 2, 3, 3, 3, 4, 5, 6, 6, 9, 9, 9, 9

            for(int i=0; i< array.Length - 1;)
            {
               int count = 1;
               while(i < array.Length - 1 && array[i] == array[++i])
               {
                  count++;   
               }
               if(count > 1)

                  Console.WriteLine("{0} occurs {1} times", array[i-1], count);
            }

            Console.ReadLine();
        }
     }
  }

Perform custom in-place insertion sort and check for duplicates during the inserts

          Runtime: O(n square). This is worst case but in practice it could be much lower (close to O(n)
                        for almost sorted input)
          Pros: No extra pass need
          Cons: It has the potential to be really slow for large inputs or sets that are not almost sorted.

• Use a hash table to remember the numbers encountered so far. Collision during insertion signals a duplicate.

          Runtime: O(n) (This is assuming insert and lookup operations on the hashtable are truly O(1))
          Pros: fast
          Cons: potentially high memory usage for hash table
          Code(C#)

    using System;
    using System.Collections.Generic;
    using System.Collections;
    namespace ArrayQuestions.FindDuplicateNumber
    {
        class Program
        {
            static void Main(string[] args)
            {
                int[] array = new int[]{3, 2, 4, 5, 3, 2, 9, 6, 3, 6, 9, 9, 9};
                Dictionary dictionary = new Dictionary();

                for (int i = 0; i < array.Length; i++)
                {
                    if (dictionary.ContainsKey(array[i]))
                        dictionary[array[i]]++;
                    else
                        dictionary.Add(array[i], 1);
                }

                foreach (var entry in dictionary)
                {
                    Console.WriteLine("{0} occurs {1} times", entry.Key, entry.Value);
                }
            }

        }
    }

• Use a bit-vector to remember the number encountered so far.

           Runtime: O(n)
           Pro: fast, compact bit vector reduces memory usage
           Cons:
                 1. Additional memory is needed for the bit vector
2. Initializing bit vector will add add to the runtime time
                 3. Slightly complex implementation if one has to  implement the bit-vector code itself.
           Pseudo Code:
             1. Initialize the bit-vector to all 0s.
             2. Loop through the array and for each number check the corresponding bit in the bit-vector.
                 If the bit is already set it signals a duplicate. If bit is not set, set the bit and continue.

Reverse Minesweeper

Question: The interviewer first discussed the game of minesweeper and the gave a reverse minesweeper problem where the specifications were as follows:
1. A block of M rows by N columns is given
2. Each item can either be a mine or not a mine
3. The location of the mines in the block is given by the character *
4. Normal/safe squares are marked by '.' (dots)

See the below table and write a program to print the number of mines adjacent to the safe blocks.

Update: This problem is from the book "Programming Challenges - The Programming Contest Training Manual - Skiena".

Example:

input	output
4 4	Field #1:
*...	*100
....	2210
.*..	1*10
....	1110
3 5	Field #2:
**...	**100
.....	33200
.*...	1*100
6 5	Field #3:
.*.*.	2*3*2
*.*.*	*3*3*
.....	35453
*****	*****
.*.*.	3*5*3
.....	11211
1 1	Field #4:
.	0
1 1	Field #5:
*	*
2 2	Field #6:
*.	*2
.*	2*
0 0

Program:

#include <stdio.h>
#include <malloc.h>
#define MINE -1

void Read_Arrays();
void FillNumbers(int * array, int rows, int cols);
void UpdateNeighbors(int *array, int row_index, int col_index, int max_row, int max_col);
void print_array(int *array, int rows, int cols);

int get_val(int *array, int row_index, int col_index, int cols);
// increment the value at the specified array location
int inc_val(int *array, int row_index, int col_index, int cols);

int main(void)
{
        Read_Arrays();
}
void Read_Arrays()
{
        int rows = 0;
        int cols = 0;

        int cur_row_index;

        int *array;

        char line[256];
        int field_num = 0;

        while(fgets(line, 256, stdin) != NULL)
        {
                int i=0;
                if(rows == 0 && cols == 0)
                {
                        sscanf(line, "%d %d", &rows, &cols);
                        array = (int *)malloc(rows*cols*sizeof(int));

                        if(array == NULL)
                        {
                                printf("failed to allocate memory\n");
                                return;
                        }
                        if(rows == 0 || cols == 0)
                        {
                                return;
                        }
                        cur_row_index = 0;
                        continue;
                }

                for(i= 0; i<cols; i++)
                {
                        char c = line[i];
                        if(c == '*')
                                c = MINE;
                        else
                                c = 0;
                        *(array + (cur_row_index*cols)+i) = c;
                }

                //if we scanned the specified number of rows lets process the array
                if(cur_row_index == rows - 1)
                {
                        FillNumbers(array, rows, cols);
                        printf("Field #%d:\n", ++field_num);
                        print_array(array, rows, cols);
                        free(array);
                        rows = 0;
                        cols = 0;
                }
                else
                {
                        cur_row_index++;
                }

        }
}

/* fill numbers in the array instead of dots */
void FillNumbers(int *array, int rows, int cols)
{
        int i, j;
        for(i=0; i<rows; i++)
        {
                for(j=0; j < cols; j++)
                {
                        if(*(array + (i*cols) + j) == MINE)
                        {
                                UpdateNeighbors(array, i, j, rows, cols);
                        }
                }
        }
}

/* this function will increment mine count for the neighbors of the mine */
void UpdateNeighbors(int *array, int row_index, int col_index, int max_row, int max_col)
{
        if(row_index-1 >= 0)
        {
                if(col_index - 1 >= 0)
                        inc_val(array, row_index - 1, col_index -1, max_col);
                inc_val(array, row_index -1, col_index, max_col);
                if(col_index + 1 < max_col)
                        inc_val(array, row_index -1, col_index + 1, max_col);
        }

        if(col_index - 1 >= 0)
                inc_val(array, row_index, col_index - 1, max_col);
        if(col_index + 1 < max_col)
                inc_val(array, row_index, col_index + 1, max_col);

        if(row_index + 1 < max_row)
        {
                if(col_index - 1 >= 0)
                        inc_val(array, row_index + 1, col_index -1, max_col);
                inc_val(array, row_index + 1, col_index, max_col);
                if(col_index + 1 < max_col)
                        inc_val(array, row_index + 1, col_index+1, max_col);
        }
}

int get_val(int *array, int row_index, int col_index, int cols)
{
        return  *(array + (row_index * cols) + col_index);
}
/* we increment only if there is no mine present at the specified location */
int inc_val(int *array, int row_index, int col_index, int cols)
{
        int val = get_val(array, row_index, col_index, cols);
        if(val == MINE) return;
        *(array + (row_index * cols) + col_index) += 1;
}

void print_array(int *array, int rows, int cols)
{
        int i, j;
        for(i = 0; i < rows; i++)
        {
                for(j = 0; j < cols; j++)
                {
                        int val = get_val(array, i, j, cols);
                        if(val != MINE)
                                printf("%d", val);
                        else
                                printf("%c", '*');
                }
                printf("\n");
        }
}

Find an Item in a Sorted Array with Shifted Elements

Problem: You are given a sorted array with shifted elements. Elements can be shifted to the left or right by 'i' number of places. The sign of 'i' denotes the direction of the shift. For positive 'i' direction of shift is right and left for negative 'i'.

For example, consider the sorted array 2, 3, 4, 8, 10, 11. A shift of 3 places to the right would be denoted by i=2 and the shifted array would look like this: 10, 11, 2, 3, 4, 8,

For i=-2, the shifted array would look like: 4, 8, 10, 11, 2, 3.



Write code to find if a given number is present in this array.

Solution: The brute force method to search all elements in the array would yield an O(n) solution, so obviously that's not the best approach. We are not leveraging the sorted nature of the array in this case.

Now, how can we leverage the sorted nature of the array? Let assume that 'i' was 0. In that case the array would be sorted and not shifted at all (0 shift). Whats the fastest way to search in a sorted array? Binary Search! We can split the array in 2 halves and do a recursive search in one of the halves until we find the number we are looking for ( or not, if its not in the array ). This approach has a running time of O(log n), which is obviously better than n.

But, the fact that the array is shifted by 'i' number of elements complicates things a little bit. Now, instead of splitting the array in equal halves, we split the array at the shift index and do a recursive binary search. There are issues we need to tackle when the shift is greater than the length of the array or if the shift is negative. I guess the code below will make much more sense than my description of the solution.

Code: We will assume that we are provided with a method below that does binary search for us and won't bother implementing it here.

// myArray is the input array
// startIndex and endIndex are the indexes in the 
// array where the binary search starts and ends
// The method returns the index of the searchVal 
// if found in the array, else it returns -1

int BinarySearch(int[] myArray, int startIndex, int endIndex, int searchVal);


// this method will return the index of the searchVal 
// if found, else it return -1
int SearchElement(int[] myArray, int shift, int searchVal)
{
   // to take care of scenarios where the shift is more 
   // than the length of the array
   shift = shift % myArray.Length; 
   
   // -ve shift can be seen as positive shift equal to 
   // the length of the array - ( -ve shift) 
   if (shift < 0)
       shift = myArray.Length + shift;

   if(myArray[shift] <= searchVal &&  
      myArray[myArray.Length - 1] >= searchVal)
   {
      return BinarySearch(myArray, shift, myArray.Length - 1, searchVal);
   }
   else if(myArray[0] <= searchVal && 
           myArray[shift - 1] >= searchVal)
   {
      return BinarySearch(myArray, 0, shift-1, searchVal);
   }
   return -1;
}

Array: Find the number with odd number of occurrences

Problem: You are given an array containing positive integers. All the integers occur even number of times except one. Find this special integer.

Solution: A naive approach would be to loop over the elements of the given array and keep a count of each integer in a hash table or another counter array. But, this quickly becomes unfeasible as the range of integers could be 2^31 (one less). This is an O(n) solution that takes at memory O(range(n)).

The next approach is to sort the array and then loop on it counting occurrences of the integers. When there is a change in the integer we check its count to see if its odd or even. If its odd we have found our special integer. This is an O(n log n) solution that uses constant memory.

Lets try to see if we can use the property that there is one number that occurs odd number of times and every other number occurs even number of times. Since an even number is divisible by 2, you could think of the even occurrences as being present in pairs. The integer with the odd number of occurrences will have 0 or more pairs and one single number. So, if we could some how get rid of all the pairs then all we'd be left with is the single number. Now, what gets rid of pairs? Hint: think of an operator.

XOR will do the trick. Its gives you O(n) solution with no extra memory.

Ex: 3,5,3,2,2

 011  -- 3
^101  -- 5
----------
 110
^011  -- 3
----------
 101
^010  -- 2
----------
 111
^010  -- 2
----------
 101  -- 5 (special one)

Code:

//
// will return the number with odd number of occurrences
// will return 0 if all numbers occur even number of times
//
int GetSpecialOne(int[] array, int length)
{
   int specialOne = array[0];
   
   for(int i=1; i < length; i++)
   {
      specialOne ^= array[i];
   }
   return specialOne;
}

Merge 2 Sorted Arrays (one has empty slots)

Question: There are two sorted arrays A1 and A2. Array A1 is full where as array A2 is partially empty and number of empty slots are just enough to accommodate all elements of A1. Write a program to merge the two sorted arrays to fill the array A2. You cannot use any additional memory and expected run time is O(n).

Solution: The trick to solving this problem is to start filling the destination array from the back with the largest elements. You will end up with a merged and sorted destination array.



Code (C#):

// A1 and A2 are two sorted arrays. 
// A2 is not completely full (has empty slots at the end and are exactly the 
// size of A1)
// the goal is to merge the two arrays in a sorted fashion

void Merge(int[] A1, int[] A2)
{
   int count = FindCount(A2); // get the count of full slots
   int i = A1.Length - 1;
   int j = count - 1;
   int k = A2.Length - 1;

   for(;k>=0;k--)
   {
      if(A1[i] > A2[j] || j < 0)
      {
         A2[k] =A1[i];
         i--;
      }
      else
      {
         A2[k] = A2[j];
         j--;
      }
   }
}

Function to perform Binary Search on a Sorted Array

Problem: Write a function to perform a binary search on a Sorted Array.

Solution: The recursive solution below runs in O(log(n)) because the problem size is halved with each recursive call.

// returns the index of the target element if found, else returns -1
        static int Binary_Search(int[] arr, int start, int end, int target)
        {
           int medianIndex = (end - start) /2 + start;
           int medianValue = arr[medianIndex];

           if(start == end && arr[start] != target)
               return -1;
           if (medianValue == target)
               return medianIndex;
           else if (medianValue < target)
               return Binary_Search(arr, medianIndex + 1, end, target);
           else
               return Binary_Search(arr, start, medianIndex - 1, target);
        }