Given a circularly sorted array of integers, 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,
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). 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 element in the array 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 a 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
|
#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 sum)
{
// find the pivot element
int pivot = findPivot(arr, n);
// maintain two pointers `low` and `high`.
// high points to an index of maximum element in the array
int high = pivot – 1;
// low points to an index of minimum element in the array
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] == sum)
{
printf(“Pair found (%d, %d)”, arr[low], arr[high]);
return;
}
// increment `low` index if total is less than the desired sum
if (arr[low] + arr[high] < sum) {
low = (low + 1) % n;
}
// decrement `high` index if 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 sum = 18;
findPair(arr, n, sum);
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
|
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 sum)
{
// find the pivot element
int pivot = findPivot(arr);
// maintain two pointers `low` and `high`.
// high points to an index of maximum element in the array
int high = pivot – 1;
// low points to an index of minimum element in the array
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] == sum)
{
System.out.printf(“Pair found (%d, %d)”, arr[low], arr[high]);
return;
}
// increment `low` index if total is less than the desired sum
if (arr[low] + arr[high] < sum) {
low = (low + 1) % arr.length;
}
// decrement `high` index if 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 sum = 18;
findPair(arr, sum);
}
}
|
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
|
# 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 pair with the given sum in a circularly sorted array
def findPair(arr, sum):
# find the pivot element
pivot = findPivot(arr)
”’ maintain two pointers `low` and `high` ”’
# high points to an index of maximum element in the array
high = pivot – 1
# low points to an index of minimum element in the array
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] == sum:
print(f‘Pair found ({arr[low]}, {arr[high]})’)
return
# increment `low` index if total is less than the desired sum
if arr[low] + arr[high] < sum:
low = (low + 1) % len(arr)
# decrement `high` index if 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 ]
sum = 18
findPair(arr, sum)
|
Output:
Pair found (3, 15)
Download Run Code
Output:
Pair found (3, 15)
Download Run Code
Output:
Pair found (3, 15)
Download Run Code
Output:
Pair found (3, 15)
The time complexity of the above solution is O(n), and the auxiliary space used by the program is O(1).
source