1. Key Pair

Problem Statement

Given an array of integers and a target value elem, determine whether at least one pair of elements exists whose sum equals the target. If such a pair exists, print it; otherwise print "No pairs found!".

Pattern Used

Two Pointers (after sorting)

Approach (High-level)

• Sort the array
• Use two pointers (low, high) to evaluate pair sums
• Move pointers based on comparison with the target value

Time & Space Complexity

• Brute Force (commented): O(n²)
• Optimized (used): O(n log n)
• Space: O(1)

LeetCode

• 1. Two Sum
• https://leetcode.com/problems/two-sum/

// T.C->O(n^2)
// int findkeyPair(int arr[], int n, int elem) {
//   for (int i = 0; i < n; i++) { // Fixed the loop condition
//     for (int j = i + 1; j < n; j++) { // Avoid duplicate pairs by starting j from i + 1
//       if (arr[i] + arr[j] == elem) {
//         cout << "Pairs are: " << arr[i] << " " << arr[j] << endl;
//       }
//     }
//   }
// }

// T.C->O(n log n)
void findkeyPair(int arr[], int n, int elem) {
    sort(arr, arr + n); // Sort the array

    // cout << "Sorted Array: ";
    // for (int i = 0; i < n; i++) {
    //     cout << arr[i] << " ";
    // }
    // cout << endl;

    int low = 0;
    int high = n - 1;

    while (low < high) { // Fixed condition
        int currentSum = arr[low] + arr[high];
        if (currentSum == elem) {
            cout << "Pairs are: " << arr[low] << " and " << arr[high] << endl;
            return; // Exit after finding one pair (optional, depending on requirements)
        }
        // If currentSum is greater than the target, decrement high
        else if (currentSum > elem) {
            high--;
        }
        // If currentSum is less than the target, increment low
        else {
            low++;
        }
    }

    cout << "No pairs found!" << endl; // If no pair is found
}

2. Find Pivot Index

Problem Statement

Given an integer array, return the pivot index where the sum of all elements strictly to the left equals the sum of all elements strictly to the right.