Daily Coding Problem is a website which will send you a programming challenge to your inbox every day. I want to show beginners how to solve some of these problems using Java, so this will be an ongoing series of my solutions. Feel free to pick them apart in the comments!
Problem
Given a list of numbers and a number k, return whether any two numbers from the list add up to k.
For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
Bonus: Can you do this in one pass?
Strategy
This problem requires every element in the list to be checked against every other element at least once. In the worst case scenario, we will have to check:
- 1 pair for 2 elements
- 3 pairs for 3 elements
- 6 pairs for 4 elements
- etc.
These are triangular numbers. The Nth triangular number T(N) is given by:
T(N) = N * (N + 1) / 2
So this algorithm has a worst-case time complexity of N2. Assuming the list has N elements...
- The first element should be checked against the second through
Nth elements - The second element should be checked against the third through
Nth elements - etc.
As soon as a pair is found that adds up to k, we can quit. We don't need to find all pairs, we just need to find the first pair that adds to k. The problem states that the pair shouldn't be returned, just true or false.
Code
The first thing I would do is build a double for loop, where the outer loop moves over all elements of the list (except the last) and the inner loop moves over all elements after the current element of the outer loop. Assuming the given list is called given
int[] given = new int[]{ ... };
int k = ...;
int len = given.length;
for (int outer = 0; outer < (len - 1); ++outer) {
for (int inner = outer + 1; inner < len; ++inner) {
// ... logic here
}
}
This way, we compare no two elements twice.
The only thing left to do is check if the elements at indices outer and inner add to k. If they do, we're done -- we can return true. Otherwise, we check the next pair. If we get through all pairs without finding any which sum to k, we return false:
int[] given = new int[]{ ... };
int len = given.length;
public boolean codingProblem001 (int[] array, int k) {
for (int outer = 0; outer < (len - 1); ++outer) {
for (int inner = outer + 1; inner < len; ++inner) {
if (given[outer] + given[inner] == k)
return true;
}
}
return false;
}
Let's check this to see if it works:
$ jshell
| Welcome to JShell -- Version 9.0.4
| For an introduction type: /help intro
jshell> /open DCP001.java
jshell> int[] given = new int[]{ 10, 15, 3, 7 }
given ==> int[4] { 10, 15, 3, 7 }
jshell> int k = 17
k ==> 17
jshell> DCP001.codingProblem001(given, k)
$4 ==> true
jshell> DCP001.codingProblem001(given, k+1)
$5 ==> true
jshell> DCP001.codingProblem001(given, k+2)
$6 ==> false
Result $4 is true because 10 and 7 add to k. $5 is also true because 15 and 3 add to k+1. But $6 is false because no two elements of given add to k+2.
All the code for my Daily Coding Problems solutions is available at github.com/awwsmm/daily.
Suggestions? Let me know in the comments.
Top comments (19)
I’d use a set and iterate over the list and for each element I’d check if the set contains that element and if it does, it means we found a positive answer and if not, add
k - arr[i]to the set.Thank you for sharing!
What is the Big-O of this solution, though?
In the worst case, if we have...
2 elements: we will do a
contains()on a set with 0 elements, then anadd(), then acontains()on a set with 1 element, then anadd().3 elements: all of the above, plus a
contains()on a set with 2 elements, then anadd()Assuming we skip the last
add()when we know we've reached the end of the list, worst-case would be callingcontains()onNsets of length 0 throughN-1, plus callingadd()N-1times.This is definitely less space-efficient than my solution, because of the set, but is it more time-efficient? What do you think?
I think it depends on how set works under the hood.
At first, because there is only one for loop, one might think it’s only
O(n).But how does the `contains()’ method actually work? I have just read here and it says that set will internally iterate its elements and compare each element to the object passed as parameter.
Another way of making sure that there isn’t another for loop going on behind the scenes is by using a
map. Because accessing an item requiresO(1)time.(as far as I know)So it could be that the
Setsolution is just as memory-efficient as the double-forloop. I'd love to do a benchmark of this.If you do, please let me know what the results are!
Thanks!
Ah, here is the answer already.
It's O(N) for sure. Sets (based on HashMaps) in Java have O(1) amortized for lookup and insert.
Very clever! I like this answer.
yo!🔥
I thought the same and this is way more efficient runtime.
Hi
Why not sorting the data first? If it is sorted, you can easily do a dichotomic search for the second number and get O(n(log(n)). Because sorting can be done in the same complexity, you get something better than the O(n2) algorithm above, with a space complexity of O(1)
You could also sort using a binary tree, then it becomes trivial to search for the second number in the tree while keeping the same complexity (with a space complexity of O(n) though)
If you use the map solution of Andrei, you don't know how much space the map will take (it depends on the implementation) but with a time complexity of O(n). If you use the set, you will get the same thing as my first solution.
Joan and Andrei both provided alternative solutions to this problem. I wondered which of our solutions was the best in the worst-case, so I created a Java Microbenchmark Harness (JMH) example which runs each of these pieces of code to time them. So I present...
A mini-tutorial on using the Java Microbenchmark Harness to benchmark Java code
Setup
Use Maven to set up a simple JMH project:
My package is
daily, so I use that in place of<org.sample>, and I set theartifactIdto001because this is the first Daily Coding Problem I'm solving in this fashion. This makes a directory called001with the following structure:The contents of
MyBenchmark.javaare as follows:...but we're going to delete all of this and write our own code.
Benchmarking
Christophe Schreiber has a good example of using JMH on Dev.To. We need to send parameters to our methods, though. In the worst-case scenario, we'll have a very long array in which no two numbers add to
k. These numbers should also all be unique so that the compiler can't do any optimisations and so that we need to continually add them to Andrei'sSet.I will be using this file on GitHub by Bruno Doolaeghe as a template:
All code is available on my GitHub. The results of the benchmarking are below. Please note that I don't use JMH very often so this may not be the optimal way to lay out this benchmark. If you have any suggestions, be sure to let me (politely) know :)
Even in the worst-case scenario with a 10-million element array, I see no difference between the three methods in terms of time:
Because of the uncertainties on the three benchmarks, they could all be the same (they could all be
0.053 us/op). That's anticlimactic!Follow-up with arrays with more elements:
Does the double-
forwin??Interesting stats though. But could it be that the N squared approach never really got to it's worst case scenario by not iterating through all the elements?
If you're crazy about complexity's O, I have the impression it would be better to start by sorting it and then going through the array starting both from the beggining and the end, but only once, so it becomes O(nlogn). It's probably less readable though.
Andrei's solution was very smart as well, and I guess depending on complexity of
containsandaddof the Set object, you could get an algorithm with the same complexity.I enjoyed this! I read the problem and decided to have a go myself and see what our different solutions looked like. I did the same except in the embedded loop i just started at array.length and went down to 0 instead.
You bring up a good point. I should hide my solutions for future coding challenges like this.
I would even check, if the outer number is greater equal than the number k. Thus we could even skip some for loops.
This sounds reasonable to me but note that the problem doesn't state whether the numbers in the array can be negative!
If I got this question in a coding interview, I'm not sure I would make that assumption.
I was actually thinking more in the line of:
Let n={3,5,10,15,17} and k=13. 15 and 17 should not be considered at all since they are greater.
The numbers are not supposed to be negative. The worst case remains the same.
But if n is meant to be sorted, we can then only check the left side of n up to the very closest number to k, which is still less than k. That would change the approach in general, I would think.