Two Sum Problem Analysis 2: Not Unique and No Duplicates

Overview

Here in this post, I would like to give some more analysis on the cases where there could be zero solution, one solution or multiple solutions and you are asked to find all of the  (copyright @sigmainfy) possible candidate index pairs such that their sum equal to the given target! To avoid overwhelming stuff, for now I still assume there are no duplicates in the input, I will discuss how to handling duplicates in the input which is the most complicated issue in a third post  “Two Sum Problem Analysis 3: Handling Duplicates Input”  for this series of two sum problem analysis.

Two Sum Problem

Similar to the description in the last post but pay attention to the bold line where we have different assumptions for this problem

Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum should return all such indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input would have no duplicates in the input but there could be multiple possible pairs. The pairs should be ordered by the increasing order of the first index in the pair. Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

Two Sum Problem Solution Analysis

As not difficult to see, for input without any duplicates, there still could be multiple or no solutions on the other hand for the two sum problem. For example, for the input: 1, 2, 8, 9 with the target 10, we have (1, 4) (2, 3) as our solutions (note we need the index pair rather than value pairs in our setting).

The most complicated case would be duplicates exist in the input, but I purposely simplify this for now and assume there are no duplicates which would be handled in my third post about two sum problem, you can imagine it a bit by considering the extreme case where there are 100 elements with the same value 1 and the target is 2, we won’t go any deeper for this in this post and now let’s consider the case where there are no duplicates.

It turns out to be still simple to come up with the approaches based on those basic method discussed in “Two Sum Problem Analysis 1: Sort and Hash with unique solution“, and there turns out to be very small modifications to achieve to get all the possible pairs, because it is not difficult, I will leave the detail for the reader themselves but directly give the core implementation here:

1) For the sort approach, replace the core while loop with the following, then you can find all the pairs in the vector structure you declare, pay close attention to the difference when we encounter some pair the sum of which is equal to the target, rather than break directly we now need to move both the head and tail (copyright @sigmainfy) pointer by one step and continue to search:

vector< vecto<int> > vecResultIndexes;
			 while (i < j) {
				 sum = number_structs[i].first + number_structs[j].first;
				 if (sum < target) ++i;
				 else if (sum > target) --j;
				 else {
					 reali = number_structs[i].second + 1, realj = number_structs[j].second + 1;
					 idxes[0] = min(reali, realj);
					 idxes[1] = max(reali, realj);
					 vecResultIndexes.push_back(idxes);
					 ++i, --j;
				 }
			 }

2) For the hash approach, the idea is the same, when we got some pairs the sum of which are equal to target, we need to continue rather than break directly as the following code shows:

vector< vecto<int> > vecResultIndexes;
			 unordered_map<int, int> number_indexes;
			 int len = numbers.size();

			 for (int i = 0; i < len; ++i) 
                 number_indexes[numbers[i]] = i;

			 for (int i = 0; i < len; ++i) {
				 auto it = number_indexes.find(target - numbers[i]);
				 if (it != number_indexes.end()) {
					 if (it->second <= i) 
                         continue;

					 idxes[0] = i + 1;
					 idxes[1] = it->second;
					 vecResultIndexes.push_back(idxes);
				 }
			 }

Remarks: note the time complexity are still same For both the sort and hash, we could achieve this because we assume there are no duplicates in the input, if there indeed are duplicates, this kind of worst time complexity would not be possible as far as I know, I will discuss this soon in my third post, regard this just as a warm up preparing for the most complicated ones.

Summary

In my last post: “Two Sum Problem Analysis 1: Sort and Hash with unique solution“, I have already given analysis on the original classic two sum problem but with the assumption that there is a unique solution. As we know, it is a quite big assumption and simplifies things too much. In this post, I remove that assumption but still assume no duplicates in the input and give out the modified version to find all the pairs. I will give a third (copyright @sigmainfy) post to discuss ever more complicated cases where there are duplicates, and I will try to show we could only achieve O(N^2) approaches.

Written on September 21, 2014