Katkat
Back

Solve counting and frequency coding tasks

MetaSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to handle frequency counting and constraint-based pair identification efficiently, often requiring a hash map to maintain counts while traversing a stream.

Problem: K-Frequency Pair Counting

Given an array of integers nums and an integer k, return the number of pairs (i, j) such that i < j and the absolute difference between their values is exactly k (i.e., |nums[i] - nums[j]| == k).

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= k <= 10^9

Examples

Example 1: Input: nums = [1, 2, 2, 1], k = 1 Output: 4 Explanation: The pairs are (1,2), (1,2), (2,1), (2,1) using the indices (0,1), (0,2), (1,3), (2,3).

Example 2: Input: nums = [1, 5, 3, 4, 2], k = 2 Output: 3 Explanation: The pairs are (1,3), (5,3), (4,2).

Function Signature

def count_k_difference(nums: list[int], k: int) -> int:

Edge Cases

  • What happens if k = 0? The problem reduces to counting pairs of identical elements.
  • What if the input array contains duplicate elements?
  • Consider the memory and time complexity requirements for large input sizes.

Hints

Hint 1

A brute-force approach would be O(n^2), which is likely too slow for 10^5 elements; consider using a hash map to store frequencies.

Hint 2

For each number 'x' in the array, you are looking for previously seen numbers that equal 'x - k' or 'x + k'.

Hint 3

If k is 0, you simply need to count how many times each number has appeared previously in the traversal.

Follow-up questions

  • How would you modify your solution if the input was an infinite stream of numbers and you had to report the count dynamically?
  • If you were restricted to O(1) extra space but allowed to modify the input array, how would you approach the problem?
  • What is the time complexity of your solution, and how does it change if you were to sort the array first instead of using a hash map?