- Practice
- Algorithms
- Search
- Pairs
- Discussions

# Pairs

# Pairs

agoston_fung + 38 comments Nice and simple with Javascript, after sorting the numbers.

var i=0,j=1,count=0; while(j < n) { var diff = nums[j] - nums[i]; if (diff == k) { count++; j++; } else if (diff > k) { i++; } else if (diff < k) { j++; } }

dush1729 + 0 comments Nice. Known as two pointer approach.

Odiumediae + 0 comments A nice, clean and simple, but pretty effective way of solving this problem, thanks! For fellow pythonistas; this approach also works well in Python3. I used

`array.array`

instead of a list, because I was afraid it might still time out too easily, but it would probably work just as well using plain old lists.Vinay_Gade + 0 comments Gr8 logic sorting numbers prior to getting difference I have tried be4 sorting numbers and time limit exceed in some cases.. Thanks a lot!

cbruguera + 1 comment Such elegance!

raja_e_baz + 11 comments Want elegance?

Can be done with a one-liner in python:

len(set(a) & set(x + k for x in a))

Where a is the array of numbers. Runs in O(N) to boot(sorting is O(nlogn))

SachinShikhare + 0 comments awesome

rudra_utpal + 2 comments possible in Java too

if(Arrays.binarySearch(al,al[i]+k) >=0 ) count++;

mbellati + 1 comment You don't need binary search. Build a Set with all the numbers, then

Set<Integer> numbers = ... long matchCount = numbers.stream() .filter(i -> numbers.contains(i - k)) .count();

carlos_contreras + 0 comments This would be the C# version of your code:

var numbers = arr.ToList();

return arr.Where(x => numbers.Contains(x - k)).Count();

kapploneon + 1 comment Will this not require sorting? Binary search requires sorting the array so cannot say it is 1 liner.

kingpmp2006 + 0 comments Set.contains() checks hashcode, no sorting required, and it is O(1)

AffineStructure + 2 comments I did the same thing. how did you do the Time Complexity calculation? look-ups in a set is O(1), so is it len(a)*O(1) == O(N)?

bfzamperetti + 0 comments when we say O(N), N is a convention to the number of elements, so in this case len(a) = N, and O(N)*O(1) = O(N).

Melkon + 0 comments The time complexity is O(n log n) as you have to sort the array.

jessachandler + 1 comment nice. I tried a list comprehension (two lines) but it times out. I thought there might be repeats, negating set.

`answer = [1 for x in range(len(a)) for y in range(x+1,len(a)) if abs(a[x] - a[y]) == k] return sum(answer)`

AniketBharati + 0 comments cause,although its list comprehension(two lines) in python,it still is an O(N^2) approach.

DivJain + 1 comment Can someone explain this? What is & doing?

SamLeatherdale + 0 comments I think it's taking the intersection of the two sets.

stratigos + 0 comments This is the approach I wanted, mainly for the elegence in the expression. Unfortunately its too slow for my beloved Ruby! Lucky you Python people can blaze through that same one liner and still pass. I tried the two-pointer approach as described by @agoston_fung and its fast enough to pass with Ruby ;-)

b_hus_han + 0 comments Can u please explain this

wilmer_henao + 1 comment I thought about sets but nowhere in the text does it say that elements are unique.

Lucky that it passes all cases.

jacksonleighall1 + 1 comment "each integer arr[i] will be unique"

wilmer_henao + 0 comments Ahhh!. How did I miss that! Thanks

fhnjs435 + 0 comments The second set() is redundant if you use the (arguably more readable) intersection function instead:

len(set(a).intersection(x+k for x in a))

ilkercankaya + 0 comments [deleted]sj_enigma + 0 comments Can you please explain your solution? Thanks in advance.

nagarjun2695 + 0 comments Really nice... :)

Pritam0209 + 0 comments i also solved it by same logic but j goes out of index

dyesdyes + 1 comment Pretty good although this approach is not the quickest. It will be at best O(n * log(n)). With a dictionary approach, it can be done in O(n).

raushan_exotel + 1 comment Can you explain how ??

simon_reiffen + 8 comments Simple. Iterate through the array once, and add each number to a dictionary. Then, iterate through a second time, and, for each number, see if that number + k exists in the library. If it does, then you know you have a pair, and can increment anwser

