I really think showing the linear solution with a set here would’ve been highly beneficial. Our last solution works only because the array is sorted and this problem in interviews is almost never sorted. The solution below is always linear. var seenSet: Set = [] for num in array { If seenSet.contains(sum - num) { return true } else { seenSet.insert(num) } } return false
@@carlosswiftdev2703 when you use internal functions like sorted during an interview, you have to add their time complexity. Sorting at best is usually nlogn which is always going to be slower the n (linear) which is what the above solution with a set is
In brute-force methode you can loop j starting from i+1 instead of from 0, because for j = 0...i you've done in the previous loops. The loop should say "for j in i+1..
Thanks for the contribution, Tamagochi. Always interesting to see the many different ways problems can be solved (with differing levels of efficiency/complexity).
@Sean If you look at the documentation the remove(at: Index) is of complexity O(n) it would add more computation in binarySearch flow /// - Complexity: O(*n*), where *n* is the length of the array. public mutating func remove(at index: Int) -> [Element].Element
First of all, thank you very much, your videos are very well explained and easy to understand. I think it's worth mentioning that the array need to be sorted for binary search and pointer move approach.
@@seanallen You said that the array is sorted 0:53 and the comment for binary search also said "(because its sorted)" but imo it would have been nice if you explained why the array has to be sorted in a bit more detail.
Thanks and I hope you realize how much value you are bringing to iOS developers. These algos are not easy to learn and you are doing a great job at chunking down the larger concept into code that is easy to absorb.
Just saw this video and i wanted to confirm something. The Linear Solution you did for it ...... Its fine for the Array you took. But you are taking 3 presumptions to solve this. 1. Data in array is sorted, 2. There is ONLY 1 match to get the sum value 3. No Value in Array is repeated (this one goes for all 3) Can you confirm if I am thinking wrong here ? or am i right ?
Your last two videos explain starting with a sorted array. Do you plan on reviewing any sorting algorithms? Love your videos btw man. Easy to follow and you do a great job explaining concepts!
+Jordan Leeper thanks for the kind words, Jordan. Glad you enjoy the channel! I have a video planned for merge sort, but probably won't do all the sorting algorithms. Thanks for watching!
in Brute Force method, we could even skip the last iteration because the last number(14) has already been compared to all other numbers, like: for i in 0..
Just today I had oral exam in data structures and algorithms and was talking about brute force, binary search, notations etc... It fantastic to see how to work with something like that in swift :D keep crushing it
That's awesome, Kristijan! I remember when I was learning this stuff, it was very rare to find examples written in Swift. That's the whole point of this series... I want to change that! Glad you enjoyed it!
if you change "let numbers3" to "var numbers3" and under it add "numbers3.sort()". Input: _______________________________________________________ var numbers3 = [1, 20, 31, 14, 15, 3] numbers3.sort() print(numbers3) Output: _______________________________________________________ [1, 3, 14, 15, 20, 31] Then no matter if the largest number is in the middle or 1st or anywhere it will sort them from low to high and you will get the right answer. Also thank you for this amazing video! really helped me a lot.
Hey Sean, I'm not sure if this is the right place to ask you questions about this sort of old post you have, but when I downloaded your source code and ran 2. Binary Search method, the code wouldn't run and stops at "let = hasCompliment = binarySearch(array: ~~~)" while saying "Use of unresolved identifier 'binarySearch'. By any means would you know why I'm getting this error? Thanks
+nik mur Hey nik, that wasn't really in the plans since it's not Swift specific. There are a lot of great resources on TH-cam that explain that already. They can do a better job than I can, since it's not really my area of expertise.
Haha, I've thrown those types of jokes in previous videos every once in a while... it's usually during late-night editing when I'm starting to get a little delirious, lol.
Thanks so much for your videos. I love these videos as I can grasp it easier if I am stepped through it. Thanks to your delegate tutorial, I was able to do my app which is on the app store now :) thanks so much for doing these videos please keep doing them.
When you say array.count - 1 where is the - 1 coming from? i understand that you need to get the highIndex, but i dont understand how you're able to get the highIndex from - 1? This is for the last func twoSumPointers
The last solution isn't working if we looking for the index and not the value itself. For example I'm looking for `n` below: ``` // it's working if we looking for this n array[index] = n // but not working for array[n] = 10 ```
Nice tutorial Sean. I have added some code to your last method to filter and sort the array(I know it's sorted already. But if it wasn't here it is) as a bit of input from me to potentially reduce the iterations inside the while loop. func comparePointers(array: [Int], sum: Int) -> Bool { //Firstly apply a filter to eliminate all numbers greater than the sum and sort, in case numbers are not sorted. Thus reducing the amount of numbers the while loop has to iterate through. var filteredArray = array.filter({return $0 < sum}).sorted() print(filteredArray) var lowIndex = 0 var highIndex = filteredArray.count - 1 while lowIndex < highIndex { let sumOfItems = filteredArray[lowIndex] + filteredArray[highIndex] if sumOfItems == sum { print("Sum of \(filteredArray[lowIndex]) and \(filteredArray[highIndex]) = \(sum)") return true } else if sumOfItems < sum { lowIndex += 1 } else if sumOfItems > sum { highIndex -= 1 } } print("Pointers have crossed") return false }
Nice, Richard! Glad you enjoyed the video and took the time to build upon it and improve it! As you know, there is much more you could do with this code. I probably could have done an hour long video on this, but had to keep it a reasonable length 😃
So just to clarify, move pointer method only works on sorted array so we can just use sort on the array first and then apply that method and should be good?
Hey Sean, it's a request, i have struck at a coding problem that, i wanted to save a image which is picked from local gallery and then save it into sqlite database or any database.Thanks Keep posting...
Shouldn't the tempArray be initiated outside of the loop in point 2? When you're removing the n-th element in each loop from tempArray, you're only removing this single element, because you have (var tempArray = array) in the line above. If you'd initiate tempArray outside of the loop you'd shorten tempArray by n elements for each binary search.
Hi Sean, I was testing your method Brute Force, and it has a bug, cause in your array you have 2 of number 7, and if you try bruteForceTwoSum(array:numbers, sum:14) it will return false, but it should return true, cause you have 2 unique number 7
Hmmm... did you download the source code in the description and check that out? I just double checked my code and ran it with a sum of 14 and I'm returning TRUE in that situation. Try downloading the source code (link in description) and comparing it to what you have. Let me know if you're still returning false, but it seems to be working in my source code.
For solutions 2 & 3, you are assuming that the array is sorted, this can' t be a given assumption. Sorting itself takes a best case O(NlogN) time, so you need to factor that as well when calculating the total running time.
I should have been more clear about the givens on this problem. It is part of the problem that the array you are given is sorted. I based this video off of this Google Interview exercise, and in this exercise the array given is sorted. th-cam.com/video/XKu_SEDAykw/w-d-xo.html Again, I probably should have been more clear about the problem's description.
For method 2, there is an assumption here that you can copy the array and then remove an element from the copy in constant time. Is that a good assumption? I would not expect so.
Adding an additional "single" step to an algorithm, doesn't change it's time complexity. For example an algorithm that is 2n (meaning you need to iterate through the array twice), is still considered linear time because it the big picture, the 2 in front of the n is a minimal change. You typically drop the constants (in this case, the 2 in front of the end) when dealing with time complexity. However... adding an extra temporary array does take up memory, so this changes the space complexity, but not really the time complexity.
Adding a step inside a loop normally does not affect run time because most steps are constant time. But a step that copies an array cannot run in constant time. The longer the array, the longer it takes to copy. You have a step that takes o(n) inside of a loop that runs n times. If that was all of the code, clearly that should be o(n^2). I may be overly sensitive to this issue because I have been tutoring algorithm students for the past few years. I notice now that you did not make any prediction of the run time for method two, so you really did not make a mistake here. Great video by the way. I just found your videos yesterday and I am going through them all.
Thanks, Isaac. Glad you're enjoying the videos! Admittedly, CS isn't my strong suite (I don't come from a computer science background), so I may make a misstep or two along the way. Thanks for pointing it out. (I don't take it personally 😁 )
Hi Sean , Great tutorial however solution #3 (index pointer) will not work if the input is negative number array ex- ([-1,-2,-3,-4,-5] , -8). In this scenario the else if logic will have to be reversed . else if sumOfTwoItems < sumValue { highIndex -= 1 }else if sumOfTwoItems > sumValue { lowIndex += 1 } Please comment . Btw great videos:)
ok it took a little while, but i've gone an iteration route, with a dictionary as a lookup table gist.github.com/bencleary1989/ba80119e85cf9b94a41447cf648595b5 all in all my first thought was option 3
Hey sean! I just realized you can use ".contains" function in the tempArray in twoSumBinarySearch with compliment function. Hehe let numbers = [1, 3, 6, 7, 7, 12, 14] func twoSumBinarySearch(array: [Int], sum: Int) -> Bool { if array.count == 0 { return false }
Jco Bea doing contains just loops through the array. Which makes it N^2 like the first solution. The main point of twoSumBinarySearch is to get the time complexity down. Which the binary search part does.
I like your videos man. But one friendly advice; there are too many people here who are not native speakers. Please for them, speak a bit slower. Thanks for your videos.
It will fix 6 and 7 = 13 //Find all two elements pair in the array that add up to given sum func findPairGiverSum(numbers: [Int], sum: Int) { let sortedNumber = numbers.sorted() // print(sortedNumber) var left = 0 var right = sortedNumber.count - 1 while(left < right){ // print("index (\(left), \(right))") if(left != 0 && sortedNumber[left] == sortedNumber[left - 1]){ left = left + 1 continue } let pSum = sortedNumber[left] + sortedNumber[right] if(pSum == sum){ print("(\(sortedNumber[left]), \(sortedNumber[right]))") right = right - 1 left = left + 1 }else if(pSum > sum){ right = right - 1 }else{ left = left + 1 } } } //findPairGiverSum(numbers: [2,3,4,3,4,1,6,6,6,7,5,9,1,8,9], sum: 10) //findPairGiverSum(numbers: [0,1,2,4,4,7,5,3,4,1,8], sum: 8) findPairGiverSum(numbers: [1,3,6,7,7,12,14], sum: 13)
Watch Next - iOS Take Home Project - Job Interview Practice - Free Preview - th-cam.com/video/MSIe2y6Fee8/w-d-xo.html
I really think showing the linear solution with a set here would’ve been highly beneficial. Our last solution works only because the array is sorted and this problem in interviews is almost never sorted. The solution below is always linear.
var seenSet: Set = []
for num in array {
If seenSet.contains(sum - num) {
return true
} else {
seenSet.insert(num)
}
}
return false
What's wrong with just using .sorted() on the array first?
@@carlosswiftdev2703 when you use internal functions like sorted during an interview, you have to add their time complexity. Sorting at best is usually nlogn which is always going to be slower the n (linear) which is what the above solution with a set is
@@vrezhgulyan6834 Awesome thank you for the explanation. I could do with watching some CS50 videos to fully understand time complexity.
Wow! The pointer solution is so clever! Simple and beautiful :)
Glad you liked it, Danil!
This was a long one.... Happy to help answer questions or clear up any confusion in the comments!
In brute-force methode you can loop j starting from i+1 instead of from 0, because for j = 0...i you've done in the previous loops. The loop should say "for j in i+1..
Thanks for the contribution, Tamagochi. Always interesting to see the many different ways problems can be solved (with differing levels of efficiency/complexity).
@Sean
If you look at the documentation the remove(at: Index) is of complexity O(n) it would add more computation in binarySearch flow
/// - Complexity: O(*n*), where *n* is the length of the array.
public mutating func remove(at index: Int) -> [Element].Element
First of all, thank you very much, your videos are very well explained and easy to understand. I think it's worth mentioning that the array need to be sorted for binary search and pointer move approach.
Thanks Kapil! You are right, they need to be sorted. I thought I mentioned that (maybe I didn't)
@@seanallen You said that the array is sorted 0:53 and the comment for binary search also said "(because its sorted)" but imo it would have been nice if you explained why the array has to be sorted in a bit more detail.
Thanks and I hope you realize how much value you are bringing to iOS developers. These algos are not easy to learn and you are doing a great job at chunking down the larger concept into code that is easy to absorb.
Thanks for the kind words, Warren. Happy to hear I'm helping!
That was the best explanation I found on youtube until now.
Thanks Prabhdeep!
Fast? Finally a video I don't need to speed up. :)
Haha, Jay... that's nice to hear. The #1 piece of constructive feedback I get is that I talk too fast. Glad to hear it works for you!
Sean Allen I totally get, and of course slow down if you need to, I can always speed it up. Keep up the good work :)
Just saw this video and i wanted to confirm something.
The Linear Solution you did for it ...... Its fine for the Array you took. But you are taking 3 presumptions to solve this.
1. Data in array is sorted,
2. There is ONLY 1 match to get the sum value
3. No Value in Array is repeated (this one goes for all 3)
Can you confirm if I am thinking wrong here ? or am i right ?
Pointer solution is really good bro.. i also solved this problem with 2 for loops but whatever you suggested its simply short and sweet
Man! Thanks! Revisiting Algorithms on the Job Search! This explanation is dope. Any book Recommendations for Interview Questions?
Glad you liked it, Jerrick. As always, you can't go wrong with cracking the coding interview. check out seanallen.co/store for a link
Your last two videos explain starting with a sorted array. Do you plan on reviewing any sorting algorithms?
Love your videos btw man. Easy to follow and you do a great job explaining concepts!
+Jordan Leeper thanks for the kind words, Jordan. Glad you enjoy the channel! I have a video planned for merge sort, but probably won't do all the sorting algorithms. Thanks for watching!
The pointer solution doesn't work well in different scenarios like
[3, 2, 4] and the target is 6
that solution is only for sorted array
in Brute Force method, we could even skip the last iteration because the last number(14) has already been compared to all other numbers, like:
for i in 0..
Just today I had oral exam in data structures and algorithms and was talking about brute force, binary search, notations etc... It fantastic to see how to work with something like that in swift :D keep crushing it
That's awesome, Kristijan! I remember when I was learning this stuff, it was very rare to find examples written in Swift. That's the whole point of this series... I want to change that! Glad you enjoyed it!
If I run this code on leetcode It gives the wrong answer:
Input:
[3,2,4]
Target: 6
The output I am getting:
[1,1]
Expected Output :
[1,2]
Isn't "complement" written with "e" ? just to make sure I understand correctly. Anyway great video as always!
Hey Filippo... it sure is. That was a typo on my part. Good catch!
if you change "let numbers3" to "var numbers3" and under it add "numbers3.sort()".
Input:
_______________________________________________________
var numbers3 = [1, 20, 31, 14, 15, 3]
numbers3.sort()
print(numbers3)
Output:
_______________________________________________________
[1, 3, 14, 15, 20, 31]
Then no matter if the largest number is in the middle or 1st or anywhere it will sort them from low to high and you will get the right answer.
Also thank you for this amazing video! really helped me a lot.
Hey Sean, I'm not sure if this is the right place to ask you questions about this sort of old post you have, but when I downloaded your source code and ran 2. Binary Search method, the code wouldn't run and stops at "let = hasCompliment = binarySearch(array: ~~~)" while saying "Use of unresolved identifier 'binarySearch'.
By any means would you know why I'm getting this error?
Thanks
perfect!!!! Can you please make video on how to calculate time complexity of a program.It would be really helpful Thanks In Advance.
Nice Explanation....Are you planning to do a separate video on Time complexity and how to calculate it?
+nik mur Hey nik, that wasn't really in the plans since it's not Swift specific. There are a lot of great resources on TH-cam that explain that already. They can do a better job than I can, since it's not really my area of expertise.
Thanks for the reply......... BTW loved the FOR-LOOP humor..... include more humor in your video's if you can :)
Haha, I've thrown those types of jokes in previous videos every once in a while... it's usually during late-night editing when I'm starting to get a little delirious, lol.
Today tried the code myself.........only thing I was improve was removing duplicates if you don't have a return after the is found statement.
let's try
twoSumPointers(array: [3,2,4], sum: 6)
The array isn’t sorted
Thanks so much for your videos. I love these videos as I can grasp it easier if I am stepped through it.
Thanks to your delegate tutorial, I was able to do my app which is on the app store now :) thanks so much for doing these videos please keep doing them.
+Ben Duke That's awesome, Ben! Makes me happy to hear I was able to help get your app on the store. More on the way!
When you say array.count - 1 where is the - 1 coming from? i understand that you need to get the highIndex, but i dont understand how you're able to get the highIndex from - 1? This is for the last func twoSumPointers
Why is the input ascending ordered? Else we would need to sort it first and which makes loop count higher
Could you add a tutorial about Big O Notations?
That's on the list, for sure. I just have a VERY long video "to-do" list. I'll get there eventually 😃
The last solution isn't working if we looking for the index and not the value itself.
For example I'm looking for `n` below:
```
// it's working if we looking for this n
array[index] = n
// but not working for
array[n] = 10
```
Nice tutorial Sean. I have added some code to your last method to filter and sort the array(I know it's sorted already. But if it wasn't here it is) as a bit of input from me to potentially reduce the iterations inside the while loop.
func comparePointers(array: [Int], sum: Int) -> Bool {
//Firstly apply a filter to eliminate all numbers greater than the sum and sort, in case numbers are not sorted. Thus reducing the amount of numbers the while loop has to iterate through.
var filteredArray = array.filter({return $0 < sum}).sorted()
print(filteredArray)
var lowIndex = 0
var highIndex = filteredArray.count - 1
while lowIndex < highIndex {
let sumOfItems = filteredArray[lowIndex] + filteredArray[highIndex]
if sumOfItems == sum {
print("Sum of \(filteredArray[lowIndex]) and \(filteredArray[highIndex]) = \(sum)")
return true
} else if sumOfItems < sum {
lowIndex += 1
} else if sumOfItems > sum {
highIndex -= 1
}
}
print("Pointers have crossed")
return false
}
Nice, Richard! Glad you enjoyed the video and took the time to build upon it and improve it! As you know, there is much more you could do with this code. I probably could have done an hour long video on this, but had to keep it a reasonable length 😃
So just to clarify, move pointer method only works on sorted array so we can just use sort on the array first and then apply that method and should be good?
With brute force method, if array contains two or more same object and you add "where a != b" line, the algorithm will not work
Hey Sean, it's a request, i have struck at a coding problem that, i wanted to save a image which is picked from local gallery and then save it into sqlite database or any database.Thanks Keep posting...
nice one, Move pointer is definitely the easy one :D
+Adis Mulabdic I agree... sometimes the better solution can end up being pretty easy once you figure it out.
Hi Sean, The pointer algorithm isn't sufficient for all condition, let say input array is [3,2,4] and the sum is 6.
You have to sort the array first
great video series and explanations
Glad you liked it!
In 15.25 sec output is 1 and 12 = 13. Why it's not showing 6 and 7 = 13?
How would you do this if we are doing this with 2 arrays and need to find if elements in both equal a sum?
Shouldn't the tempArray be initiated outside of the loop in point 2? When you're removing the n-th element in each loop from tempArray, you're only removing this single element, because you have (var tempArray = array) in the line above. If you'd initiate tempArray outside of the loop you'd shorten tempArray by n elements for each binary search.
I like hidden basketball references like 23 lol
I guess the 3rd approach works only for a sorted array
Hi Sean, I was testing your method Brute Force, and it has a bug, cause in your array you have 2 of number 7, and if you try bruteForceTwoSum(array:numbers, sum:14) it will return false, but it should return true, cause you have 2 unique number 7
Hmmm... did you download the source code in the description and check that out? I just double checked my code and ran it with a sum of 14 and I'm returning TRUE in that situation. Try downloading the source code (link in description) and comparing it to what you have. Let me know if you're still returning false, but it seems to be working in my source code.
Hey Sean Will Brute Force code work if we have multiple combinations for sum in array ?
Hey Sean. Any idea about solving 3 sum or 4 sum problem?
I have not tried those types of problems, Gunjan, so I wouldn't really know off the top of my head.
For solutions 2 & 3, you are assuming that the array is sorted, this can' t be a given assumption. Sorting itself takes a best case O(NlogN) time, so you need to factor that as well when calculating the total running time.
I should have been more clear about the givens on this problem. It is part of the problem that the array you are given is sorted. I based this video off of this Google Interview exercise, and in this exercise the array given is sorted. th-cam.com/video/XKu_SEDAykw/w-d-xo.html
Again, I probably should have been more clear about the problem's description.
Got it !! And btw, you are doing a great job with the videos, keep it up :)
Thanks Anshul!
Hi Anshul,
So if we sort the array in the third example, the time complexity would be O(n log n)?
Thanks.
this doesnt work for the two sum problem on leetcode
For method 2, there is an assumption here that you can copy the array and then remove an element from the copy in constant time. Is that a good assumption? I would not expect so.
Adding an additional "single" step to an algorithm, doesn't change it's time complexity. For example an algorithm that is 2n (meaning you need to iterate through the array twice), is still considered linear time because it the big picture, the 2 in front of the n is a minimal change. You typically drop the constants (in this case, the 2 in front of the end) when dealing with time complexity. However... adding an extra temporary array does take up memory, so this changes the space complexity, but not really the time complexity.
Adding a step inside a loop normally does not affect run time because most steps are constant time. But a step that copies an array cannot run in constant time. The longer the array, the longer it takes to copy. You have a step that takes o(n) inside of a loop that runs n times. If that was all of the code, clearly that should be o(n^2). I may be overly sensitive to this issue because I have been tutoring algorithm students for the past few years.
I notice now that you did not make any prediction of the run time for method two, so you really did not make a mistake here.
Great video by the way. I just found your videos yesterday and I am going through them all.
Thanks, Isaac. Glad you're enjoying the videos! Admittedly, CS isn't my strong suite (I don't come from a computer science background), so I may make a misstep or two along the way. Thanks for pointing it out. (I don't take it personally 😁 )
Thank you Sean!
Glad you enjoyed it, Kenneth.
Hi Sean , Great tutorial however solution #3 (index pointer) will not work if the input is negative number array ex- ([-1,-2,-3,-4,-5] , -8). In this scenario the else if logic will have to be reversed .
else if sumOfTwoItems < sumValue {
highIndex -= 1
}else if sumOfTwoItems > sumValue {
lowIndex += 1
}
Please comment . Btw great videos:)
Thank for pointing that out. Good catch!
Wan't bruteforce solution give us false for 14?
at 0.75 speed you sound pretty hammered and it's hard to take a drunk programmer seriously... :-)
Hahaha, Ibrahim, that's hilarious. 😂 😂 😂
This works if theres only one solution for the sum
Nice video Sean!
+Ben Cleary Thanks Ben. Interested to see if you have any alternate solutions 😀
ok it took a little while, but i've gone an iteration route, with a dictionary as a lookup table gist.github.com/bencleary1989/ba80119e85cf9b94a41447cf648595b5 all in all my first thought was option 3
Nice solution Ben! I've added it to the source code download (with a credit to you).
Thanks Sean 👍
Another great video.
+rahul bandal Thanks, Rahul!
Hey sean!
I just realized you can use ".contains" function in the tempArray in twoSumBinarySearch with compliment function. Hehe
let numbers = [1, 3, 6, 7, 7, 12, 14]
func twoSumBinarySearch(array: [Int], sum: Int) -> Bool {
if array.count == 0 { return false }
for i in 0..
Jco Bea doing contains just loops through the array. Which makes it N^2 like the first solution. The main point of twoSumBinarySearch is to get the time complexity down. Which the binary search part does.
Okay bro. Thanks
your logic will fail with [3,2,4] with sum 6.
I like your videos man. But one friendly advice; there are too many people here who are not native speakers. Please for them, speak a bit slower. Thanks for your videos.
This is a very old video of mine. I've gotten a lot better 😀
It will fix 6 and 7 = 13
//Find all two elements pair in the array that add up to given sum
func findPairGiverSum(numbers: [Int], sum: Int) {
let sortedNumber = numbers.sorted()
// print(sortedNumber)
var left = 0
var right = sortedNumber.count - 1
while(left < right){
// print("index (\(left), \(right))")
if(left != 0 && sortedNumber[left] == sortedNumber[left - 1]){
left = left + 1
continue
}
let pSum = sortedNumber[left] + sortedNumber[right]
if(pSum == sum){
print("(\(sortedNumber[left]), \(sortedNumber[right]))")
right = right - 1
left = left + 1
}else if(pSum > sum){
right = right - 1
}else{
left = left + 1
}
}
}
//findPairGiverSum(numbers: [2,3,4,3,4,1,6,6,6,7,5,9,1,8,9], sum: 10)
//findPairGiverSum(numbers: [0,1,2,4,4,7,5,3,4,1,8], sum: 8)
findPairGiverSum(numbers: [1,3,6,7,7,12,14], sum: 13)