Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Search For Integers With Given Difference And At Given Distance

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
36 upvotes
Asked in company
Amazon

Problem statement

You are given an array consisting of 'N' non-negative integers, and two non-negative integers 'K' and 'M', your task is to find a pair of indices(say i and j) from the array such that ‘i’ ≠ ‘j’, |Ai-Aj| <= 'M', and |i-j| <= 'K', where |a-b| represents the absolute value of a-b.

Note :

1) The array may contain duplicate elements.
2) The size of the array is at least 2.
3) The given array follows 0-based indexing so 0 <= i,j< N.
4) It is guaranteed that there exist at least one such pair of indices.
Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line of the input contains an integer 'T' denoting the number of test cases.

The first line of each test case contains three space-separated integers 'N', 'K', and 'M', as described in the problem statement.

The second line of each test case contains 'N' space-separated integers, representing the elements of the array.
Output Format :
You just need to find the pair of indices(i and j), and if the pair returned satisfies the given condition, the output will be shown as “valid”, else the output will be shown as “invalid”.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
1 <= N <= 10^4
1 <= K <= N
1 <= M <= 10^9
1 <= ARR[i] <= 10^9

Where 'ARR[i]' denotes the 'ith' element of the array.

Time Limit: 1 sec
Sample Input 1 :
1
4 1 2
2 4 6 8
Sample Output 1 :
valid(one of the possible answers is 0 1).
Explanation For Sample Input 1 :
Difference between the elements at index 0 and 1 is 2 which is at most M, and also the difference between the indices is 1 which is at most k.
Sample Input 2 :
1
3 2 2
2 3 4
Sample Output 2 :
valid(one of the possible answers is 0 2).
Explanation For Sample Input 2 :
 Difference between the elements at index 0 and 2 is 2 which is at most M, and also the difference between the indices is 2 which is at most k.
Hint

Find all possible pairs that have a difference of at most M 

Approaches (2)
Brute force
  • Idea behind this brute force approach is to run nested loop and each time visit next k elements( because as per the problem statement the indices must have a difference of at most K) from the present index, until we find a pair that satisfies the given conditions.
  • Now, run a loop(say, loop variable i) through all the elements of the array:
  1. Run a nested loop(say, loop variable j) through the elements starting from index i+1 upto next k elements(if present, else till the end of the array).
  2. At each iteration of the inner loop check if the absolute difference of the element at index i and that at index j is at most M then return the indices i and j as the answer, else continue with the process.
Time Complexity

O(N^2), where N is the number of elements in the array.

 

As we are running two nested loops thus making the time complexity N^2.

Space Complexity

O(1).

 

As we are not using any extra space.

Code Solution
(100% EXP penalty)
Search For Integers With Given Difference And At Given Distance
All tags
Sort by
Search icon

Interview problems

C++ ||easy 3 lines code ||

vector<int> indicesAtGivenDistance(vector<int>& nums, int n, int k, int m)
{
    for(int i = 0; i < n; i++){
        for(int j = i; abs(j - i) <= k; j++){
            if(abs(nums[i] - nums[j]) <= m){
                return {i, j};
            }
        }
    }
    return {-1, -1};
}
230 views
1 reply
3 upvotes

Simple O(N) . Better than SOLUTION's provided by coding ninja.

vector<int> indicesAtGivenDistance(vector<int>& nums, int n, int k, int m)
{
    // Write your code here
    for(int i=0;i<n;i=i+1)
    {
        int j;
        if(i+k<n)
        {
            j=i+k;
            // cout<<abs(nums[i]-nums[j])<<"\ti->"<<i<<"\tj->"<<j<<endl;
            if(abs(nums[i]-nums[j]) ==m) return {i,j};
        } 
    }
    return {0,0};
}
140 views
0 replies
0 upvotes

Interview problems

Working Solution Python| Using 2Pointer

def indicesAtGivenDistance(nums, n, k, m):

    # Write your code here

    # Return a list containing two integers denoting the pair of valid indices.

    # You can return the indices in any order

    #

    #--------------------------------------------------------------------------

    #

    # Approach 1 only passed 8/10 TestCases 

    #

    #for i in range(0,n):

    #    for j in range(i+1,n):

    #        if(abs(nums[i]-nums[j])<=m and abs(i-j)<=k):

    #            return(i,j)

    #

    #--------------------------------------------------------------------------

    #

    # Approach 2 More Efficient solution passed 10/10 TestCases

    #

    i=0

    j=n-1

    while(i<j):

        v=abs(nums[i]-nums[j])

        if(v<=m and abs(i-j)<=k):

            return(i,j)

        elif(v>m):

            j-=1

        else:

            i+=1

    return[0,0]

    #---------------------------------------------------------------------------

84 views
1 reply
0 upvotes

Interview problems

Python | O(NlogN) | Two Pointer

x.sort()
i = 0
j = len(x)-1
while(i<j):
	val = abs(x[i]-x[j])
	if(val>m):
    		j-=1
	else:
    		return [i,i+1]
    
return [0,0]

Search For Integers With Given Difference And At Given Distance

182 views
2 replies
1 upvote

Interview problems

Discussion thread on Interview Problem | Search For Integers With Given Difference And At Given Distance

Hey everyone, creating this thread to discuss the interview problem - Search For Integers With Given Difference And At Given Distance.

 

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Search For Integers With Given Difference And At Given Distance

 

173 views
3 replies
0 upvotes
Full screen
Console