How to Find Index of a Duplicate in An Array (Java)

Tags: , , , ,



For this programming assignment, we are supposed to find the index of a duplicate in this array for one row of a sudoku puzzle. I have this method, static boolean equals(int[] a, int[] a2):

boolean isValue = true;
int[] dataRow = { 9, 8, 7,  6, 5, 4,  3, 2, 8 }; 
int[]     chk = { 9, 8, 7,  6, 5, 4,  3, 1, 8 };
isValue = Arrays.equals(dataRow, chk);
int i, j;

for (i = 0; i < dataRow.length; i++) 
     {
     for (j = 0; j < dataRow.length; j++) 
        {
        if (dataRow[i] == dataRow[j]) 
           {
           System.out.println("Duplicate - " + dataRow[i] + " found at index " + i + " and " + j);
           //--8 found at index 8 and 1

This program right here simply prints out this: Duplicate - 9 found at index 0 and 0 which means that no duplicate is found. I commented that 8 is found at index 8 and 1. I’m just not sure how to print out where the duplicate was found. I tried modifying the if statement, but that didn’t work: if (dataRow[i] != chk[j]), if (dataRow[i] == chk[i]). I also tried putting the nested for loop into a while loop: while (!isValue), but that didn’t work either. I think my professor also wants to make sure all the values in the array are between 1-9, and my idea is something like this: while (!isValue && (dataRow >= 1 && dataRow <= 9)), but I’m not sure if that will work. I appreciate any help you guys can give me.

Answer

As you have a limited range of values [1..9] in the input array, you could create a small check array to count how many times a digit occurs in the input array, thus detecting duplicates and missing values:

public static void checkForDuplicateAndMissing(int... arr) {
    System.out.println("Input: " + Arrays.toString(arr));
    int[] check = new int[10]; // populated with 0

    boolean noDuplicates = true;  
    for (int i = 0; i < arr.length; i++) {
        int d = arr[i];
        if (check[d] != 0) {
            System.out.printf("Duplicate value %d found at index %d%n", d, i);
            noDuplicates = false;
        }
        check[d]++;
    }
    if (noDuplicates) {
        System.out.println("No duplicates found in the input array");
    }
  
    boolean allFound = true;
    for (int i = 1; i < check.length; i++) {  // skipping 0 as it's not in range [1..9]
        if (check[i] == 0) {
            System.out.println("Missing value: " + i);
            allFound = false;
        }
    }
    if (allFound) {
        System.out.println("All digits present in the input array");
    }
    System.out.println("-------n");
}

Test:

checkForDuplicateAndMissing(9, 8, 7,  6, 5, 4,  3, 2, 8);
checkForDuplicateAndMissing(9, 8, 7,  6, 5, 4,  1, 3, 2);
checkForDuplicateAndMissing(9, 8, 7,  6, 5, 1,  2);

Output:

Input: [9, 8, 7, 6, 5, 4, 3, 2, 8]
Duplicate value 8 found at index 8
Missing value: 1
-------

Input: [9, 8, 7, 6, 5, 4, 1, 3, 2]
No duplicates found in the input array
All digits present in the input array
-------

Input: [9, 8, 7, 6, 5, 1, 2]
No duplicates found in the input array
Missing value: 3
Missing value: 4
-------

Update
Array check may store indexes of digits at the input array (shifted by 1), then the information about first index may be printed:

//...
    for (int i = 0; i < arr.length; i++) {
        int d = arr[i];
        if (check[d] != 0) {
            System.out.printf("Duplicate value %d found at index %d, first value is at %d%n", d, i, check[d] - 1);
            noDuplicates = false;
        }
        check[d] = i + 1; // storing index of the digit instead of its count
    }

output for the first input array:

Input: [9, 8, 7, 6, 5, 4, 3, 2, 8]
Duplicate value 8 found at index 8, first value is at 1
Missing value: 1


Source: stackoverflow