Pair Sum in a Sorted and Rotated Array

Given an array arr[] of size n, which is sorted and then rotated around an unknown pivot, the task is to check whether there exists a pair of elements in the array whose sum is equal to a given target value.

Examples : 

Input: arr[] = [11, 15, 6, 8, 9, 10], target = 16
Output: true
Explanation: There is a pair (6, 10) with sum 16.

Input: arr[] = [11, 11, 15, 26, 38, 9, 10], target = 35
Output: true
Explanation: There is a pair (26, 9) with sum 35.

Input: arr[] = [9, 10, 10, 11, 15, 26, 38], target = 45
Output: false
Explanation: There is no pair with sum 45.

[Naive Approach] Using Hashing - O(n) Time and O(n) Space

We have discussed different solutions for finding a pair with given sum in an array (not sorted). The best complexities we can achieve is O(n) Time and O(n) auxiliary space in the hashing based solution.

// C++ code to check whether any pair exists // whose sum is equal to the given target value #include <iostream> #include <vector> #include <unordered_set> using namespace std; bool pairInSortedRotated(vector<int> &arr, int target){  unordered_set<int> s;  for (int i = 0; i < arr.size(); i++){  // Calculate the complement that added to  // arr[i], equals the target  int complement = target - arr[i];  // Check if the complement exists in the set  if (s.find(complement) != s.end())  return true;  // Add the current element to the set  s.insert(arr[i]);  }    // If no pair is found  return false; } int main(){  vector<int> arr = {11, 15, 6, 8, 9, 10};  int target = 16;  if (pairInSortedRotated(arr, target))  cout << "true";  else  cout << "false";  return 0; } 

// Java code to check whether any pair exists // whose sum is equal to the given target value import java.util.HashSet; class GfG {  static boolean pairInSortedRotated(int[] arr, int target){  HashSet<Integer> set = new HashSet<>();  for (int i = 0; i < arr.length; i++) {  // Calculate the complement that added to  // arr[i], equals the target  int complement = target - arr[i];  // Check if the complement exists in the set  if (set.contains(complement)) {  return true;  }  // Add the current element to the set  set.add(arr[i]);  }    // If no pair is found  return false;  }  public static void main(String[] args) {  int[] arr = {11, 15, 6, 8, 9, 10};  int target = 16;  if (pairInSortedRotated(arr, target))  System.out.println("true");  else  System.out.println("false");  } } 

# Python3 code to check whether any pair exists # whose sum is equal to the given target value def pairInSortedRotated(arr, target): s = set() for num in arr: # Calculate the complement that added to # num, equals the target complement = target - num # Check if the complement exists in the set if complement in s: return True # Add the current element to the set s.add(num) # If no pair is found return False if __name__ == "__main__": arr = [11, 15, 6, 8, 9, 10] target = 16 if pairInSortedRotated(arr, target): print("true") else: print("false") 

// C# code to check whether any pair exists // whose sum is equal to the given target value using System; using System.Collections.Generic; class GfG {  static bool pairInSortedRotated(int[] arr, int target){  HashSet<int> set = new HashSet<int>();  for (int i = 0; i < arr.Length; i++) {  // Calculate the complement that added to  // arr[i], equals the target  int complement = target - arr[i];  // Check if the complement exists in the set  if (set.Contains(complement))  return true;  // Add the current element to the set  set.Add(arr[i]);  }  // If no pair is found  return false;  }  static void Main(){  int[] arr = {11, 15, 6, 8, 9, 10};  int target = 16;  if (pairInSortedRotated(arr, target))  Console.WriteLine("true");  else   Console.WriteLine("false");   } } 

// Javascript code to check whether any pair exists // whose sum is equal to the given target value function pairInSortedRotated(arr, target) {  let set = new Set();  for (let num of arr) {    // Calculate the complement that added to  // num, equals the target  let complement = target - num;  // Check if the complement exists in the set  if (set.has(complement)) {  return true;  }  // Add the current element to the set  set.add(num);  }  // If no pair is found  return false; } // Driver Code let arr = [11, 15, 6, 8, 9, 10]; let target = 16; if (pairInSortedRotated(arr, target))  console.log("true"); else   console.log("false"); 

true

[Expected Approach] Two Pointer Technique - O(n) Time and O(1) Space

First find the largest element in an array which is the pivot point. The element just after the largest element is the smallest element. Once we have the indices of the largest and the smallest elements, we use two pointer technique to find the pair.

• Set the left pointer(l) to the smallest value and the right pointer(r) to the highest value.
• To handle the circular nature of the rotated array, we will use the modulo operation with the array size.
• While l ! = r, we shall keep checking if arr[l] + arr[r] = target.
  • If arr[l] + arr[r] > target, update r = (r - 1 + n) % n.
  • If arr[l] + arr[r] < target, update l = (l + 1) % n.
  • If arr[l] + arr[r] = target, then return true.
• If no such pair is found after the iteration is complete, return false.

