'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Topics

Search For Integers With Given Difference And At Given Distance

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
34 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 )
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.
Full screen
Console