We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Search
- Pairs
- Discussions
Pairs
Pairs
Sort by
recency
|
1263 Discussions
|
Please Login in order to post a comment
java public static int pairs(int k, List arr) { int count = 0; int start = 0; Collections.sort(arr); for(int i = 1; i < arr.size(); i++){ int diff = arr.get(i) - arr.get(start); if(diff > k) { start++; i--; } else if (diff == k) { count++; start++; } } return count; }
Java solution using Lambdas
}
Golang Time Complexity: O(n) Space Complexity: O(n)
First: populates a hash map with all elements from the input array arr for quick lookups.
Second: For each element x, it checks if x - k and x + k exist in the hash map. if exist, count
The current element x is then removed from the hash map to prevent counting the same pair twice (e.g., counting (3, 5) when x=3 and then again when x=5)
}
`
My Java 8 solution, which passes all test cases, for a Max Score of 50:
(1) Sort the Array in Ascending Order.
(2) Iterate through the array sequentially from
arrIndex = 0
all the way toarrIndex = arr.size() - 2
, and do the following:(2) (a) Make a
subList
which spans fromarrIndex + 1
to the last index of the array. This is our way of narrowing our search space. We expect the other value in the pair to occur in this space.(2) (b) For the element at
arr[arrIndex]
: do a "Binary Search" through the Narrowed Sorted Sublist (costingO(log (n))
- to attempt to find the "other corresponding expected value", which would result in the "target difference". If search is successful, then Another Pair has been FOUND. At this point, we also increment thesubListStartIndex
, narrowing our search space further.Overall Expected Worst Case Time Complexity:
O(n * log(n))
.