// Cpp program to find a Pair Sum in a Sorted  // and Rotated Array using Two Pointer Technique #include <iostream> #include <vector> using namespace std; bool pairInSortedRotated(vector<int>& arr, int target) {  int n = arr.size();  // Find the pivot element  int i;  for (i = 0; i < n - 1; i++)  if (arr[i] > arr[i + 1])  break;   // l is now index of smallest element  int l = (i + 1) % n;  // r is now index of largest element  int r = i;  // Keep moving either l or r till they meet  while (l != r) {  // If we find a pair with sum target, return true  if (arr[l] + arr[r] == target)  return true;  // If current pair sum is less, move to higher sum  if (arr[l] + arr[r] < target)  l = (l + 1) % n;  // Move to lower sum  else  r = (r - 1 + n) % n;  }  return false; } int main() {  vector<int> arr = {11, 15, 6, 8, 9, 10};  int target = 16;  if (pairInSortedRotated(arr, target))  cout << "true";  else  cout << "false";  return 0; } 

// Java program to find a Pair Sum in a Sorted  // and Rotated Array using Two Pointer Technique class GfG {  static boolean pairInSortedRotated(int[] arr, int target) {  int n = arr.length;  // Find the pivot element  int i;  for (i = 0; i < n - 1; i++)  if (arr[i] > arr[i + 1])  break;  // l is now index of smallest element  int l = (i + 1) % n;  // r is now index of largest element  int r = i;  // Keep moving either l or r till they meet  while (l != r) {  // If we find a pair with sum target, return true  if (arr[l] + arr[r] == target)  return true;  // If current pair sum is less, move to higher sum  if (arr[l] + arr[r] < target)  l = (l + 1) % n;  // Move to lower sum side  else  r = (r - 1 + n) % n;  }  return false;  }  public static void main(String[] args) {  int[] arr = {11, 15, 6, 8, 9, 10};  int target = 16;  if (pairInSortedRotated(arr, target))  System.out.println("true");  else  System.out.println("false");  } } 

# Python program to find a Pair Sum in a Sorted  # and Rotated Array using Two Pointer Technique def pairInSortedRotated(arr, target): n = len(arr) # Find the pivot element i = 0 for i in range(n - 1): if arr[i] > arr[i + 1]: break # if whole array is sorted max # element will be at last index if arr[i] <= arr[i + 1]: i += 1 # l is now index of smallest element l = (i + 1) % n # r is now index of largest element r = i # Keep moving either l or r till they meet while l != r: # If we find a pair with sum target, return true if arr[l] + arr[r] == target: return True # If current pair sum is less, move to higher sum if arr[l] + arr[r] < target: l = (l + 1) % n # Move to lower sum side else: r = (r - 1 + n) % n return False if __name__ == "__main__": arr = [11, 15, 6, 8, 9, 10] target = 16 if pairInSortedRotated(arr, target): print("true") else: print("false") 

// C# program to find a Pair Sum in a Sorted  // and Rotated Array using Two Pointer Technique using System; using System.Collections.Generic; class GfG {  static bool pairInSortedRotated(int[] arr, int target) {  int n = arr.Length;  // Find the pivot element  int i;  for (i = 0; i < n - 1; i++)  if (arr[i] > arr[i + 1])  break;  // l is now index of smallest element  int l = (i + 1) % n;  // r is now index of largest element  int r = i;  // Keep moving either l or r till they meet  while (l != r) {  // If we find a pair with sum target, return true  if (arr[l] + arr[r] == target)  return true;  // If current pair sum is less, move to higher sum  if (arr[l] + arr[r] < target)  l = (l + 1) % n;  // Move to lower sum side  else  r = (r - 1 + n) % n;  }  return false;  }  static void Main() {  int[] arr = { 11, 15, 6, 8, 9, 10 };  int target = 16;  if (pairInSortedRotated(arr, target))  Console.WriteLine("true");  else  Console.WriteLine("false");  } } 

// JavaScript program to find a Pair Sum in a Sorted  // and Rotated Array using Two Pointer Technique function pairInSortedRotated(arr, target) {  let n = arr.length;  // Find the pivot element  let i;  for (i = 0; i < n - 1; i++)  if (arr[i] > arr[i + 1])  break;  // l is now index of smallest element  let l = (i + 1) % n;  // r is now index of largest element  let r = i;  // Keep moving either l or r till they meet  while (l !== r) {  // If we find a pair with sum target, return true  if (arr[l] + arr[r] === target)  return true;  // If current pair sum is less, move to higher sum  if (arr[l] + arr[r] < target)  l = (l + 1) % n;  // Move to lower sum side  else  r = (r - 1 + n) % n;  }  return false; } // Driver Code let arr = [11, 15, 6, 8, 9, 10]; let target = 16; if (pairInSortedRotated(arr, target))  console.log("true"); else  console.log("false"); 

true

Time Complexity: O(n)
Auxiliary Space: O(1)

Further Optimization : The above implementation find the pivot point using a linear search in O(n) Time. We can find the pivot point using Binary Search in O(Log n). Please refer Search in a sorted and rotated array for details. Please note that the overall time complexity remains same as we run a linear time two pointer algorithms after finding the pivot point.