algoadvance

You are given a 0-indexed integer array nums of length n and an integer target. Your task is to find the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.

Clarifying Questions

  1. What is the range and size of the nums array?
    • Typical constraints could vary, but let’s assume n can be between ( 2 ) and ( 10^5 ), and the elements of nums can vary between ( -10^9 ) and ( 10^9 ).
  2. What is the range of the target?
    • The target is likely to fall within the range of the sum of two extreme elements, i.e., (-2 \times 10^9) to ( 2 \times 10^9).
  3. Can the array contain duplicates?
    • Yes, the array can contain duplicate values.

Strategy

Let’s break down the strategy to solve this problem efficiently.

  1. Brute Force Approach: Loop through all pairs (i, j) and count the pairs where nums[i] + nums[j] < target. This approach has a time complexity of (O(n^2)), which is not efficient for large arrays.

  2. Optimized Approach:

    • Sorting and Two-Pointer Technique:
      • First, sort the array.
      • Use two pointers (left and right). Initially set left at the start (0) and right at the end (n-1) of the array.
      • If nums[left] + nums[right] < target, it implies all combinations from left to right-1 with nums[left] will also be less than target, allowing us to count more efficiently.

Code

Here is an efficient implementation using the optimized approach:

def count_pairs(nums, target):
    nums.sort()  # Sort the array first
    left, right = 0, len(nums) - 1
    count = 0
    
    while left < right:
        if nums[left] + nums[right] < target:
            # If nums[left] + nums[right] is less than target,
            # then all pairs (left, right), (left, right-1), ..., (left, left+1)
            # will also be less than target
            count += right - left
            left += 1
        else:
            right -= 1
    
    return count

# Example usage:
nums = [1, 2, 3, 4, 5]
target = 7
print(count_pairs(nums, target))  # Output: 7

Time Complexity

Overall, the time complexity of this approach is (O(n \log n)), which is efficient and suitable for large input sizes.

Feel free to ask further questions or for more clarification on any part of the solution!

Try our interview co-pilot at AlgoAdvance.com