New update is available. Click here to update.

Search For Integers With Given Difference And At Given Distance

MEDIUM

20 mins

28 upvotes

Sorting

Arrays

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Search For Integers With Given Difference And At Given Distance

Contributed by

Ankit Kharb

Medium

0/80

Avg time to solve 20 mins

Success Rate 85 %

28 upvotes

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, Constraints, 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.

Auto

Console