Solving 3SUM problem using Swift
The 3Sum problem is often asked during technical interviews and the problem at first seems quite tough but it’s got a pretty similar taste to 2Sum problem.
Here is the problem: You are given a sorted array, and you need to find three numbers in the array that can add up to a particular sum which is also given to you. I would strongly urge everyone to first try solving the 2Sum problem where it requires you to find 2 numbers that add up to give you the given sum and similarly practice this problem before continuing to the solution given below.
So first lets start with function signature:
The function takes in the sorted array of type
Int and a
Sum integer and returns a
Firstly, I am initializing three variables - _
complement, lowIndex & highIndex._To solve the 3Sum problem here is the method I am using: If the array is say
\[1,4,6,4\] and sum is 11, then we will first hold on to first number which in this case is 1, and then using linear pointer method on the remaining array
\[4,6,4\]. Here we will have a pointer which will start from 4 with one index more than the number we holding on to, and the high pointer will start with index of array.count - 1. (The right hand side)
Next, we will start a for loop which will give us the
element and the _
index of that element in the sequence, hence using
array.enumerated() Then inside the for loop, I am setting
lowIndex to current
index + 1. We also set complement by subtracting the current element we are on with the sum passed in the function by the user.
Then we have another loop inside this for loop. This time it’s a while loop. The while loop will keep running until the two pointers cross over.
Inside the while loop, we have three if statements:
Now the problem has been converted in to 2sum. We will check if the two numbers sum is greater than complement, if yes, then move the highIndex pointer by 1 to the left. Similarly, if the sum of two numbers is less than the complement, then move the lowIndex pointer by 1 to the right. Else, if the sum of two numbers is equal to complement, then return true.
After this if statement, we are setting the
highIndex back to 0 and
array.count - 1.
Next call this function:
The output for this is:
This is how you can solve this algorithm. This particular solution is O(n^2) mainly as we are using two nested loops.