Two Sum Sorted Editorial

Practice Problem Link: Two Sum Sorted

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a sorted array, check if there exist two numbers whose sum is zero.

Naive Approach

We loop over all pairs of elements in the array and check if we can find two numbers such that A[i] = -A[j]. If yes, return true, else return false.

 Analysis

• Time Complexity: O(n²)
• Space Complexity: O(1)

Implementation

C++

bool hasTwoSumZero(vector<int> A) {
	int n = A.size();
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {
			if(A[i] + A[j] == 0){
				return true;
			}
		}
	}
	return false;
}

Java

class Solution {
	boolean hasTwoSumZero (int[] A) {
		int n = A.length;
		for(int i = 0; i < n; i++) {
			for(int j = i + 1; j < n; j++) {
				if(A[i] + A[j] == 0){
					return true;
				}
			}
		}
		return false;
	}
}

Optimal Approach

Since it is told that the array is sorted, we will use the 2 pointers technique to solve this problem. We keep 2 pointers, pointing at either end of the array. If A[left] + A[right] = 0, we return true, if A[left] + A[right] > 0, we move the right pointer to the left by 1, else we move the left pointer to right by 1. We continue this, till the left pointer exceeds the right pointer.

Analysis

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

Implementation

C++

bool hasTwoSumZero(vector<int> A) {
	int n = A.size();
	int left = 0, right = n - 1;
	while(left < right) {
		if(A[left] + A[right] == 0) {
			return true;
		}
		else if(A[left] + A[right] > 0) {
			right--;
		}
		else {
			left++;
		}
	}
	return false;
}

Java

class Solution {
	boolean hasTwoSumZero (int[] A) {
		int n = A.length;
		int left = 0, right = n - 1;
		while(left < right) {
			if(A[left] + A[right] == 0) {
				return true;
			}
			else if(A[left] + A[right] > 0) {
				right--;
			}
			else {
				left++;
			}
		}
		return false;
	}
}