Given an array of integers arr with duplicates, find the first integer with a duplicate within n distance.
| Input Parameters |
Expected outputs |
| arr1[]={ 1,4,7,3,5,8,3,7,9,3,4};
n=5
|
First repeating number within 5 distance is 3.
|
| arr2[]={ 3,7,4,5,8,9,2,0,3,5,7};
n=5
|
There is no number that repeats with 5 distance.
|
| The java method should accept following input parameters: arr (int array), n (integer).
|
| Initialize a variable set of type HashSet to hold the input elements of arr.
|
| Using a for loop iterate through arr, using idx as a loop variable with initial value 0 and increment idx till it reaches arr.length-1:
If set contains arr[idx], we have found the first integer with a duplicate within n distance, so return arr[Idx] from the program.
If above is not true, add arr[idx] to set.
If (idx >=n) then remove the integer at arr[idx-n] from set, this will mean all those integer elements of arr that do not have duplicate within n distance are removed. Only integers with distance < n remain in the set, this allows us to find duplicates within n distance.
|
| At completion of above loop, if we have not found a duplicate integer within n distance, this means none of the integers within the array have duplicate within n digits. Return Integer.MIN_VALUE indicating the fact that we have not found any integer with duplicate within n distance in arr.
|
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
import java.util.HashSet;
public class SetArrayFindDuplicateWithinNDistance {
public int setArrayFindDuplicateWithinNDistance(int[] arr, int n) {
HashSet<Integer> set=new HashSet<Integer>();
for (int idx=0; idx < arr.length; idx++) {
if (set.contains(arr[idx])) {
return arr[idx];
}
set.add(arr[idx]);
if (idx >= n) {
set.remove(arr[idx-n]);
}
}
return Integer.MIN_VALUE;
}
public static void main(String[] args) {
SetArrayFindDuplicateWithinNDistance sp=new SetArrayFindDuplicateWithinNDistance();
int retVal;
try {
int arr1[]={ 1,4,7,3,5,8,3,7,9,3,4};
int n=5;
printArraySummary(arr1, "Original Array1");
retVal=sp.setArrayFindDuplicateWithinNDistance(arr1, n);
if (retVal!=Integer.MIN_VALUE) {
System.out.println("First repeating number within "+n+ " digits is "+retVal);
}else {
System.out.println("\n There is no number that repeats with n digits");
}
int arr2[]={ 3,7,4,5,8,9,2,0,3,5,7};
n=5;
printArraySummary(arr2, "Original Array1");
retVal=sp.setArrayFindDuplicateWithinNDistance(arr2, n);
if (retVal!=Integer.MIN_VALUE) {
System.out.println("First repeating number within "+n+ " digits is "+retVal);
}else {
System.out.println("\n There is no number that repeats with n digits");
}
}catch (Exception exception) {
System.out.print("Exception,"+ exception);
exception.printStackTrace();
}
}
public static void printArraySummary(int[] intArray, String label) throws Exception {
// Case 1: The input Array is null !!
if (intArray == null) { System.out.println("\n\n Input Array was null !! \n"); return; }
// Case 2: Print input Array by index (first to last)
System.out.println();
System.out.println("************************************************************************");
System.out.print(label+" : ");
int arrayIndex=0;
for (arrayIndex=0; arrayIndex< intArray.length; arrayIndex++) {
System.out.print(intArray[arrayIndex]);
if (arrayIndex< intArray.length-1) {System.out.print(",");}
}
System.out.println();
System.out.println("*************************************************************************");
System.out.println();
Thread.sleep(2000);
return;
}
}