def pairs(a, k) d = {} answer = 0 for i in a: d[i] = i for j in a: g = j+k if g in d: answer +=1 return answer

virco + 1 comment Well that's exactly NlogN.

dangerDon + 2 comments i don't think so Because it is not using binary search instead it use dictionary that use hashing So it is O(n) only Correct me if i am wrong

karioun_jaafar + 3 comments You are correct for the complexity, however no need for a dictionnary here, a set does the trick. Also, you can do this in one iteration over the collection by adding the numbers to the set incrementally and checking if the complement was already present in the set. Something like this:

numbers = set() count = 0 for n in a: if n + k in numbers: count += 1 if n - k in numbers: count += 1 numbers.add(n) return count

jacob_cyrus_sta1 + 0 comments Very excellent answer

kandpalbharat83 + 0 comments searching in a list requires O(N) time, whereas dict requires only O(1) time.

msilb + 0 comments Nice one. Indeed can be easily done using 1 iteration in log(N) time. Slightly uglier but similar solution using Java 8:

static int pairs(int k, int[] arr) { int res = 0; Map<Integer, Integer> complements = new HashMap<>(); for (int el : arr) { if (complements.containsKey(el)) { res = res + complements.get(el); } if (el - k > 0) { complements.compute(el - k, (key, value) -> (value == null) ? 1 : value + 1); } complements.compute(el + k, (key, value) -> (value == null) ? 1 : value + 1); } return res; }

puneetd30 + 0 comments It is O(n)

raghav42 + 3 comments My code is

def pairs(a,k): # a is the list of numbers and k is the difference value c=0 for i in a: g=i+k if g in a: c+=1; return c

Why am i getting timeout in some of the test cases?

mklassen + 2 comments Your code has complexity O(n^2) -- It should be at least O(n * logn) to not time out. Its possible to solve it in O(n)

raghav42 + 1 comment i believe it's O(n).

mklassen + 1 comment for i in a: #top level for-loop g=i+k if g in a: #nested for-loop c+=1;

For each element in a you're performing another search through all of a. The (g in a) is definitely an O(n) operation.

samirsahu + 1 comment Not sure about Python, but the "g in n" in Java using a HashSet/Map would typically get O(1). Although it depends on the hashing algorithm used internally, but overall fetching from a HashSet/Map is considered as O(1). If the hashing is not good enough, it can turn out to be a O(n).

VitorRafael + 0 comments Python's "in" operator has different time complexities depending on the data structure being used. If it's a list it might reach O(N) very easily, but using a Dictionary - Python's Hashtable - or a Set, both use the __hash__ method, is O(1). It might reach O(N) if the __hash__ is not well implemented just like samirsahu said.

ameegosar + 0 comments Have you solved it with O(N)?

I thought my code below was O(N) but apparently not because it fails 4 test cases :

