# Non Built-In Java Solution with insertion sort

• With HashMap or HashSet the problem is trivial, but the performance analysis with these built-in functions are always some kind of vague to me.

Anyway, I use insertion sort to solve this problem by searching the insertion index for element (i + 1) within the element range from 0 to i. If the element of the insertion index is equal to the element with index (i + 1), then a duplicate is found.

``````public class Solution {
public boolean containsDuplicate(int[] nums) {
if (nums == null) {
return false;
}
for (int i = 0; i < nums.length - 1; i++) {
if (insertOrder(nums, i)) {
return true;
}
}
return false;
}

private boolean insertOrder(int[] nums, int endIndex) {
int insertionIndex = getInsertIndex(nums, 0, endIndex, nums[endIndex + 1]);
if (nums[insertionIndex] == nums[endIndex + 1] && (insertionIndex != endIndex + 1)) {
return true;
} else {
int currentValue = nums[endIndex + 1];
for (int i = endIndex + 1; i >= insertionIndex + 1; i--) {
nums[i] = nums[i - 1];
}
nums[insertionIndex] = currentValue;
}
return false;
}

private int getInsertIndex(int[] nums, int leftIndex, int rightIndex, int target) {
int m = leftIndex + (rightIndex - leftIndex) / 2;

if (leftIndex > rightIndex) {
return leftIndex;
}

if (target < nums[m]) {
return getInsertIndex(nums, leftIndex, m - 1, target);
} else if (target > nums[m]) {
return getInsertIndex(nums, m + 1, rightIndex, target);
} else {
return m;
}
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.