programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Jeanne Boyarsky
• Liutauras Vilda
Sheriffs:
• Rob Spoor
• Bear Bibeault
• Tim Cooke
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Piet Souris
Bartenders:
• Frits Walraven
• Himai Minh

# Sum of two numbers

Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:
Coming back to code ranch after a long time.

I am revisiting my problem-solving skills and started solving some basic problems on leetcode. One of the problems is:

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

I am solving it in the following way with o(n):

I am looking for ways to improve and optimize this code. Also, what potential problem this code could have.

Please let me know if such questions aren't supposed to be asked and I apologize in advance for the same. If it's fine to ask then I may open new threads with some other problems.

Marshal
Posts: 26624
81
• 1
• Number of slices to send:
Optional 'thank-you' note:
Try your code with this input:

Given nums = [2, 11, 7, 15], target = 9

Edit: And yeah, this sort of question is perfectly fine. Carry on with your project.

Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:
Modified the code:

Complexity changed to O(n^2). Suggestions, please?

Saloon Keeper
Posts: 4511
166
• Number of slices to send:
Optional 'thank-you' note:
An idea is to make a Map<element, List(index)>. Then, if you have a key, see if target - key is present.

Marshal
Posts: 73011
330
• Number of slices to send:
Optional 'thank-you' note:

Punit Jain wrote:Coming back to code ranch after a long time.

Good to see you back

. . . some basic problems on leetcode. . . .

Saloon Keeper
Posts: 13010
281
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:An idea is to make a Map<element, List(index)>. Then, if you have a key, see if target - key is present.

I had the same idea, although you don't need the list of indices. The problem description states that the target is a sum of two integers, so you only need to keep track of one index per integer that you've already seen.

This solution will run in linear time if you use a HashMap.

Piet Souris
Saloon Keeper
Posts: 4511
166
• Number of slices to send:
Optional 'thank-you' note:
I interpreted the exercise in OP's opening post such, that if there is an element 7, and the target is 14, then a solution is 7 + 7, provided there are at least two sevens. That's why I have a List of indices. But I might be wrong with my interpretation.

Stephan van Hulst
Saloon Keeper
Posts: 13010
281
• Number of slices to send:
Optional 'thank-you' note:

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Piet Souris
Saloon Keeper
Posts: 4511
166
• Number of slices to send:
Optional 'thank-you' note:
Yes, I read that. But if the array = {0, 7, 7, 12}  and the target is 14, then there is one solution 7 + 7, and these two sevens are not the same element. As said, that is my interpretation, but you could be right as well. In OP's second code he would also find 7 + 7. Well, wonder whart OP thinks

Stephan van Hulst
Saloon Keeper
Posts: 13010
281
• Number of slices to send:
Optional 'thank-you' note:
Your interpretation is correct. You still don't need to keep track of multiple instances of the same element. When you encounter the second seven, you can immediately return its index without storing it in the map first.

Piet Souris
Saloon Keeper
Posts: 4511
166
• Number of slices to send:
Optional 'thank-you' note:
Ah, I see what you mean. Clever!

Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:

Punit Jain wrote:Coming back to code ranch after a long time.

Good to see you back

. . . some basic problems on leetcode. . . .

Thanks, Here is the link: https://leetcode.com/explore/interview/card/amazon/76/array-and-strings/508/

Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:Yes, I read that. But if the array = {0, 7, 7, 12}  and the target is 14, then there is one solution 7 + 7, and these two sevens are not the same element. As said, that is my interpretation, but you could be right as well. In OP's second code he would also find 7 + 7. Well, wonder whart OP thinks

Yeah, if the same number is coming twice then it can be used. The problem only says that the same number can't be used twice.

Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:An idea is to make a Map<element, List(index)>. Then, if you have a key, see if target - key is present.

Need some more explanation on this. Did you mean copy the whole array to a map, first?

Piet Souris
Saloon Keeper
Posts: 4511
166
• Number of slices to send:
Optional 'thank-you' note:
Yes, but Stephan is right in that that is not needed.

Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:Yes, but Stephan is right in that that is not needed.

Yet to implement the complete code, but this is what you are talking about, correct?

Piet Souris
Saloon Keeper
Posts: 4511
166
• 1
• Number of slices to send:
Optional 'thank-you' note:
This is not what I meant, but this is indeed the way to go! Well done!

In