static int pairs(int k, int[] arr) { // Complete this function Dictionary dict = new Dictionary(); int count =0; int k1; for(int i=0; i k) { k1 = arr[i]-k; //{(5,0),} } else { k1 = arr[i]; //3, 1 }

`if(dict.ContainsKey(k1) || dict.ContainsKey(arr[i])) { if(dict.ContainsKey(k1)) { dict[k1]++; count++; } else { dict.Add(k1,0); //{(1,0),(1,1),(4,0)}, {(1,1),(3,1),(2,1)} } if(dict.ContainsKey(arr[i])&&arr[i] != k1) { dict[arr[i]]++; count++; } else if(arr[i] != k) { dict.Add(arr[i],0); } } else { dict.Add(arr[i],0); if(arr[i] != k1) { dict.Add(k1,0); } } } return(count); }`

devansh1497 + 0 comments The line "if g in a" also has a complexity of O(n).

nikhil_beast + 0 comments [deleted]

stivencp321 + 0 comments tanks :D

JJJason + 0 comments you can use

**d = set(a)**to replace your first for looplohyinghao91 + 1 comment Java implementation

`static int pairs(int k, int[] arr) { int sum =0; Set<Integer> set = new HashSet<Integer>(); for(int n=0; n< arr.length; n++){ set.add(arr[n]); } for(int n=0; n< arr.length; n++){ if(set.contains(arr[n]+k)){ sum+=1; } } return sum; }`

kamurtiveena + 1 comment can you please explain secong loop for(int n=0; n< arr.length; n++){ if(set.contains(arr[n]+k)){ sum+=1; }} how it works?actually what its going to check

RedAesthetics + 0 comments Set has already stored all of the array elements previously. Then there is a comparaison between each element of the array individidualy + the targeted value "K". So, if that sum is available within the elements inside of the set list, then it will increment.

samirsahu + 3 comments Here is the same thing in Java: -

`HashSet<Integer> map = new HashSet<>(); for(int i=0; i<arr.length; i++){ map.add(arr[i]); } int pairCount = 0; for(int i=0; i<arr.length; i++){ if(map.contains(arr[i]-k)){ pairCount++; } } return pairCount;`

Time complexity would be O(n). Typically fetching from a HashSet is O(1). Space complexity would also be O(n).

Passed all test cases.

saket0565 + 0 comments java is more efficient than c++ . In it would have taken O(logn) to find the key.

salim_yahya89 + 0 comments Thank you, it helped. I started with a linear search, but always get "Time-out".

bakocsaba80 + 0 comments This is my sollution:

`Set<Integer> numbers = new HashSet<>(); int pairs = 0; for (int n : arr) { numbers.add(n); if(numbers.contains(n+k)) pairs++; if(numbers.contains(n-k)) pairs++; } return pairs;`

iabhayt + 0 comments [deleted]gaal_dev + 0 comments d = set() as an alternative

Lac_Loi + 0 comments very nice , didnt know this ,thank you :D

sukhendu123 + 0 comments great logic..

adithyagaroju + 0 comments Highly compact code !!!

codesith + 3 comments No need to sort. You can get it done in O(n). create a new Array size of 2^32-1 For each element in the original array, add K to it. Use the sum as the index in the second array and set the value to true. Take a second pass of the original array, use the value of each element as the index in the second array. If there's a match in the second array, increment a counter. There you go.

ahan98 + 1 comment this is the solution I thought of as well, but when I tried implementing it in C, I kept getting a segfault because the amount of memory you need to allocate for an array that large results in a stack overflow. is there a way to implement this solution in C?

jacksonleighall1 + 0 comments Use one bit per integer such that the arraysize is (2^32-1)/8 bytes. See my other post for code.

steffen_vulpius + 0 comments Instead of a sparse array, store the sum in a HashTable. And then in the second pass check if the element value is present as a key.

RENAS + 0 comments I implemented this approach but in C#, using a int,int Dictionary to store the counted items and their count. each item can be paired with multiple items, i count this possible pairs and add that count to the sum. space and time complexity is O(n).

agarwal1810 + 0 comments I think we can increment the value of i also for diff == k , as there is no use of testing same i with higher values of j, all values being unique.

wins1908 + 2 comments Nice, thanks for your solution. I have an improvement which would reduce a half of loop. In case of diff > k, after increasing i by 1, let's check of i == j and increase j by 1 as well.

static int pairs(int[] a,int k) { int matches = 0; Arrays.sort(a); int i = 0; int j = 1; while (j < a.length) { int diff = a[j] - a[i]; if (diff == k) { matches++; j++; } else if (diff > k) { i++; if (i == j) { j++; } } else if (diff < k) { j++; } } return matches; }

faridhuseynov_e1 + 0 comments why do we need to check, whether i==j in case of diff>k? j is always higher than i and once you find diff>k your i increases, however even though at that stage i=j the for loop already compensates for ++j.

udit08 + 0 comments Did the same but time out in 2 test cases(12 and 14). Please tell the reason.

luisgrases + 0 comments Another clear high level way of doing it using javascript:

var hash = x.reduce((prev, next) => { prev[next] = true; return prev; },{}) var result = x.reduce((prev, next) => { return (hash[next+k]) ? prev + 1 : prev; }, 0)

Just need to traverse the list 2 times: O(N)

darkjedi + 0 comments TIL: Always use a compare function inside Array.sort() as without any compare function, it compares wrt unicode.

saikumar_09 + 1 comment I am actually an electronics student with a great interest in coding (especially PYTHON 3.5). Even I came up with a solution that's working fine, but exceeded time limit (as i always use lists in solving which take more time). So can anyone suggest me books I should read, that can make me code like you all which runs my program in a lesser time Thanks in advance

luisgrases + 1 comment Watch the free MIT course of algorithms in youtube

saikumar_09 + 0 comments Thank you for the

Shakil335 + 0 comments Can you please explain the code ..

starjasmine + 0 comments [deleted]shubham_sawlani1 + 0 comments Similarly, can we use this technique to find no of pairs present in the array whose sum is equal to X?

starjasmine + 0 comments I reconsidered your tip and finally I found that you're right. Thanks.

alihashir4799 + 1 comment C++:

long pairs(long k, vector array) { long count = 0,temp; std::sort(array.begin(),array.end());

`for(int i=0;i<array.size();i++){ for(int j=i+1;j<array.size();j++){ if(array[j]-array[i]==k){ count++; } if((array[j]-array[i])>k){ ++i; j = i; continue; } } }`

return count;

}

bikrant_sync + 0 comments there is no need to 'continue' if you are using a sorted array.

Here is a working code:

`Arrays.sort(arr); int count = 0; for(int i=0; i < arr.length - 1;i++) { for (int j=i; j < arr.length;j++) { if (arr[j] - arr[i] > k) { break; } else if (arr[j] - arr[i] == k) { count++; } } } return count;`

hemanthraju88598 + 1 comment if u sort, it would take extra time to sort, O(nlogn) even if you use efficent sorting algorithm like quicksort . then how come the time didnt exceeded its limit?

lohyinghao91 + 0 comments hashset is a unsorted alogrithim. The retreival time of hashset is o(1). Therefore the 2 for loop only cause the entire alogrithim to be of o(n) complexity.

san_cse + 0 comments this will not work if we have identical elements in array

anita_sahu + 0 comments Thanks a lot for the simple and optimised logic.

quanghm + 0 comments while it passes all test cases, it is not correct when array has repeated values. For example, input

`6 1 1 1 2 2 3 3`

yields

`4`

as output while it should be`8`

.sai4992 + 0 comments if elements are unique, we can increment ' i ' too in if statement right??

joaoareiasmoraes + 0 comments You can do it in linear time without sorting

jaipalchauhan52 + 0 comments Great.Thanks for the help.

nevvermind + 0 comments Nit-pick to an otherwise great solution: once you find a correct difference, you can also increase

`i`

, not only`j`

, removing some unnecessary comparisons:if (diff == k) { count++; j++; i++; } else if (diff > k) { i++; } else { j++; }

aimarpaulo + 1 comment What if the array has duplicate value for example 1 3 3 6 6 9.

fhnjs435 + 0 comments Re-read the question. * each integer arr[I] will be unique

bo4arovpavel1989 + 0 comments [deleted]bo4arovpavel1989 + 0 comments There is better - O(n) solution:

let dictArr = {};

`for (let i = 0; i < arr.length; i++) { dictArr[arr[i]] = dictArr[arr[i]] ? dictArr[arr[i]] + 1 : 1; } let counter = 0; for (let i = 0; i < arr.length; i++) { let hasToBe = arr[i] - k; if (dictArr[hasToBe]) counter += dictArr[hasToBe] } return counter;`

soheshdoshi + 0 comments i also did same

soumosirdutta + 0 comments trying to understand with test case as [1,1,2,2,3,3,4] should i first make this array unique set of elements and then apply the two pointer method ?

udit08 + 0 comments I did the same but it says Time limit exceeded in 4 test cases

nitish2041 + 0 comments great logic

dashyabhishek98 + 0 comments Are you sure this logic is working ? Because i implement this logic in java but the 3 sample test is fail.

AVCarreiro + 8 comments Since we are guaranteed that each number is unique, we can use a structure with constant-time contains() and solve the problem in linear time, am I wrong? At least my solution passed all test cases.

f2003062 + 4 comments I dont think we can solve it in linear time. My solution of O(NlogN) time is accepted. Is it possible without sorting the given array..?

AVCarreiro + 0 comments If your solution was accepted you can now see the editorial. They expect a solution of at least O(N logN), but that's dependent on the structure you use, like a binary search tree or hash table.

ennorehling + 3 comments You cannot do better than sorting the array and looking up the target value with binary search. Binary search is O(log n), and you have to do n of those, so your total complexity is O(n log n), which is the same complexity as sort, so sorting the array is a "free" operation.

If you implement this with any other data structure (hashmap, etc) that has O(log n) complexity for a lookup and insert, you're still going to have to make n lookups, which gives you a total complexity of O(n log n). The only way to improve on the sorted array would be to have a data structure that allows lookup and insert complexity below O(log n), and there's no such thing.

abandonclock + 5 comments I used python.

Since all numbers are unique, you can convert original input array to a set, which is O(n) time complexity. And construct a set with each number adding k, which is also O(n).

Then origional_set&with_k_larger_set is just the answer, which costs O(n). Adding all together, the time complexity is O(n).

ennorehling + 2 comments Can you explain what you mean when you say "converting an array to a set"? How is this set implemented?

abandonclock + 0 comments Definition of set in python is basically same as in math.

A set is an unordered collection with no duplicate elements. Basic uses include membership testing and eliminating duplicate entries. Set objects also support mathematical operations like union, intersection, difference, and symmetric difference.

list_a = [1,2,3] set_a = set(list_a) # set_a = set([1, 2, 3]) list_b = [1,3,3,2] set_b = set(list_b) # set_b = set([1, 2, 3])

Set is implemented by hash table in python.

nikolay_dimitrov + 0 comments ennorehling is right, the implementation behind that "set" cannot be magical :)

opeispo + 0 comments Wow. Thumbs up!

ruppala3 + 0 comments Brilliant!

vipul144 + 0 comments Could you please expalin "Then origional_set&with_k_larger_set is just the answer", How adding "k" to the original_set gives the answer?

RyanayR + 1 comment I wish I thought of that! It's one line in python...

def pairs(a, k): return len(set([x + k for x in a]).intersection(set(a)))

dingo_custer + 1 comment Would this be faster?

a=set(a) return sum(x+k in a for x in a)

Also, you don't need the brackets - you can do a set comprehension instead of a converting a list comprehension

miladneek + 0 comments why does it run a lot slower if you don't do a = set(a) ?? and just do the 2nd line?

baran_jana + 0 comments note that hash map has a constant lookup and insertion, you have probably mistaken this with BST.

coderanga + 0 comments instead of using binary search over the sorted array, using interpolation search would be tardly more efficient: compute mid at every point using: mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where âˆ’ A = list Lo = Lowest index of the list Hi = Highest index of the list A[n] = Value stored at index n in the list X = element to be searched Proven that time complexity in this case would be log(log n) per search, so for n elements it would be n(log(log n) , however when it comes to big O, the effective worst case for O(nlogn) + O(n(log(logn))) would still remain O(nlogn). Let me know if you have some thoughts here

gary_chen1 + 0 comments You can do it in linear time if use linear space too. Construct a hash table whose keys will be all a[i]-k and a[i]+k (k above and below each numebr in the array).

Walk through the table once; for each number, add to your answer the value for key a[i] in the lookup table, and then increment a[i]-k and a[i]+k's value in the lookup table.

This solution worked for me; it takes O(n) time and O(n) space.

foxtrot + 4 comments I used a dictionary in which, all the numbers in the array are the keys - all with value 1 (to signify that this key exists). Now, when I use dict [3] and it returns to me a 1, this means that 3 exists in the array. Using this trick, I was able to make a linear time program (The longest a case took was 0.04s)

So yeah, you're right!rotten_egg + 1 comment what is the size if array dict that you have used?? i am getting segmentation fault by using this method!

foxtrot + 2 comments Size of the dict constructed is the same as size of the array (1 key-value pair for every element in the array). Could you please show me your code? I might be able to understand your problem better.

Here's mine (Python 3):

https://github.com/duaraghav8/Hackerrank-Problems/blob/master/pairs.pyrotten_egg + 1 comment #include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cstdio> #include <limits> #include <vector> #include <cstdlib> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> using namespace std; /* Head ends here */ int pairs(vector < long long int > a,long long int n,long long int k,long long int max) { long long int ans=0; long long int c[max]={0}; for(int i=0;i<n;i++) { c[a[i]]=1; } for(int i=0;i<n;i++) { if(c[a[i]+k]==1) ans++; } return ans; } /* Tail starts here */ int main() { long long int res; long long int _a_size,_k; cin >> _a_size>>_k; cin.ignore (std::numeric_limits<std::streamsize>::max(), '\n'); vector<long long int> _a; long long int _a_item; for(long long int _a_i=0; _a_i<_a_size; _a_i++) { cin >> _a_item; _a.push_back(_a_item); } long long int max = -1; for (auto val : _a) { if (max < val) max = val; } res = pairs(_a,_a_size,_k,max); cout << res; return 0; }

I am quite naive, trying to implement hashing, but since the values in the array are quite big, i am getting segmentation fault, and only four test cases are cleared, please help me.

foxtrot + 1 comment The code is displayed in a very messy way on Hackerrank Comment threads, but I kind of get what you're trying to do. Ok so here's the link to the C++ Code I wrote for you. It Passes all test Cases and max time is 0.11s. Hope you'll be able to figure out where you went wrong :)

https://github.com/duaraghav8/Hackerrank-Problems/blob/master/pairs.cpp

rotten_egg + 0 comments thanks a ton!

smartyzack + 0 comments I have some confusion about the size of the dict you may have used, even though I am not much familiar with python (so I maybe mistaken) I observe nowhere in code have you specified the size of the array. From what I can think the size of the dict should be the largest integer in the input.

Following is my understanding:

For eg : If array has only 2 inputs say 1 and 6. and difference to be searched for is 5. You would be searching for numbers[1+5] ie numbers[6], so here numbers[6] needs to be 1, while according to what you said the size of dict would be same as size of array which would not be true in this case.

Please correct me if I am mistaken.

vladis466 + 2 comments Basically the same thing but within the confines of the printed code that comes when the page is loaded. Slowest = .07 seconds.

Out of curiosity is there a reason you would use the try as opposed to a simple if statement? I am new to python

def pairs(a,k): #a contains array of numbers and k is the value of difference #put all values into a dictionary. If it exists,extract myDict = {item : 1 for index, item in enumerate(a)} count = 0 for each in myDict: if each + k in myDict: count += 1 print count if __name__ == '__main__': a = map(int, raw_input().strip().split(" ")) _a_size=a[0] _k=a[1] b = map(int, raw_input().strip().split(" ")) pairs(b,_k)

foxtrot + 0 comments I understand your doubt. I had the same after about 2 months into the language. I'd like you to read the first answer to this question:

http://stackoverflow.com/questions/1835756/using-try-vs-if-in-pythonjackfrosty + 0 comments Probably unnecessary to add the 'enumeration' because you never use the 'index' while creating/populating 'myDict.'

ennorehling + 0 comments Your time may not be too awful, but your space usage is insane. Your complexity isn't linear though: No matter what you're doing, you have to check every number in the input array at least once for a match, so that's O(n) operations of that check, no matter how it's implemented.

gnawer + 2 comments To make a true hash set for the entire range of 32-bit integer you need to spend 2^32 space. You can make a hash of say (2^32 / 10000) size, which will then give you worst-case search performance O(10000). But technically it's still O(1). So I think you are correct, but this is one of these cases where theory and real world differ a lot.

foxtrot + 0 comments A few days back I was reading an argument about how constructing a Suffix Tree, despite being O(N) in worst case, has a large constant factor which can be costlier than the O(N.log^2(N)) Suffix Array method. So yeah, I agree with you when you talk about the difference between theory and practice!

nommet77 + 0 comments Good hash set implementation would require like around 20-30% more memory than the data itself.

gitChristian + 1 comment Yes we can solve it in linear time using a hash table. Load up the vector into the hash table, then for each element, ask if the element (+ or -) k exists in hash table.

ennorehling + 1 comment Inserting into a hashtable is not O(1), though. Neither is lookup, they are both

*amortized*O(log n), so your total complexity is O(n log n).frederik + 1 comment This is wrong. Insertion and lookup are both O(1) amortized: https://www.cs.cornell.edu/courses/cs312/2008sp/lectures/lec20.html

ennorehling + 2 comments You're right, my college days are long ago. But for realistic hash implementations, conflict resolution in worst cases is still worse than O(1). I still believe that being better than O(n log n) for worst-case inputs is tough.

Kevinagin + 0 comments Even though there is the amortized cost of dealing with collisions, it is still O(1). That's because you drop coefficients in big-O notation. So the hashing approach can give you a runtime of O(n) on this problem.

slashvar1 + 0 comments There's a lot to be said about conflict in a hash table.

Most modern implementations combine a smart probing approach with storage reallocation when conflict rate increases. You can thus expect O(1) in most insert/lookup most of the time.

Of course, if you use a fixed size storage and solve conflicts with linked list of elements, things can go really wrong. But again, it depends on the storage size and the quality of the hash function.

NitinTak + 0 comments [deleted]tomsmeding + 0 comments Only really because the numbers themself are really bounded (<=10^5), so you can just allocate an array of 10^5 booleans (10kb) and use that as your data structure. Had the numbers been the full int range, for example, the space to allocate would have grown to ~2gb (or 4gb if negatives are allowed), which isn't really doable anymore.

bruce20036 + 0 comments Try to use a queue to store the expected pair for each elements. It is possible to run in O(N).

dyesdyes + 0 comments Note that you don;t need to have unique numbers to compute the number of pairs.

Synclicity + 2 comments Python one-liner

return len(set(a) & set([item + k for item in set(a)]))

168W1A0575 + 0 comments Awesome man!

andreibelcin17a1 + 0 comments I just used a dict :) Your solution is awesome!

puntu + 0 comments what rubbish! Why should I solve in O(NlogN). just use a Hashtable and just check that of(a[i]+k) and (a[i]-k) is in that table or not. just using one scan you can solve it. the time complexity is O(N)

draciel + 1 comment I am able to get correct answer on my system but I am getting segmentation fault on hackerrank for all test cases. I am using gcc 4.6.3 on Ubuntu

PRASHANTB1984 + 1 comment Hi, Notes on the environment are here. Also, we have hidden cases which are larger and more complex than the samples which you see. Seg fault typically happens because of invalid memory access (array index which doesn't exist, etc.).

h15026020016 + 0 comments sir same issue. but i used vectors

marinskiy + 1 comment Here is

**Python 3**solution from my HackerrankPractice repository:n, value = map(int, input().split()) points = list(map(int, input().split())) distances = [x + value for x in points] ans = len(set(points) & set(distances)) print(ans)

Feel free to ask if you have any questions :)

marinskiy + 0 comments time complexity is still nlogn though

hysang + 0 comments C++ solution works. Use hash function to solve it.

int pairs(int k, vector<int> arr) { int res = 0; unordered_set<int> sta; for(int i = 0; i < arr.size(); i++) sta.insert(arr[i]); for(auto it = sta.begin(); it != sta.end(); it++) if(sta.find(*it+k) != sta.end()) res++; return res; }

