Explanation of the Problem
The gist of the sum zero problems is you will have a list or an array of numbers. You will have to return the pair of the two numbers that when added together hit the target sum zero. There should be only one solution to the problem and a number cannot be used twice.
Input: nums = [-5,-4,-3,-2,0,2,4,6,8], target = 0 Output: [-4,4] Explanation: From the example we can see that nums + nums == 0, which is the required target, so have to return [-4,4].
Solution 1: Bruteforce Approach
Intuition: For every element in the array we will try to find out an element such that the sum of both the elements in the array becomes equal to the target sum zero.
Approach towards the problem: We will generally transverse through the entire array and for each element (i) in the array we will try to find out another element amongst the other elements such that the sum of both the elements becomes equal to the target sum.
Time Complexity: O(N2)
Solution 2: Optimised Solution
Approach towards the problem: In this problem for optimizing the solution we will generally take the first element as the left pointer and the last element in the array as the right pointer. We will generally take the sum of the left element and the right element and try to find out whether their sum is zero, greater than zero, or less than zero. If the sum is greater than zero then we will decrease the right by 1 . And if the sum is less then we will increase left by 1. If we find the sum as zero then we will return the left and right elements as a pair.
Note: Array should be sorted while applying the above logic.
Time Complexity: O(N)