Find all the pairs in a given ordered set of numbers whose sum is equal to a given input sum

In this problem, we will be given a sorted set of numbers and a number, we need to print all the pairs available in the set whose sum is equal to the given number. For example, if we are given a set of numbers [1,2,5,6,7, 9,11,48,64, 84] and the sum is 8 - the output should be 1,7 2,6 since these are the only "pairs" of numbers which produce the given sum 8 among the numbers in the set.

This problem is similar to the other example Find all the pairs in a given unordered set of numbers whose sum is equal to a given input sum, except that in this case the given input is actually a sorted set instead of an unordered set.

Since we already know that the set is sorted in some order (ascending or descending), we can use our low-high approach we used in sorting the unordered set of binary numbers, where the low represents the starting indexes and high represents the ending indexes. As we move the low and high against each other we can find out which pair matches the given sum as we move.

Logic:

The approach goes as below:

  1. declare pointers low = 0, high = length (numbers) -1
  2. loop till low < high
  3. find the sum of numbers at low and high
  4. if the produced sum is less than expected, means that the sum should be on the higher side – so move the low towards right
  5. if the produced sum is higher than expected, means that the sum should be on the lesser side – so move the high towards left
  6. if the produced sum is equal to the expected, add this pair (low, high) to our output pairs and move the low and high indexes

Code in C#:

        public void DoFindPairsForSumOrdered(
          int[] arrayOfNumbers, 
          int expectedSum)
        {
            List<KeyValuePair<int, int>> expectedSumPairs 
              = new List<KeyValuePair<int, int>>();
            int low = 0, high = arrayOfNumbers.Length - 1;
            while (low < high)
            {
                int sum = arrayOfNumbers[low] + arrayOfNumbers[high];
                if (sum == expectedSum)
                {
                    expectedSumPairs.Add(
                        new KeyValuePair<int, int>(arrayOfNumbers[low], arrayOfNumbers[high]));
                    low++; high--;
                }
                else if (sum > expectedSum)
                {
                    high--;
                }
                else if (sum < expectedSum)
                {
                    low++;
                }
            }

            foreach (var item in expectedSumPairs)
            {
                Console.WriteLine($"{item.Key},{item.Value}");
            }
        }

*This problem is based on the question used in Google Example Coding Interview Video

Ram
Ram

I'm a full-stack developer and a software enthusiast who likes to play around with cloud and tech stack out of curiosity. You can connect with me on Medium, Twitter or LinkedIn.

Privacy Overview
Referbruv

This website uses cookies so that we can provide you with the best user experience possible. Cookie information is stored in your browser and performs functions such as recognising you when you return to our website and helping our team to understand which sections of the website you find most interesting and useful.

Strictly Necessary Cookies

Strictly Necessary Cookie should be enabled at all times so that we can save your preferences for cookie settings.

3rd Party Cookies

This website uses Google Analytics to collect anonymous information such as the number of visitors to the site, and the most popular pages.

Keeping this cookie enabled helps us to improve our website.