I use a different approach than discussed in the forum


  • 0
    S

    I see that most people use a bucket sort approach to solve this problem. This is totally fine. I propose a little different approach here. It takes nlog(n) time and uses sorting.
    I create a small class to hold the index and value of the elements. I then create an array of this class and insert all the vlaues in this array. Now this elements array contain the index and value of all the given numbers. I then sort this array by value.
    Then I initialized two pointers. If the first pointer is at element i then second pointer will be at element j such that nums[j] < nums[i] <= t; I then take this subarray from i to j and then sort them by index. Now it is a matter of simple pair comparison. Here is the code. in C#

    public class Solution
    {
    public class Elements
    {
    public int index;
    public int value;
    public Elements(int i, int v)
    {
    index = i;
    value = v;
    }
    }
    public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t)
    {
    if(nums == null || nums.Length <= 1)
    return false;
    var elements = nums.Select((v,i) => new Elements(i,v)).OrderBy(item => item.value).ToArray();
    int firstPtr = 0;
    while(firstPtr < nums.Length)
    {
    int secondPtr = GetSecondPtr(firstPtr, elements, t);
    if(secondPtr <= firstPtr)
    {
    firstPtr++;
    continue;
    }
    if(IsNearerThanK(elements,firstPtr,secondPtr,k))
    return true;
    firstPtr = secondPtr;
    }
    return false;
    }

    private bool IsNearerThanK(Elements[] ele, int first, int second, int difference)
    {		
    	var elements = ele.Skip(first).Take(second - first + 1).OrderBy(x => x.index).ToArray();
    	int i = 0;
    	while(i < elements.Length - 1)
    	{
    		if(Math.Abs(elements[i+1].index - elements[i].index) <= difference)
    			return true;
    		i++;
    	}
    	return false;
    }
    private int GetSecondPtr(int firstPtr, Elements[] elements, int t)
    {
    	int secondptr = firstPtr;
    	while(secondptr < elements.Length)
    	{
    		long diff = (long)elements[secondptr].value - (long)elements[firstPtr].value;
    		if(diff > t)
    			break;
    		secondptr++;
    	}
    	return secondptr - 1;
    }
    

    }


Log in to reply
 

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