you should test whether sumsHash.contains(target - numbers[i], and then the &&... can be deleted.

Bartender
Posts: 2867
150
• 1
• Number of slices to send:
Optional 'thank-you' note:
Just wanted to add, sumsHash does not tell me what the variable does. I think you took the word "Hash" from HashMap which is not a good idea. Next, the map merely stores the array and the indexes, there's no "sum" involved in it.

Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:
Here is the implementation:

This will fail when there are duplicate elements in the array. Reason - when I copy the array to a map and if there is a duplicate, it will replace the existing number. The pointer will move but the map will not have the next element. It will try to access the next element to return and will fail will null pointer.

I guess I will have to maintain the pointer somewhere?

Stephan van Hulst
Saloon Keeper
Posts: 13010
281
• Number of slices to send:
Optional 'thank-you' note:

Punit Jain wrote:This will fail when there are duplicate elements in the array.

I think this will fail in general. You are not returning the correct indices. On line 19, you are getting the index of numbers[i], but you should be getting the index of target - numbers[i].

when I copy the array to a map and if there is a duplicate, it will replace the existing number.

You mean it will replace the index of the existing number. You can easily solve this by using putIfAbsent instead of put.

The pointer will move but the map will not have the next element. It will try to access the next element to return and will fail will null pointer.

I guess I will have to maintain the pointer somewhere?

No, this problem simply occurs because when the algorithm finds a solution (on line 18), you look up the wrong index on line 19.

Also, don't mention 'pointers'. Java doesn't have a concept of pointers. Java has 'references' (which may or may not be implemented using pointers, but the language specification doesn't say anything about this), or you have an 'index' into an array, map or collection.

You don't need the search method. Either the code finds the correct indices inside the for-loop, or the array doesn't contain numbers that make up the target sum. After your for-loop, you can just return null or throw an IllegalArgumentException.

• Why are you creating an instance of Sum when Sum doesn't have any fields and doesn't implement any interfaces? Just make its methods static and call them without creating an instance.
• Why are your class and methods public? Do you need to use it outside of the package you declared it in?
• Why is your class not final? Do you need to extend it?
• You have a typo in the variable 'macth'.
• The name 'findSumMatched' doesn't make sense to me. A sum is a number that consists of two or more addends that were added together. The target is a sum. I would declare the method as findTwoAddends(int[] numbers, int sum).
• If you're on Java 10+, you can use the var identifier to declare a variable to avoid redundancy when using a constructor to initialize the variable. Otherwise, if you're on Java 7+ you can use the diamond operator.
• In general it's not a good idea to use containsKey() if you're going to get an element from a map directly afterward. It will cause the map to perform a lookup twice. Just call get() and check if the result is null.
• When you are performing the same expression multiple times, you should instead perform it once and assign the result to a variable. Then use the variable multiple times. For instance, assign numbers[i] to a variable inside your for-loop.
•
Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:

Stephan van Hulst wrote:

Punit Jain wrote:This will fail when there are duplicate elements in the array.

I think this will fail in general. You are not returning the correct indices. On line 19, you are getting the index of numbers[i], but you should be getting the index of target - numbers[i].

Yes, I was getting the wrong index. Fixed the index issue.

when I copy the array to a map and if there is a duplicate, it will replace the existing number.

Stephan van Hulst wrote:You mean it will replace the index of the existing number. You can easily solve this by using putIfAbsent instead of put.

I think I misunderstood. I don't need to store that number.

Stephan van Hulst wrote:Also, don't mention 'pointers'. Java doesn't have a concept of pointers. Java has 'references' (which may or may not be implemented using pointers, but the language specification doesn't say anything about this), or you have an 'index' into an array, map or collection.

You don't need the search method. Either the code finds the correct indices inside the for-loop, or the array doesn't contain numbers that make up the target sum. After your for-loop, you can just return null or throw an IllegalArgumentException.

thanks so much.

Stephan van Hulst wrote:

• Why are you creating an instance of Sum when Sum doesn't have any fields and doesn't implement any interfaces? Just make its methods static and call them without creating an instance.
• Why are your class and methods public? Do you need to use it outside of the package you declared it in?
• Why is your class not final? Do you need to extend it?
• You have a typo in the variable 'macth'.
• The name 'findSumMatched' doesn't make sense to me. A sum is a number that consists of two or more addends that were added together. The target is a sum. I would declare the method as findTwoAddends(int[] numbers, int sum).
• If you're on Java 10+, you can use the var identifier to declare a variable to avoid redundancy when using a constructor to initialize the variable. Otherwise, if you're on Java 7+ you can use the diamond operator.
• In general it's not a good idea to use containsKey() if you're going to get an element from a map directly afterward. It will cause the map to perform a lookup twice. Just call get() and check if the result is null.
• When you are performing the same expression multiple times, you should instead perform it once and assign the result to a variable. Then use the variable multiple times. For instance, assign numbers[i] to a variable inside your for-loop.

• I was just solving a problem from leet code and was focusing on the logic. Implemented all these comments. Thanks for the comments and explanation.

Stephan van Hulst
Saloon Keeper
Posts: 13010
281
• Number of slices to send:
Optional 'thank-you' note:
Show us your updated code for review.

Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:

Stephan van Hulst wrote:Show us your updated code for review.

Sure, here is the updated code:

Campbell Ritchie
Marshal
Posts: 73011
330
• Number of slices to send:
Optional 'thank-you' note:
Why the illegal argument exception?

Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:Why the illegal argument exception?

Can return an empty array or null as well. Depends on how the caller will be handling this, but I should have handled this in the code. Just updated the code in the above post.

Campbell Ritchie
Marshal
Posts: 73011
330
• 1
• Number of slices to send:
Optional 'thank-you' note:
Kindly don't “update” posts after they have been answered. What circumstances will that exception be thrown in?

Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:Kindly don't “update” posts after they have been answered. What circumstances will that exception be thrown in?

Whenever the numbers aren’t available in the given array.

Campbell Ritchie
Marshal
Posts: 73011
330
• Number of slices to send:
Optional 'thank-you' note:
So, is that an “abnormal” situation? Does it merit an exception?

Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:So, is that an “abnormal” situation? Does it merit an exception?

No, it is an expected behaviour from this code when the numbers aren't present in the array. I understood what you are saying - the exception is to be thrown for an abnormal situation. I should return a null or empty array.

Campbell Ritchie
Marshal
Posts: 73011
330
• 1
• Number of slices to send:
Optional 'thank-you' note:

An empty array is usually better than null.

Sheriff
Posts: 16278
271
• Number of slices to send:
Optional 'thank-you' note:
Actually, the requirements say "You may assume that each input would have exactly one solution" so I think an IllegalArgumentException is appropriate when no solution is found.

Junilu Lacar
Sheriff
Posts: 16278
271
• 1
• Number of slices to send:
Optional 'thank-you' note:

Punit Jain wrote:No, it is an expected behaviour from this code when the numbers aren't present in the array. I understood what you are saying - the exception is to be thrown for an abnormal situation. I should return a null or empty array.

If the requirements say "You may assume that each input would have exactly one solution" then you do have an abnormal condition when no solution is found. The IllegalArgumentException is fine, in my opinion.

Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:

Junilu Lacar wrote:

Punit Jain wrote:No, it is an expected behaviour from this code when the numbers aren't present in the array. I understood what you are saying - the exception is to be thrown for an abnormal situation. I should return a null or empty array.

If the requirements say "You may assume that each input would have exactly one solution" then you do have an abnormal condition when no solution is found. The IllegalArgumentException is fine, in my opinion.

Maybe just a good idea not to throw. Because an exception is supposed to be thrown in exceptional scenarios. In this code, it's more like a behaviour or a use-case or something that may happen more often. Not sure though, but this is how I am thinking.

Campbell Ritchie
Marshal
Posts: 73011
330
• 1
• Number of slices to send:
Optional 'thank-you' note:
Yes, Junilu, if the exercise says there is a solution, it is probably a good idea to throw an exception of some sort after all.

Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:

Punit Jain wrote:

Junilu Lacar wrote:

Punit Jain wrote:No, it is an expected behaviour from this code when the numbers aren't present in the array. I understood what you are saying - the exception is to be thrown for an abnormal situation. I should return a null or empty array.

If the requirements say "You may assume that each input would have exactly one solution" then you do have an abnormal condition when no solution is found. The IllegalArgumentException is fine, in my opinion.

Maybe just a good idea not to throw. Because an exception is supposed to be thrown in exceptional scenarios. In this code, it's more like a behaviour or a use-case or something that may happen more often. Not sure though, but this is how I am thinking.

Actually, my comment was conflicting, but yeah as the statement says - You may assume that each input would have exactly one solution. I will throw an argument not found as its an exceptional scenario.

Stephan van Hulst
Saloon Keeper
Posts: 13010
281
• Number of slices to send:
Optional 'thank-you' note:
I agree that IllegalArgumentException is the way to go. The method expects that the array always contains two numbers that make up the target sum.

Campbell Ritchie wrote:An empty array is usually better than null.

I'd agree in general, but not in this case. The return value doesn't represent a collection of results that can be iterated over. Rather, it represents a tuple of two numbers that either exists or doesn't exist.

If the method didn't expect that the sum can always be found, the appropriate return type would have been Optional<int[]>.

Stephan van Hulst
Saloon Keeper
Posts: 13010
281
• 1
• Number of slices to send:
Optional 'thank-you' note:

Punit Jain wrote:Sure, here is the updated code

Your code looks very good. Some final points:

• Your class is still public.
• You can initialize your map using the diamond operator.
• You're calling get() in your loop twice, causing the map to make two lookups.
•
Punit Jain
Ranch Hand
Posts: 1143
5
• Number of slices to send:
Optional 'thank-you' note:

Stephan van Hulst wrote:

Punit Jain wrote:Sure, here is the updated code

Your code looks very good. Some final points:

• Your class is still public.
• You can initialize your map using the diamond operator.
• You're calling get() in your loop twice, causing the map to make two lookups.

• Here is the updated code: