Win a copy of Five Lines of Code this week in the OO, Patterns, UML and Refactoring forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Bear Bibeault
  • Ron McLeod
  • Jeanne Boyarsky
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Liutauras Vilda
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • fred rosenberger
  • salvin francis
Bartenders:
  • Piet Souris
  • Frits Walraven
  • Carey Brown

Sum of two numbers

 
Ranch Hand
Posts: 1137
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 25677
69
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 1137
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Modified the code:



Complexity changed to O(n^2). Suggestions, please?
 
Bartender
Posts: 4001
156
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
An idea is to make a Map<element, List(index)>. Then, if you have a key, see if target - key is present.
 
Marshal
Posts: 69805
277
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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

Good to see you back

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

Please provide links so we can look at the problems ourselves.
 
Saloon Keeper
Posts: 12141
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Bartender
Posts: 4001
156
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 12141
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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

 
Piet Souris
Bartender
Posts: 4001
156
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 12141
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 4001
156
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ah, I see what you mean. Clever!
 
Punit Jain
Ranch Hand
Posts: 1137
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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. . . .

Please provide links so we can look at the problems ourselves.



Thanks, Here is the link: https://leetcode.com/explore/interview/card/amazon/76/array-and-strings/508/
 
Punit Jain
Ranch Hand
Posts: 1137
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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: 1137
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Bartender
Posts: 4001
156
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, but Stephan is right in that that is not needed.
 
Punit Jain
Ranch Hand
Posts: 1137
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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
Bartender
Posts: 4001
156
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Saloon Keeper
Posts: 2622
128
Google Web Toolkit Eclipse IDE Java
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 1137
4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 12141
258
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

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.

Other comments about your code:

  • 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: 1137
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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:
    Other comments about your code:

  • 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: 12141
    258
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Show us your updated code for review.
     
    Punit Jain
    Ranch Hand
    Posts: 1137
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

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



    Sure, here is the updated code:

     
    Campbell Ritchie
    Marshal
    Posts: 69805
    277
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Why the illegal argument exception?
     
    Punit Jain
    Ranch Hand
    Posts: 1137
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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: 69805
    277
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Kindly don't “update” posts after they have been answered. What circumstances will that exception be thrown in?
     
    Punit Jain
    Ranch Hand
    Posts: 1137
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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: 69805
    277
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    So, is that an “abnormal” situation? Does it merit an exception?
     
    Punit Jain
    Ranch Hand
    Posts: 1137
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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: 69805
    277
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    An empty array is usually better than null.
     
    Sheriff
    Posts: 15779
    264
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 15779
    264
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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: 1137
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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: 69805
    277
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 1137
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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: 12141
    258
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    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: 12141
    258
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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: 1137
    4
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    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:
      Bookmark Topic Watch Topic
    • New Topic