面试算法题：在不可修改的无序数组中找乘积大于k的二元组

Alright, let's tackle this problem step by step, making sure we stick to all the constraints: no sorting, modifying the original array, or creating sorted copies. Our goal is to find all unique pairs whose product exceeds a given integer k, while keeping the time complexity as low as possible.

Core Approach #

The key insight here is to use a frequency hash map to count occurrences of each element in the array. This lets us work with unique values only (avoiding redundant checks) and handle duplicates properly without altering the original array. We'll split our logic into cases based on the value of k (negative, zero, positive), since the conditions for a valid pair change drastically with k's sign.

Case Analysis & Implementation #

Let's break down each scenario:

1. When k < 0

Any pair that results in a non-negative product will automatically satisfy product > k (since non-negative values are larger than negative k). Additionally, we need to check negative-positive pairs where their negative product is still greater than k (e.g., k=-10, pair (-2,3) gives -6 > -10):

• Non-negative pairs: Include positive-positive, positive-zero, and zero-zero pairs (if applicable).
• Negative-negative pairs: Their product is positive, so it's always greater than k.
• Negative-positive pairs: Only include pairs where a*b > k (the negative product is larger than the negative k).

2. When k = 0

Only pairs with a positive product are valid (since we need product > 0). This means:

• Positive-positive pairs
• Negative-negative pairs
  All other pairs (positive-negative, positive-zero, etc.) result in products ≤ 0 and are excluded.

3. When k > 0

Only pairs with a positive product that exceeds k are valid:

• Positive-positive pairs where their product is greater than k
• Negative-negative pairs where their product (positive value) is greater than k
  All other pairs result in non-positive products which can't exceed a positive k.

Code Example (Python) #

from collections import defaultdict

def find_valid_product_pairs(arr, k):
    # Count frequency of each element without modifying the original array
    freq = defaultdict(int)
    for num in arr:
        freq[num] += 1
    
    result = set()
    unique_nums = list(freq.keys())
    
    # Helper to add pairs in sorted order to avoid duplicates (e.g., (a,b) and (b,a) are same)
    def add_sorted_pair(a, b):
        if a > b:
            a, b = b, a
        result.add((a, b))
    
    if k < 0:
        # Handle non-negative pairs
        non_negatives = [num for num in unique_nums if num >= 0]
        positives = [num for num in non_negatives if num > 0]
        zeros_exist = 0 in freq
        
        # Positive-positive pairs
        for i in range(len(positives)):
            a = positives[i]
            # Add pair of same element if it appears at least twice
            if freq[a] >= 2:
                add_sorted_pair(a, a)
            # Add pairs with other positives
            for j in range(i + 1, len(positives)):
                b = positives[j]
                add_sorted_pair(a, b)
        
        # Positive-zero pairs
        if positives and zeros_exist:
            for num in positives:
                add_sorted_pair(num, 0)
        
        # Zero-zero pair
        if zeros_exist and freq[0] >= 2:
            add_sorted_pair(0, 0)
        
        # Negative-negative pairs
        negatives = [num for num in unique_nums if num < 0]
        for i in range(len(negatives)):
            a = negatives[i]
            if freq[a] >= 2:
                add_sorted_pair(a, a)
            for j in range(i + 1, len(negatives)):
                b = negatives[j]
                add_sorted_pair(a, b)
        
        # Negative-positive pairs where product > k
        for pos in positives:
            for neg in negatives:
                if pos * neg > k:
                    add_sorted_pair(pos, neg)
    
    elif k == 0:
        # Positive-positive pairs
        positives = [num for num in unique_nums if num > 0]
        for i in range(len(positives)):
            a = positives[i]
            if freq[a] >= 2:
                add_sorted_pair(a, a)
            for j in range(i + 1, len(positives)):
                b = positives[j]
                add_sorted_pair(a, b)
        
        # Negative-negative pairs
        negatives = [num for num in unique_nums if num < 0]
        for i in range(len(negatives)):
            a = negatives[i]
            if freq[a] >= 2:
                add_sorted_pair(a, a)
            for j in range(i + 1, len(negatives)):
                b = negatives[j]
                add_sorted_pair(a, b)
    
    else:  # k > 0
        # Positive-positive pairs with product > k
        positives = [num for num in unique_nums if num > 0]
        for i in range(len(positives)):
            a = positives[i]
            if freq[a] >= 2 and a * a > k:
                add_sorted_pair(a, a)
            for j in range(i + 1, len(positives)):
                b = positives[j]
                if a * b > k:
                    add_sorted_pair(a, b)
        
        # Negative-negative pairs with product > k
        negatives = [num for num in unique_nums if num < 0]
        for i in range(len(negatives)):
            a = negatives[i]
            if freq[a] >= 2 and a * a > k:
                add_sorted_pair(a, a)
            for j in range(i + 1, len(negatives)):
                b = negatives[j]
                if a * b > k:
                    add_sorted_pair(a, b)
    
    return list(result)

Time Complexity Analysis #

• Frequency counting: Runs in O(n) time, where n is the length of the input array.
• Pair checking: We only iterate over unique elements (let's call this count m, where m ≤ n). The worst-case scenario is when all elements are unique (m = n), leading to O(n²) time. However, if there are many duplicate elements, m is much smaller than n, making the time complexity significantly lower than O(n²) — which meets the problem's requirement.

Why This Works #

By using a frequency map, we avoid modifying the original array and eliminate redundant checks for duplicate elements. The sorted pair helper ensures we don't count (a,b) and (b,a) as separate pairs, keeping our result set unique.

内容的提问来源于stack exchange，提问作者Nishant Garg