Count pairs in list of integers such that their addition is equal to the input value

Question

Given a List<int>, the problem I am trying to solve is: Find the number of unique pairs in List<int> such that their addition is exactly equal to the input value.

The bottleneck is a nested for() loop that I have used to go through the list

// *** OPTIMIZE THIS LOOP ***
for (int i = 0; i < intList.Count - 1; i++)
{
 for (int j = i + 1; j < intList.Count; j++) 
 {
 if ((intList[i] + intList[j] == totalValue) && 
 IsPairUnique(intList[i], intList[j]) == true)
 {
 nCombinations++;
 }
 }
}

How can this be made better for performance? I understand 'better' is a subjective word and has no real meaning as such. For a List<int> of size 50000 the code takes about 18 seconds on one of my VM. For 500000 it's way too worst. So, here by 'better' I mean 'faster'. Clearly this problem deserves much less than 18 seconds to solve in my opinion. With 1 Parallel.For() I have managed to get the loop time to 10-11 seconds, but I have a feeling that this whole algorithm needs a fresh set of eyes to look at.

Parallel.For(0, intList.Count - 1,
 i => 
 { 
 for (int j = i + 1; j < intList.Count; j++)
 {
 if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
 { 
 nCombinations++;
 }
 }
 });

How can I speed this up? Full code from my console application is as below:

class TestClass
{
 static List<int> compareList = new List<int>();
// GetPossibleCombination method.
// This method finds out the unique number of possible combinations where 
// addition of any 2 values from the list is exactly equal to 'totalValue'
static int GetPossibleCombinations(List<int> intList, long totalValue)
{
 // handle edge conditions
 if (intList == null || 
 intList.Count == 0 || 
 intList.Count > 500000 || 
 totalValue > 5000000000)
 return 0;
 compareList.Clear();
 int nCombinations = 0;
 // *** OPTIMIZE THIS LOOP ***
 for (int i = 0; i < intList.Count - 1; i++)
 {
 for (int j = i + 1; j < intList.Count; j++) // start from this element onwards
 {
 if ((intList[i] + intList[j] == totalValue) && IsPairUnique(intList[i], intList[j]) == true)
 {
 nCombinations++;
 }
 }
 }
 return nCombinations;
}
// This method creates a list of possible values we have 
static bool IsPairUnique(int v1, int v2)
{
 if (compareList.Contains(v1 * 10 + v2) == true || compareList.Contains(v2 * 10 + v1) == true)
 return false;
 else
 {
 // else add a new one
 compareList.Add(v1 * 10 + v2);
 compareList.Add(v2 * 10 + v1);
 }
 return true;
}
static void Main(string[] args)
{ 
 int intListSize = 50000; // Optimize it for numbers upto 500,000
 long totalValue = 5000;
 List<int> intList = new List<int>();
 Random r = new Random();
 for (int i = 0; i < intListSize; i++)
 { 
 intList.Add(r.Next(0, 10000)); // populate random values.
 }
 Stopwatch sw = new Stopwatch();
 sw.Start();
 // Find the number of unique pairs in 'intList' such that 
 // their addition is exactly equal to 'totalValue'
 int res = GetPossibleCombinations(intList, totalValue);
 sw.Stop();
 Console.WriteLine(sw.Elapsed.ToString());
 }
}

• Oh My Goodness: Does "unique pairs" mean "unique indexes", "unique values", or "unique combinations of values"? For example: if the data is 1, 1, 1 and the input value is 2, do we have zero, one or three unique pairs?
• silverspoon: @OhMyGoodness, "unique pairs" mean "unique combinations of values" from the list. e.g.: If 'totalValue' we are looking for is 5 and the value at list[i] is 2, list[i+1] is 3 and list[j] 3, list[j+1] is 2 then only one pair (either i, i+1 or j, j+1) should be considered. Hope this helps.

Answer 1

The solution has a quadratic time complexity. If it solves the 50000-strong list in 18 seconds, I'd expect about 1800 seconds (aka 30 minutes) for a 500000 one. Notice that the problem is aggravated by the way you are looking for duplicates (and IsPairUnique doesn't look correct; it is prone to false positives).

There are few standard ways to bring the complexity down.

• Sort the list. Arrange two iterators, one at the beginning, another at the end.

  Now add the pointed elements. If the sum is less than the target, advance the left one. If it is greater, move the right one toward the beginning. If it is a target, record it, and move both. In any case, when moving an iterator, skip duplicates. Rinse and repeat until they met.

• If you have enough extra memory, put them in a set. For each element in a set check if its complement is also there.

• Oh My Goodness: The set approach won't detect 1+1=2
• mabako: You could very well keep track of how many entries with a value of totalValue/2 you have (if totalValue is even) - if you have 2+ entries, count it as an additional pair. For all other numbers, it doesn't matter how many of them you've seen.