Two Number Sum with Time and Space complexity — Competitive Programming

Question 1 (Level — Easy)

Welcome to the competitive series of Code Wrestling. Today, we are gonna solve an easy problem, Two Number Sum.

We will find the Time and Space complexity of our solution and will also guide you to the process of finding an optimized solution.

Visit our YouTube channel for more interesting stuff Code Wrestling.

Video Link: Two Number Sum.

Github Repository Link: Github/TwoNumberSum

Go to the next question → Question — 2 (Validate Subsequence)

Code Wrestling

Question

Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. If any two numbers in the input array sum up to the target sum, the function should return them in an array, in any order. If no two numbers sum up to the target sum, the function should return an empty array.

Note that the target sum has to be obtained by summing two different integers in the array; you can’t add a single integer to itself in order to obtain the target sum.

Sample Input:

array = [3, 5, -4, 8, 11, 1, -1, 6]
targetSum = 10

Sample Output:

[-1, 11]

STOP HERE. And read the question again. Try to solve the question on your own and then proceed further to see our solution.

Solution

The objective here is to find two different numbers from the given array, such that their sum is equal to the target sum.

Solution 1 with time complexity O(n²) and space complexity O(n).

So a simple solution will be to loop over the array and find the sum of each number with every other number and check if the sum is equal to the target sum.

Approach:

For the given array: [3, 5, -4, 8, 11, 1, -1, 6].

1. First, take the first element (3 here), and now add it to every other element in the array (5, -4, 8, 11, 1, -1, 6) and check whether the sum is equal to the target sum.
2. If not then take the second element (5 here), and now add it to the remaining elements in the array (-4, 8, 11, 1, -1, 6), and check the sum.
3. If we find the number such that sum == targetSum, then return the elements by creating an array, otherwise repeat the above steps till we find the sum == targetSum or the number of elements is over.
4. If none of the elements found then return an empty array.

Below is the code snippet: (C#)

private int[] GetArrayWithSum(int[] arrayValues, int targetSum)
{
  // Time Complexity O(n^2)
  // Space Complexity O(1)
  for (int i = 0; i < arrayValues.Length - 1; i++)
  {
      for (int j = i + 1; j < arrayValues.Length; j++)
      {
          if (arrayValues[i] + arrayValues[j] == targetSum)
          {
             return new[] { arrayValues[i], arrayValues[j] };
          }
      }
  }
  return new int[] { };
}

Here the time complexity is O(n²) because of two for loops thus O(n * n) and thus O(n²) and space complexity is O(1).

This solution is simple but it has two for loops and thus is not a good one. Let’s see how we can optimize it. Can we remove one for loop?

Solution 2 with Time Complexity O(n) and Space Complexity O(n).

Let’s think of a way such that we can remove one for loop out of the two for loops.

Approach: (For array = [3, 5, -4, 8, 11, 1, -1, 6], and targetSum = 10)

Let’s keep a track of elements that we have already visited by storing them in some collection (List or Set or Dictionary).

The idea here is, we will go through each element of array, and find the difference between targetSum and currentElement. This will be the number that we need to have, let’s name it as requiredNumber. So we will check if this requiredNumber was already visited, because if it was visited that means it’s already present in our array and that’s our solution.

1. Loop over the array elements. Take the number (3, here), now find the difference i.e requiredNumber = (targetSum — currentNumber), (here, 10–3 => 7) now this is the number that we need to have.
2. If the requiredNumber is present in our already visited variable, then that’s our answer, if it’s not, then add your currentNumber (3, here) in already visited variable.
3. Now visited = [3], move to next number, i.e 5. Find the difference, so 10–5 = 5; now check if 5 is present in visited? No, it’s not. So add the currentNumber (5) to visited. So visited = [3,5].
4. Now next number, — 4, find the difference: 10 — ( — 4) = 14, is 14 present in visited? No, thus add currentNumber ( — 4) to visited. So visited = [3,5,-4].
5. Fast forward, visited = [3, 5, -4, 8, 11, 1], and next element is -1. Now find the difference: 10 — ( — 1) = 11. Is 11 present in visited? Yessssss, it is. Thus our solution is [11, -1]. So that’s the approach here.

Below is the code snippet: (C#)

private int[] GetArrayWithSum(int[] arrayValues, int targetSum)
{
    // Time Complexity = O(n)
    // Space Complexity = O(n)
    List<int> visitedValues = new List<int>();
    foreach (int number in arrayValues)
    {
        int requiredNumber = targetSum - number;
        if (visitedValues.Contains(requiredNumber))
        {
            return new[] { number, requiredNumber };
        }
        else
        {
            visitedValues.Add(number);
        }
    }
    return new int[] { };
}

Here the time complexity is O(n) because only one for loop and space complexity is O(n) because we are storing the visited numbers in a collection, thus O(n).

The solution is really good, but let’s see another solution where we will slightly increase the time complexity but will completely reduce the space complexity.

Solution 3 with Time Complexity O(n logn) and Space Complexity O(1).

Approach:

Let’s sort the array first. Use quickSort algorithm, which has a time complexity of O(n logn). Now after sorting the array, we will point to two elements in the array, a left element (L) and a right element (R). Initially, L is the leftmost element and R is the rightmost element. As the array is sorted moving from left to right will increase the number.

So calculate the sum of L’th element and the R’th element, if the sum is less than the target sum, increase L (move one step more towards right), because we need to increase sum, if the sum is more than the target sum, then we need to decrease R (move one step more towards left), because we need to decrease the sum, and if the sum is equal to target sum, that’s our solution.

Actual array = [3, 5, -4, 8, 11, 1, -1, 6]

1. Loop over the sorted array [-4, -1, 1, 3, 5, 6, 8, 11 ], make L as -4 and R as 11.
2. Calculate the sum, L + R => -4+ 11=> 7, So, 7 is less than targetSum (10), thus move L one step towards right i.e make L as -1.
3. Calculate the sum, L + R => -1+ 11=> 10. So, 10 is equal to targetSum, and hence is our final answer. [-1,11]

Below is the code snippet: (C#)

private int[] GetArrayWithSum(int[] arrayValues, int targetSum)
{
   // Time complexity O(nlogn)
   // Space complexity O(1)
   // QuickSort time complexity is O(nlogn)
   Array.Sort(arrayValues);  
   
   int left = 0;
   int right = arrayValues.Length - 1;
   // while loop complexity O(n)
   // together O(n + nlogn) => O(nlogn)
   
   while(left < right)
   {
      int sum = arrayValues[left] + arrayValues[right];
      if(sum < targetSum)
      {
         left++;
      }
      else if (sum > targetSum)
      {
         right--;
      }
      else
      {
         return new[] { arrayValues[left], arrayValues[right] };
      }
   }
   return new int[] { };
}

Here the time complexity is O(n logn) because the sorting has a time complexity of O(n logn) and the while loop has a complexity of O(n), now add both so O(n + n logn) => O(n logn) and space complexity is O(1).

Solve the next question → Question — 2 (Validate Subsequence)

Thank you so much for reading till the end. See you in the next article. Till then… HAPPY LEARNING!!

Do visit our YouTube channel Code Wrestling for more interesting stuff and watch the following video to understand the topic more fluently.

Github Repository:

codewrestling/CompetitiveProgramming

Code Wrestling