Jobs

Interviews

Discussions

Count Number of Pairs With Absolute Difference K

Easy

Asked by:

More companies

35 views

Topics:

Arrays

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: 4
Explanation: 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 <= 99

Try coding it in LeetCode

Count Number of Pairs With Absolute Difference K

Easy

Asked by:

35 views

Topics:

Arrays

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: 4
Explanation: 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 <= 99

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the numbers in the input array, and can the values be negative?
What is the size limit of the input array `nums`?
Are duplicate numbers allowed in the input array, and if so, should pairs (i, j) and (j, i) both be counted if `nums[i]` and `nums[j]` satisfy the condition, assuming i != j?
If no pairs exist that satisfy the condition, what value should I return?
Is `k` always a non-negative integer?

Brute Force Solution

Approach

The brute force way to find pairs with a specific absolute difference involves checking every possible pair. We simply compare each number in the list with every other number. If their absolute difference matches what we are looking for, we count it.

Here's how the algorithm would work step-by-step:

Take the first number in the list.
Compare it with every other number in the list to see if the absolute difference between them is equal to the target difference.
If it is, increase our count of matching pairs.
Move to the second number in the list.
Compare this second number with every number that comes after it in the list (we've already compared it with the numbers before it).
Again, check if their absolute difference is equal to the target difference, and increase the count if it is.
Keep repeating this process, taking each number in turn and comparing it with all the numbers that follow it in the list.
After checking all possible pairs, the final count is the answer.

Code Implementation

def count_pairs_with_absolute_difference_k(numbers, target_difference):
    pair_count = 0

    # Iterate through each number in the list
    for first_number_index in range(len(numbers)):

        # Compare the current number with the rest of the numbers after it.
        for second_number_index in range(first_number_index + 1, len(numbers)):

            # Get the absolute difference for comparison
            absolute_difference = abs(numbers[first_number_index] - numbers[second_number_index])

            #Check if the absolute difference matches the target
            if absolute_difference == target_difference:
                pair_count += 1

    return pair_count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size n. For each element, it compares it with all subsequent elements in the array to check the absolute difference. In the worst case, this involves comparing approximately n*(n-1)/2 pairs, which corresponds to a quadratic number of operations dependent on the input size n. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The provided brute force algorithm iterates through the input array using nested loops, comparing pairs of elements. It uses a counter variable to keep track of the number of pairs that satisfy the condition. The algorithm only uses a few integer variables, such as loop indices and a count, which take up constant space, irrespective of the input array size N. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

Instead of checking every possible pair of numbers, the efficient solution keeps track of how many times each number appears. Then, it quickly calculates the number of pairs that meet the difference requirement using this information.

Here's how the algorithm would work step-by-step:

First, count how many times each number shows up in the list.
Then, for each number, figure out what other number would be exactly 'k' away from it (either 'k' bigger or 'k' smaller).
Check if that other number is actually in the list. If it is, multiply the number of times the original number appears by the number of times the other number appears. This gives you the number of pairs with that specific difference.
Add up the results from all these multiplications to get the total number of pairs that have a difference of 'k'.

Code Implementation

def count_number_of_pairs(number_list, difference):
    number_counts = {}
    pair_count = 0

    for number in number_list:
        if number in number_counts:
            number_counts[number] += 1
        else:
            number_counts[number] = 1

    # Iterate through each unique number
    for number in number_counts:

        # Check for the number 'k' greater
        target_number_higher = number + difference
        if target_number_higher in number_counts:
            pair_count += number_counts[number] * number_counts[target_number_higher]

        # Check for the number 'k' smaller
        # Avoid double counting if k == 0
        if difference != 0:
            target_number_lower = number - difference
            if target_number_lower in number_counts:

                # Count pairs with the 'k' smaller number.
                pair_count += number_counts[number] * number_counts[target_number_lower]

    # Divide by 2 since each pair was counted twice.
    return pair_count // 2

Big(O) Analysis

Time Complexity

O(n) – The algorithm first iterates through the input array of size n to count the frequency of each number using a hash map. This operation takes O(n) time. Then, it iterates through the unique numbers (at most n) and checks for the presence of number + k and number - k in the hash map, which takes O(1) on average for hash map lookups. Thus, the overall time complexity is dominated by the initial frequency counting, resulting in O(n).

Space Complexity

O(N) – The solution uses a hash map (or frequency counter) to store the counts of each number in the input list. In the worst case, all N numbers in the input list are distinct, requiring the hash map to store N key-value pairs. Therefore, the auxiliary space used by the hash map grows linearly with the input size N. Other variables used such as the 'count' variable, or 'target' only take up constant space.

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return 0 to indicate invalid input.
Empty input array	Return 0 since no pairs can be formed.
Array with one element	Return 0 as a pair requires at least two elements.
Large input array (performance)	Use a hashmap-based solution to achieve O(n) time complexity, avoiding nested loops.
k is zero	The solution should correctly count pairs with identical elements.
k is negative	Take the absolute value of k before processing, or handle negative differences appropriately in the comparison.
Integer overflow if numbers are very large	Ensure the data type used to store the difference does not overflow; consider using long if necessary.
Array contains duplicate numbers	The algorithm should accurately count pairs even with duplicate numbers in the input array.

Null input array

How to Handle:

Throw an IllegalArgumentException or return 0 to indicate invalid input.

Empty input array

How to Handle:

Return 0 since no pairs can be formed.

Array with one element

How to Handle:

Return 0 as a pair requires at least two elements.

Large input array (performance)

How to Handle:

Use a hashmap-based solution to achieve O(n) time complexity, avoiding nested loops.

k is zero

How to Handle:

The solution should correctly count pairs with identical elements.

k is negative

How to Handle:

Take the absolute value of k before processing, or handle negative differences appropriately in the comparison.

Integer overflow if numbers are very large

How to Handle:

Ensure the data type used to store the difference does not overflow; consider using long if necessary.

Array contains duplicate numbers

How to Handle:

The algorithm should accurately count pairs even with duplicate numbers in the input array.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the numbers in the input array, and can the values be negative?
What is the size limit of the input array `nums`?
Are duplicate numbers allowed in the input array, and if so, should pairs (i, j) and (j, i) both be counted if `nums[i]` and `nums[j]` satisfy the condition, assuming i != j?
If no pairs exist that satisfy the condition, what value should I return?
Is `k` always a non-negative integer?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number in the list.
Compare it with every other number in the list to see if the absolute difference between them is equal to the target difference.
If it is, increase our count of matching pairs.
Move to the second number in the list.
Compare this second number with every number that comes after it in the list (we've already compared it with the numbers before it).
Again, check if their absolute difference is equal to the target difference, and increase the count if it is.
Keep repeating this process, taking each number in turn and comparing it with all the numbers that follow it in the list.
After checking all possible pairs, the final count is the answer.

Code Implementation

def count_pairs_with_absolute_difference_k(numbers, target_difference):
    pair_count = 0

    # Iterate through each number in the list
    for first_number_index in range(len(numbers)):

        # Compare the current number with the rest of the numbers after it.
        for second_number_index in range(first_number_index + 1, len(numbers)):

            # Get the absolute difference for comparison
            absolute_difference = abs(numbers[first_number_index] - numbers[second_number_index])

            #Check if the absolute difference matches the target
            if absolute_difference == target_difference:
                pair_count += 1

    return pair_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, count how many times each number shows up in the list.
Then, for each number, figure out what other number would be exactly 'k' away from it (either 'k' bigger or 'k' smaller).
Check if that other number is actually in the list. If it is, multiply the number of times the original number appears by the number of times the other number appears. This gives you the number of pairs with that specific difference.
Add up the results from all these multiplications to get the total number of pairs that have a difference of 'k'.

Code Implementation

def count_number_of_pairs(number_list, difference):
    number_counts = {}
    pair_count = 0

    for number in number_list:
        if number in number_counts:
            number_counts[number] += 1
        else:
            number_counts[number] = 1

    # Iterate through each unique number
    for number in number_counts:

        # Check for the number 'k' greater
        target_number_higher = number + difference
        if target_number_higher in number_counts:
            pair_count += number_counts[number] * number_counts[target_number_higher]

        # Check for the number 'k' smaller
        # Avoid double counting if k == 0
        if difference != 0:
            target_number_lower = number - difference
            if target_number_lower in number_counts:

                # Count pairs with the 'k' smaller number.
                pair_count += number_counts[number] * number_counts[target_number_lower]

    # Divide by 2 since each pair was counted twice.
    return pair_count // 2

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return 0 to indicate invalid input.
Empty input array	Return 0 since no pairs can be formed.
Array with one element	Return 0 as a pair requires at least two elements.
Large input array (performance)	Use a hashmap-based solution to achieve O(n) time complexity, avoiding nested loops.
k is zero	The solution should correctly count pairs with identical elements.
k is negative	Take the absolute value of k before processing, or handle negative differences appropriately in the comparison.
Integer overflow if numbers are very large	Ensure the data type used to store the difference does not overflow; consider using long if necessary.
Array contains duplicate numbers	The algorithm should accurately count pairs even with duplicate numbers in the input array.

Null input array

How to Handle:

Throw an IllegalArgumentException or return 0 to indicate invalid input.

Empty input array

How to Handle:

Return 0 since no pairs can be formed.

Array with one element

How to Handle:

Return 0 as a pair requires at least two elements.

Large input array (performance)

How to Handle:

Use a hashmap-based solution to achieve O(n) time complexity, avoiding nested loops.

k is zero

How to Handle:

The solution should correctly count pairs with identical elements.

k is negative

How to Handle:

Take the absolute value of k before processing, or handle negative differences appropriately in the comparison.

Integer overflow if numbers are very large

How to Handle:

Ensure the data type used to store the difference does not overflow; consider using long if necessary.

Array contains duplicate numbers

How to Handle:

The algorithm should accurately count pairs even with duplicate numbers in the input array.