Teaching Kids Programming: Videos on Data Structures and Algorithms
Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] – nums[j]| == k.
The value of |x| is defined as:
x if x >= 0.
-x if x < 0.Example 1:
Input: nums = [1,2,2,1], k = 1
Output: 4Explanation: The pairs with an absolute difference of 1 are:
– [1,2,2,1]
– [1,2,2,1]
– [1,2,2,1]
– [1,2,2,1]Example 2:
Input: nums = [1,3], k = 3
Output: 0
Explanation: There are no pairs with an absolute difference of 3.Example 3:
Input: nums = [3,2,1,5,4], k = 2
Output: 3
Explanation: The pairs with an absolute difference of 2 are:
– [3,2,1,5,4]
– [3,2,1,5,4]
– [3,2,1,5,4]Constraints:
1 <= nums.length <= 200
1 <= nums[i] <= 100
1 <= k <= 99Hints:
Can we check every possible pair?
Can we use a nested for loop to solve this problem?
Count Number of Pairs With Absolute Difference K via Bruteforce Algorithm
Bruteforcing the pairs of numbers take O(N^2) quadratic time. We then increment the answer/counter once the difference of pairs is K.
1 2 3 4 5 6 7 8 9 | class Solution: def countKDifference(self, nums: List[int], k: int) -> int: ans = 0 n = len(nums) for i in range(n): for j in range(i): if abs(nums[i] - nums[j]) == k: ans += 1 return ans |
class Solution: def countKDifference(self, nums: List[int], k: int) -> int: ans = 0 n = len(nums) for i in range(n): for j in range(i): if abs(nums[i] - nums[j]) == k: ans += 1 return ans
The space complexity is O(1) constant.
Count Number of Pairs With Absolute Difference K via Hash Table
We can count the numbers, and then use the multiplication rule to accumulate the answer quickly. The following algorithm takes O(N) time and O(N) space – based on a hash table. First pass is to count the numbers via Counter, and the second pass is to go through each unique numbers and multiply the corresponding frequency (could be i + k or i – k).
1 2 3 4 5 6 7 | class Solution: def countKDifference(self, nums: List[int], k: int) -> int: c = Counter(nums) ans = 0 for i in c: ans += c[i] * c[i + k] # c[i - k] could also work return ans |
class Solution: def countKDifference(self, nums: List[int], k: int) -> int: c = Counter(nums) ans = 0 for i in c: ans += c[i] * c[i + k] # c[i - k] could also work return ans
Here is another variant of using the hash table – we only perform one pass and update the counter.
1 2 3 4 5 6 7 8 | class Solution: def countKDifference(self, nums: List[int], k: int) -> int: c = defaultdict(int) ans = 0 for i in nums: ans += c[i - k] + c[i + k] c[i] += 1 return ans |
class Solution: def countKDifference(self, nums: List[int], k: int) -> int: c = defaultdict(int) ans = 0 for i in nums: ans += c[i - k] + c[i + k] c[i] += 1 return ans
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Leaderboard Algorithm: Compute the Ranking of Numbers
Next Post: Javascript (NodeJS) Function to Check if a Witness Has been Voted by or Proxied By on Steem Blockchain