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