# 5ms 98.8% Java Solution

• ``````public class Solution {
public void xwap(int[] a, int i, int j) {
int tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}

public void qsort(int[] a, int[] indice, int s, int t) {
if (s>=t) return;
int mid=a[(s+t)/2], i=s, j=t;
while (i<j) {
while (i<j && a[i]<mid) i++;
while (i<j && a[j]>mid) j--;
if (a[i]==mid && a[j]==mid) j--;
if (i<j) {
xwap(a,i,j);
xwap(indice,i,j);
}
}
qsort(a,indice,s,i-1);
qsort(a,indice,i+1,t);
}

public boolean containsNearbyDuplicate(int[] nums, int k) {
if (nums==null) return false;
if (nums.length<2) return false;
int n=nums.length;
int[] indice = new int[n];
for (int i=0; i<n; i++) indice[i]=i;
qsort(nums,indice,0,n-1);

for (int i=0; i<n; i++) {
int j=i+1;
while (j<n && nums[j]==nums[i]) {
if (Math.abs(indice[i]-indice[j])<=k) return true;
j++;
}
}

return false;
}
}``````

• Hi, I appreciate the mapping way designed by yourself. But quicksort here could be easily degrade? I checked the testcase by increasing order. Did you avoid this by choosing pivot as middle one?

• I didn't aovid it. A carefully designed test cases can degrade qsort efficiency. I didn't consider those cases. But in general qsort is sufficient.

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