mannnsfeb19 + 1 comment Anybody help, i'm failing only test case 14 , why?

below is the solution:

// Complete the pairs function below. static int pairs(int k, int[] arr) {

`Hashtable<Integer,Integer> ht = new Hashtable<>(); int pairs=0; for (int i=0;i<arr.length;i++) { if( ht.containsKey(Math.abs(arr[i]-k) ) ) pairs++; if( ht.containsKey(k+arr[i]) ) pairs++; ht.put(arr[i],i); } return pairs; }`

brian_aronowitz + 1 comment I have a similar answer, and also am failing test 14!

brian_aronowitz + 1 comment Alright, solved it. I basically just changed my solution to use a two passes rather than one. The first pass to put the values (c) into a map, then I iterate again on the second pass, and just check if the complement exists (c+k).

I think there's some pathologial edge case if you check both ways in a single pass. Not sure if I can prove it, but this solution works, and is (O(2N)) vs O(N).

mannnsfeb19 + 1 comment true, as the test case itself is very large, can't check where the edge case is going wrong. thanks for the reply.

lhcopetti + 0 comments I found out the problem and I had a really similar code like yours. The culprit is the

`Math.abs`

call. Try your code with this input:(n=2, k = 6) [2, 4] 2 6 2 4

The solution is zero, but it outputs one because

`Math.abs`

gets in the way

vishal59 + 0 comments function pairs($k, $arr) { sort($arr); $c=0; $arr=array_unique($arr); for($i=0;$i<count($arr)-1;$i++) for($j=$i+1;$j<count($arr);$j++) if(($arr[$j]-$arr[$i])==$k) { $c++; break; } return $c; }

I wrote this code in php, while checking the test-cases from 10 to 14 my test-cases were failed. please let me know if anyone get any kind of solution.

Sort 541 Discussions, By:

Please Login in order to post a comment