Find Out Pairs with given sum in an array in python of time complexity O(n log n)- FACEBOOK,AMAZON

Introduction

This tutorial will guide you through the process of finding pairs in an array that sum to a given target value using Python. We will focus on achieving a time complexity of O(n log n), making it efficient for large datasets. This method is particularly useful for technical interviews or applications in data structures.

Step 1: Understand the Problem

Before diving into coding, clarify the problem:

• Given an array of integers and a target sum, identify all unique pairs of numbers that add up to the target.
• For example, with an array [1, 2, 3, 4, 5] and a target sum of 6, the pairs would be (1, 5) and (2, 4).

Step 2: Sort the Array

Sorting the array is crucial for applying the two-pointer technique. Here's how to do it:

1. Use the built-in sort() method in Python.
2. This step will allow us to efficiently find pairs since we can traverse from both ends of the sorted array.

arr = [1, 2, 3, 4, 5]
arr.sort()  # Now arr is [1, 2, 3, 4, 5]

Step 3: Implement the Two-Pointer Technique

Now that the array is sorted, follow these steps to find the pairs:

1. Initialize two pointers:

   • left at the start (index 0).
   • right at the end (last index).

2. Use a loop to check the sum of the elements at these pointers:

   • If the sum equals the target, save the pair and move both pointers inward.
   • If the sum is less than the target, move the left pointer to the right to increase the sum.
   • If the sum is greater than the target, move the right pointer to the left to decrease the sum.

Here's the code for this logic:

def find_pairs_with_sum(arr, target):
    arr.sort()
    left, right = 0, len(arr) - 1
    pairs = []
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            pairs.append((arr[left], arr[right]))
            left += 1
            right -= 1
        elif current_sum < target:
            left += 1
        else:
            right -= 1
            
    return pairs

# Example usage
arr = [1, 2, 3, 4, 5]
target = 6
print(find_pairs_with_sum(arr, target))  # Output: [(1, 5), (2, 4)]

Step 4: Handle Edge Cases

While implementing the function, consider the following edge cases:

• Arrays with fewer than two elements should return an empty list since pairs cannot be formed.
• Duplicate values in the array should be handled according to the requirements (e.g., whether to include duplicates as separate pairs).

Conclusion

In this tutorial, you learned how to find pairs in an array that sum to a specific target using Python with a time complexity of O(n log n). The key steps included sorting the array and applying the two-pointer technique. This approach is efficient and effective for solving similar problems in interviews or real-world applications.

For further practice, consider implementing additional features or optimizations, such as handling duplicates or working with larger datasets. You can also explore the provided GitHub link for more examples and code references.