Find a pair with given sum in a rotated sorted array

There is an integer array nums which is sorted in ascending order (with distinct values).

nums is rotated at an unknown pivot index k (1<= k < nums.length) such that the resulting array is
[nums[k], nums[k+1], … , nums[n-1], nums[0], nums[1], … , nums[k-1]] (0 indexed).

For example, [0,1,2,4,5,6,7] rotated at pivot index 3 become [4,5,6,7,0,1,2]

Given the array nums after the possible rotation and a target sum, the task is to check if the array has a pair of elements with the given target sum.

Input: arr[] = {11, 15, 6, 8, 9, 10}, X = 16

Output: true

Explanation: There is a pair (6, 10) with sum 16

Approach

This can be solved using two pointer and binary search approach.

To understand the solution of the above problem first we need to understand how to find if the array has a pair of elements with the given target sum when the array is simply sorted and not rotated. Let's understand with the help of the example.

Let the array be : {6, 8, 9, 10, 11, 15} and the target sum be : 16

Step 1 : Initialize two pointers namely right and left at the right and left end of the array (Highest and lowest element) respectively.

Step 2 : Check if the value array[left] + array[right] is equal to the target sum. If it is equal to target sum then it is the answer pair we are looking for.

Here, 6+15 = 21 is not equal to 16

Step 3 : Else if array[left] + array[right] > target sum, then decrement the right pointer such that right = right - 1.

Else if array[left] + array[right] < target sum, then increment the left pointer such that left = left + 1.

As, 6+15 > 16

6+11 > 16

6+10 = 16.

Hence, the answer pair is {6,10}

Step 4 : While traversing if the left and right pointer points to the same element, It indicates that no such pair exists in the given array.

This same two pointer method can be applied to the rotated sorted array with slight modifications.

Find the pivot element.
Find the answer pair.

Find the pivot element

Pivot element is the element around which the array is rotated.

In the example array :

The pivot element is 6.

Steps to find the pivot element are :

Traverse the array from first to the last element of the array until the condition array[i] > array[i+1] is true.
For the i, where array[i] > array[i+1], pivot = i+1.
If no such element is found then it indicates that the array is sorted and not rotated.

Find the answer pair

Initialize two pointers left = pivot and right = pivot - 1.
Loop through the array and check if the sum of the elements at the left and right pointers is equal to the given sum. If it is, then return true.
If the sum is less than the given sum, increment the left pointer, else decrement the right pointer.
If the loop completes ( left = right ) and no pair is found, return false.

Complexity

Time Complexity: O(n), where n is the length of the input array.
Space Complexity: O(1)

Java Code

import java.util.*;

class FindPairInRotatedArray {

    public static boolean findPair(int[] arr, int x) {
        // length of array
        int n = arr.length;

        // find pivot element
        int pivot = 0;
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                pivot = i + 1;
                break;
            }
        }

        int left = pivot;
        int right = pivot - 1;

        while (left != right) {
            if (arr[left] + arr[right] == x) {
                return true;
            } else if (arr[left] + arr[right] < x) {
                left = (left + 1) % n;
            } else {
                right = (right - 1 + n) % n;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {13, 17, 4, 7, 9, 12};
        int x = 17;
        System.out.println("Input array: " + Arrays.toString(arr));
        System.out.println("Given sum: " + x);
        System.out.println("Pair with give sum exists: " + findPair(arr, x));
    }
}

Output

Input array: [13, 17, 4, 7, 9, 12]
Given sum: 17
Pair with give sum exists: true

Dislike

Thanks for feedback.