I appeared for Hackerrank intermediate problem-solving certification.
came across the below-mentioned problem and was stuck for more than an hour.
Let there are n number of students and every student has predefined
skill-level ,S where S[i] defines skill-Level of ith student .what is the
maximum number of pairs that can be formed such that the difference
between the skill-Level of students in a pair is not less than a number
,minDiff.
Constraints :
1<n<=2*10^5
0<=S[i]<=10^9
0<=minDiff<=10^5
Sort the array and divide it in 2 array lets call them min and max array. There can not be more than n/2 pairs. pair the minimum elements from both min array and max array and check if their difference is atleast k if not you go forward to the next element in max array. In this way the diff will be always as minimum as possible.
1 Like
If there are no test cases you can go for O(n*n) solution brute force approach traverse through array for each element and check for element in array that can satisfy equation and mark that pair using map. @ssrivastava990 @querty1234 will tell you about efficient approach.
cool,
thanks @nilanjana1234 appreciate ur time
n^2 will not do since n <=10^5
When there are no test cases there is always high probaility for it to work need some optimisation . As soon as you found a match you should mark it and break . Some optimisation and it is good to go. It will be barely passing all test cases thats for sure.