'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Last Updated: Jun 30, 2023
Easy

Given a Sorted and Rotated Array, Find if There is a Pair with a Given Sum

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

Before diving into the problem, let’s understand the concept behind the sorted and rotated array for a clear vision. 

Introduction to Given a Sorted and Rotated Array, Find if There is a Pair with a Given Sum

Unlike the standard arrays, the elements are stored in ascending or descending order in a sorted array.

For example:

Example of Sorted & Unsorted array

We all know rotating means shifting something from its original place to a specific location. Like in school days, we used to rotate( or shift) our seats the same way as we rotate the array elements in clockwise or anti-clockwise orientation. We can rotate the array elements as many times as we want. 
 

For example- Rahul has rotated the array 3 times, as shown below:

Rotation of arrays

This is how the rotation takes place in the case of arrays. Now, let’s figure out the approaches we can think of while dealing with the sorted and rotated arrays using the problem given below.

You are given a sorted array that has been rotated around an unknown point. Determine whether the array contains a pair with the supplied sum ‘X.’ It is reasonable to presume that all array elements are distinct.

Examples:

Input

arr[ ] = { 3, 6, 8, 16, 19 } 
X = 14 ( target sum )

Output

true

Explanation

The pair ( 6 , 8) with sum 14.
 

Input

arr[ ] = { 5, 8, 30, 90 }
X = 20 ( target sum )

Output

false

Explanation

No pair with sum 20.

It is recommended to try the stated problem on your own before proceeding with the solution.

Approaches

In this article, we will be looking forth into the two methods to encounter the stated problem.

  1. Brute force approach
  2. Two-pointer approach


Let’s start with the ideas:

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Method 1: Brute Force approach

A simple solution can be iterating over all the possible pairs then comparing the pair sum with the target sum. However, it is not an optimum approach because we are looping through all potential pairs, which increases the program’s time complexity.

We will need two loops to execute this approach where the outer one will pick one element, and the inner one will couple the selected element with all of its following elements one by one. Later on, the pair’s sum will be compared with the target sum. If matches, return 1, otherwise check for the next pair. Repeat this process until the end of the array is encountered. If no pair has a sum equivalent to the target sum, then return 0.

Let’s see the implementation of the above approach:

Implementation

C++

#include<bits/stdc++.h>
using namespace std;

void hasPairSum(int A[], int target, int n){
int sum=0;
for(auto i=0;i<n;i++){
    for(auto j=i+1;j<n;j++){
        sum = A[i]+A[j];
        // if matches the target sum
        if(sum == target){
            cout<<"A pair exists with the given target sum: "<<A[i]<<" and "<<A[j]<<"\n";
            return;
        }
    }
}
// if not found any pair
cout<<"There does not exist any pair with the given target sum\n";
return;
}

int main()
{
	int target,size;
	cout<<"Enter the target sum:\n";
	cin>>target;
	cout<<"Enter the size\n";
	cin>>size;
	int A[size];
	// User input
	cout<<"Enter the elements:\n";
	for(int i=0;i<size;i++){
		cin>>A[i];
	}
	hasPairSum(A,target,size);
	return 0; 
}

Input

Enter the target sum:
12
Enter the size
4
Enter the elements:
8 5 6 7

Output

A pair exists with the given target sum: 5 and 7

Explanation: We iterated through each element, then used an inner loop to build a pair with the elements afterwards. The pair was printed, and 1 was returned to the calling statement since the pair sum was equal to the desired target.

Pictorial Representation:

Pictorial Representation

Time Complexity:- O(n^2), where n is the number of elements. We have a poor solution since we employed two loops that run nearly equivalent through all elements.

Space Complexity:- O(1), i.e., constant space.

Must Read, Array Implementation of Queue and  Rabin Karp Algorithm

Method 2: Using a two-pointer approach

In general, A two-pointer strategy is an approach in which two pointers, as the name implies, point to some indexes. The first will point to the beginning of the array, while the second will point to the end. However, it is required for the array to be in a sorted form to implement the two-pointer approach.

two-pointer approach

These two pointers can now be used to loop through the elements of a sorted array. The method returns 1 if the total sum of the values at pointer1 and pointer2 equals the target sum. 

If the total is less than the target sum, the pointer 1 will be incremented by one.

sum <  target_sum condition

Pointer 2 will be decremented by one to reach the target if the total exceeds the target sum. 

sum > target_sum condition

This idea will be carried on until both the pointers collide.

