CC-13 : Check if input array contains duplicates.

Description:

Given an input array check if the elements contain duplicates.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array 1: 33, 3, 4, 97, 62, 122, 124, 20, 1,	Array contains duplicate: false
Array 2: 33, 3, 4, 97, 62, 122, 124, 62, 20, 1,	Array contains duplicate: true

Pseudocode:

checkContainsDuplicate(nums[]):

Call quicksort() method to sort the array.

Iterate through nums using for loop with idx as iteration variable and values of idx ranging from 1 to numslength-1:

If nums[idx]==nums[idx-1], we have found a duplicate so return true.

If no duplicate found above, return false.

QuickSort(nums[], startIdx, endIdx):

Integer array named nums, start index startIdx and end index endIdx of nums are received as input parameters.

If (startIdx < endIdx) then execute following steps:

Initialize and integer variable pivot with value nums[endIdx]. We will use this variable to partition the elements into two partitions.

Initialize and integer variable iidx with value startIdx-1. We will use this variable to track and swap elements less than pivot to partition containing elemnts lesser than the pivot.

Iterate through using for loop with jidx as iteration variable and values of iidx ranging from startIdx to endIdx-1:

If nums[jidx]<=pivot then:

Increment iidx by 1.

Swap elements at position iidx and jidx.

Swap elements at index iidx+1 and endIdx.

Set integer variable partitionIdx to iidx+1.

Call method quicksort(nums, startIdx, partitionIdx-1) to sort the partition with lesser elements than pivot element.

Call method quicksort(nums, partitionIdx+1, endIdx,) to sort the partition with greater elements than pivot element.

The element of nums array have been sorted now using Quick Sort, so return nums array from the method.

Code:

public boolean checkContainsDuplicate(int[] nums) {
	nums=quickSort(nums, 0, nums.length-1);
	for (int idx=1; idx < nums.length;idx++){
		if (nums[idx]==nums[idx-1]) {
			return true;
		}
	}
	return false;
}

public int[] quickSort(int[] nums,int startIdx, int endIdx) {
	if(startIdx < endIdx) {
		int pivot=nums[endIdx];
		int iidx=startIdx-1;
		for (int jidx=startIdx; jidx < endIdx;jidx++) {
			if (nums[jidx] <= pivot) {
				iidx++;		
				int swap=nums[iidx];
				nums[iidx]=nums[jidx];
				nums[jidx]=swap;
			}
		}
		int swap=nums[iidx+1];
		nums[iidx+1]=nums[endIdx];
		nums[endIdx]=swap;
		
		int partitionIdx=iidx+1;
		quickSort(nums, startIdx, partitionIdx-1);
		quickSort(nums, partitionIdx+1,endIdx);
	}
	return nums;
}

Click here to download and run code and test cases !

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.

public class SortCheckContainsDuplicate {
 
public boolean checkContainsDuplicate(int[] nums) {
	nums=quickSort(nums, 0, nums.length-1);
	for (int idx=1; idx < nums.length;idx++){
		if (nums[idx]==nums[idx-1]) {
			return true;
		}
	}
	return false;
}

public int[] quickSort(int[] nums,int startIdx, int endIdx) {
	if(startIdx < endIdx) {
		int pivot=nums[endIdx];
		int iidx=startIdx-1;
		for (int jidx=startIdx; jidx < endIdx;jidx++) {
			if (nums[jidx] <= pivot) {
				iidx++;		
				int swap=nums[iidx];
				nums[iidx]=nums[jidx];
				nums[jidx]=swap;
			}
		}
		int swap=nums[iidx+1];
		nums[iidx+1]=nums[endIdx];
		nums[endIdx]=swap;
		
		int partitionIdx=iidx+1;
		quickSort(nums, startIdx, partitionIdx-1);
		quickSort(nums, partitionIdx+1,endIdx);
	}
	return nums;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	boolean retVal;
	try {
	SortCheckContainsDuplicate sort=new SortCheckContainsDuplicate();
	int[] nums= { 33,3,4,97,62,122, 124, 20,1};
	System.out.println("\nArray 1:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	retVal=sort.checkContainsDuplicate(nums);
	System.out.println("\n\nArray contains duplicate: " +retVal);		
	
	int[] nums1= { 33,3,4,97,62,122, 124,62, 20,1};
	System.out.println("\nArray 2:");
	arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums1.length; arrayIndex++) {
		System.out.print(nums1[arrayIndex]+", ");		
	} 
	retVal=sort.checkContainsDuplicate(nums1);
	System.out.println("\n\nArray contains duplicate: " +retVal);		
	
	
			
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}