# My 8ms Java solution beats 98.8%

• The basic idea is to sort the array, and record each element's index in original array. Since I want to practice quick sort so I implemented the modified version of quick sort manually.

nums[] will be a sorted array, and indexs[] will be the array recording the original position of each element.
eg.
the input is 3,1,5,6
nums: 1, 3, 5, 6 (after sort)
indexs: 1, 0, 2, 3
so we can easily use a for-loop to check whether two element's value and index are within the given input;

public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int n = nums.length;
int[] indexs = new int[n];
for(int i = 0; i < n; i++){
indexs[i] = i;
}
quicksort(nums, indexs, 0, n - 1);

``````    for(int i = 0; i < n; i++){
int start = nums[i];
int sindex = indexs[i];
for(int j = i + 1; j < n; j++){
int end = nums[j];
int eindex = indexs[j];
long diff = (long)end - (long)start;
if(diff > t){
break;
}
if(Math.abs(eindex - sindex) <= k){
return true;
}
}
}

return false;
}

private void quicksort(int[] nums, int[] indexs, int start, int end){
if(start >= end){
return;
}
int mid = start + (end - start)/2;
int pivot = nums[mid];
int i = start;
int j = end;
while(i <= j){
while(nums[i] < pivot){
i++;
}
while(nums[j] > pivot){
j--;
}
if(i <= j){
if(nums[i] != nums[j]){
swap(nums, indexs, i, j);
}
i++;
j--;
}
}
quicksort(nums, indexs, start, i - 1);
quicksort(nums, indexs, i, end);
}

private void swap(int[] nums, int[] indexs, int i, int j){
int value = nums[i];
nums[i] = nums[j];
nums[j] = value;
int index = indexs[i];
indexs[i] = indexs[j];
indexs[j] = index;
}
``````

}

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