We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
You were on the right path indeed. Dictionary can be used for solving this problem. @nelson_matos solution is certainly of order n but precisely it is O(2n) as he is running two for loops one after the other which is not required. Here is how you can do it in single iteration which results in O(n) complexity precisely. In fact, if the desired pair is found mid-way then you don't have to even iterate the entire array:
I started iterating the array elements. I created a dictionary look up (element,index) of the input array as I iterated through the elements. e.g. for the input test case # 0
4 (Sum to be found)
5 (number of input elements)
1 4 5 3 2
I created a look-up data structure as shown below for each value and its index in the array during iteration:
1 - 0
4 - [value >= 4. So ignored as a pair will not be possible in this case]
5 - [value >= 4. So ignored as a pair will not be possible in this case]
3 - [Solution found at this element. Break further iteration]
Case # 1 has got duplicate elements. So how do you insert the duplicate values in dictionary?
4 (Sum to be found)
4 (number of input elements)
2 2 4 3
Duplicate value will have two cases:
Either it will be part of the solution pair. So, you will get solution the moment you reach to the duplicate element. So you will not need to insert it any way.
If it is not part of the solution pair then you can simply ignore it. Move to next element and continue iterating.
Time Complexity: O(n) //there are no nested for loops.
Space Complexity: O(n) //an extra look-up dictionary storage is required
Ice Cream Parlor
You are viewing a single comment's thread. Return to all comments →
You were on the right path indeed. Dictionary can be used for solving this problem. @nelson_matos solution is certainly of order n but precisely it is O(2n) as he is running two for loops one after the other which is not required. Here is how you can do it in single iteration which results in O(n) complexity precisely. In fact, if the desired pair is found mid-way then you don't have to even iterate the entire array:
I started iterating the array elements. I created a dictionary look up (element,index) of the input array as I iterated through the elements. e.g. for the input test case # 0
I created a look-up data structure as shown below for each value and its index in the array during iteration:
Case # 1 has got duplicate elements. So how do you insert the duplicate values in dictionary?
Duplicate value will have two cases:
If it is not part of the solution pair then you can simply ignore it. Move to next element and continue iterating.
Here is my complete C# solution.