To have a better understanding of the two-pointer technique, try implementing the described approach on your own.

This approach only applies to the sorted array. We can use the same method for rotated arrays but with some minor changes.

Approach for the rotated arrays:

The aim is to find the largest element in the array first, serving as the pivot point, and then the smallest element. We apply a similar approach in the middle procedure (as stated for the sorted array above) to see a pair. Once we have indexes for the largest and smallest items in an array, the only new update is that indexes are rotated when they are increased and decremented using modular arithmetic.

Algorithm:

Step 1:- Find the sorted and rotated array’s pivot element. The pivot element is the largest in the array. In a sorted and rotated array, the smallest element will be adjacent to the pivot element.

Step 2:- Use two pointers (for example, left and right), with the left pointing to the smallest element and the right referring to the largest.

Step 3:- Compare the pair sum with the target sum. If matches return 1, otherwise jump to step 4.

Step 4:-  If the pair sum is less than the target sum, then to increase the sum, move the left pointer to the next position by incrementing it rotationally.

Step 5:-  If the pair sum is greater than the target sum, then to decrease the sum, move the right pointer to the next position by decrementing it rotationally.

Step 6:- Repeat the 3,4 and 5 steps until both the pointers collide.

Implementation

#include <bits/stdc++.h>
using namespace std;

// This function returns true if arr[0..size-1] has a pair
// with sum equals to the target sum.

void pairInSortedRotated(int arr[], int n, int target)
{
	// Find the pivot(largest) element
	int i;
	for (i = 0; i < n - 1; i++)
    	if (arr[i] > arr[i + 1])
        	break;
	int low = (i + 1) % n; // l is now the index of smallest element
	int high = i;          // r is now index of largest element
	// Keep moving either low or high till they meet

	while (low != high)
	{
    	// return true if we find a pair satisfying the condition
    	if (arr[low] + arr[high] == target)
    	{
        	cout << "A pair exists with the given target sum: " << arr[low] << " and " << arr[high] << "\n";
        	return;
    	}
    	// If current pair sum is less, increment the low pointer
    	if (arr[low] + arr[high] < target)
        	low = (low + 1) % n;
    	// Move to the lower sum side
    	else
        	high = (n + high - 1) % n;
	}

	cout << "There does not exist any pair with the given target sum\n";
	return;
}

int main()
{
	int size, target;
	cout << "Enter the size of the array:\n";
	cin >> size;
	int arr[size];
	cout << "Enter the array elements:\n";
	for (int i = 0; i < size; i++)
	{
    	cin >> arr[i];
	}
	cout << "Enter the target sum:\n";
	cin >> target;

	pairInSortedRotated(arr, size, target);
	return 0;
}

Input

Enter the size of the array:
4
Enter the array elements:
8 5 6 7
Enter the target sum:
12

Output

A pair exists with the given target sum: 5 and 7

Time Complexity: O(n), where n is the number of elements. This solution can be optimized if the largest or pivot element is being searched using the binary search, which takes O(logn), however the overall time complexity will still be O(n) as we use the two-pointer approach.

Space Complexity:- O(1), i.e., constant space.

Pictorial Representation:

Pictorial Representation
Representation of array elements with conditions.

Try to implement the same approach for duplicate elements on your own.

Check out this array problem - Merge 2 Sorted Arrays

Frequently Asked Questions

What is a rotated array?

An array’s rotation simply means shifting the array’s elements to the specified places. We can rotate an array in both clockwise and anticlockwise ways. An array can be rotated an infinite number of times.

How do you find an element in a sorted and rotated array?

Using binary search, an element in a sorted array can be found in O(log n) time.

How many times can an array be rotated?

An array can be rotated an infinite number of times.

What is the two-pointer approach?

In the two-pointer approach, pointers refer to an array’s indexes. Using pointers, we can process two elements per loop instead of just one: two pointers, each starting from the beginning and the end until they collide. 

Conclusion

We learned about the different methods for finding the pair sum in a sorted and rotated array that matches the target sum in great detail to recap the subject. To have a better understanding, use your hands and tackle the given challenges on Coding Ninjas Studio. In addition, evaluate each technique and try to code in your preferred language.

Check out the following problems - 


Enroll in one of our top-notch courses to ensure a prosperous future.

Ninja, have fun learning! Happy Coding!

Previous article
The minimum number of elements to add to make median equals x
Next article
Segregate 0s and 1s in an Array
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass