Find a pair with the given sum in a circularly sorted array
Given a circularly sorted integer array, find a pair with a given sum. Assume there are no duplicates in the array, and the rotation is in an anti-clockwise direction around an unknown pivot.
For example,
Output: Pair found (3, 15)
Input: A[] = { 5, 8, 3, 2, 4 }, target = 12
Output: Pair found (4, 8)
Input: A[] = { 9, 15, 2, 3, 7 }, target = 20
Output: Pair not found
A simple solution would be to consider each pair in the given array and check if the desired sum is found. The problem with this approach is that its worst-case time complexity is O(n2), where n is the size of the input. This solution also does not take advantage of the fact that the array is circularly sorted.
We have already discussed the 2–pointer algorithm to find pairs with a given sum in a sorted array in O(n) time. We can extend this solution for circularly sorted arrays as well. We start by finding out the pivot element of the sorted sequence, which has a special property which no other array element have – both the next and previous element of the pivot element are greater than it.
The idea is to maintain two indices (low and high) that initially points to minimum and maximum elements in the array. Then loop till low becomes equal to the high index and reduce the search space at each iteration of the loop by comparing the sum of elements present at index low and high with the desired sum. Increment low if the sum is less than the expected sum; otherwise, decrement high if it is more than the desired sum. If the pair is found, return it.
Note that the indices are incremented and decremented in a rotational manner using modular arithmetic since the array is circularly rotated. The complete algorithm is demonstrated below in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <stdio.h> // Returns index of the pivot element in a circularly sorted array int findPivot(int arr[], int n) { for (int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) { return i + 1; } } return n; } // Function to find a pair with the given sum in a circularly sorted array void findPair(int arr[], int n, int target) { // base case if (n <= 1) { return; } // find the pivot element int pivot = findPivot(arr, n); // maintain two pointers, `low` and `high`. // `high` points to an index of the maximum array element int high = pivot - 1; // `low` points to an index of the minimum array element int low = pivot % n; /* Reduce search space at each iteration of the loop */ // loop till `low` becomes equal to `high` while (low != high) { // pair with the desired sum is found if (arr[low] + arr[high] == target) { printf("Pair found (%d, %d)", arr[low], arr[high]); return; } // increment `low` index if the total is less than the desired sum if (arr[low] + arr[high] < target) { low = (low + 1) % n; } // decrement `high` index if the total is more than the desired sum else { high = (high - 1 + n) % n; } } // Pair with the given sum doesn't exist in the array printf("Pair not found"); } int main(void) { int arr[] = { 10, 12, 15, 3, 6, 8, 9 }; int n = sizeof(arr) / sizeof(arr[0]); int target = 18; findPair(arr, n, target); return 0; } |
Output:
Pair found (3, 15)
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
class Main { // Returns index of the pivot element in a circularly sorted array public static int findPivot(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { if (arr[i] > arr[i + 1]) { return i + 1; } } return arr.length; } // Function to find a pair with the given sum in a circularly sorted array public static void findPair(int[] arr, int target) { // base case if (arr.length <= 1) { return; } // find the pivot element int pivot = findPivot(arr); // maintain two pointers, `low` and `high`. // `high` points to an index of the maximum array element int high = pivot - 1; // `low` points to an index of the minimum array element int low = pivot % arr.length; /* Reduce search space at each iteration of the loop */ // loop till `low` becomes equal to `high` while (low != high) { // pair with the desired sum is found if (arr[low] + arr[high] == target) { System.out.printf("Pair found (%d, %d)", arr[low], arr[high]); return; } // increment `low` index if the total is less than the desired sum if (arr[low] + arr[high] < target) { low = (low + 1) % arr.length; } // decrement `high` index if the total is more than the desired sum else { high = (high - 1 + arr.length) % arr.length; } } // Pair with the given sum doesn't exist in the array System.out.println("Pair not found"); } public static void main(String[] args) { int[] arr = { 10, 12, 15, 3, 6, 8, 9 }; int target = 18; findPair(arr, target); } } |
Output:
Pair found (3, 15)
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
# Returns index of the pivot element in a circularly sorted array def findPivot(arr): for i in range(len(arr) - 1): if arr[i] > arr[i + 1]: return i + 1 return len(arr) # Function to find a pair with the given sum in a circularly sorted array def findPair(arr, target): # base case if len(arr) <= 1: return # find the pivot element pivot = findPivot(arr) ''' maintain two pointers, `low` and `high` ''' # `high` points to an index of the maximum array element high = pivot - 1 # `low` points to an index of the minimum array element low = pivot % len(arr) ''' Reduce search space at each iteration of the loop ''' # loop till `low` becomes equal to `high` while low != high: # pair with the desired sum is found if arr[low] + arr[high] == target: print(f'Pair found ({arr[low]}, {arr[high]})') return # increment `low` index if the total is less than the desired sum if arr[low] + arr[high] < target: low = (low + 1) % len(arr) # decrement `high` index if the total is more than the desired sum else: high = (high - 1 + len(arr)) % len(arr) # Pair with a given sum that doesn't exist in the array print('Pair not found') if __name__ == '__main__': arr = [ 10, 12, 15, 3, 6, 8, 9 ] target = 18 findPair(arr, target) |
Output:
Pair found (3, 15)
The time complexity of the above solution is O(n) and doesn’t require any extra space.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)