Find the range of index of consecutive integers from a sorted array

Question

I would like to know how can improve my solution.

import java.util.*;
public class prog{
 public Map<Integer, Integer> findList(int[] array1)
 {
 Map<Integer, Integer> list= new HashMap<Integer, Integer>();
 int start_index= 0;
 int end_index = 0;
 int length = array1.length; 
 for(int i = 1; i < length ; ++i) 
 { 
 if(array1[i-1] + 1 != array1[i])
 {
 end_index = i - 1;
 list.put(start_index, end_index);
 start_index = i;
 } 
 } 
 if( array1[length -2]+1 == array1[length -1])
 {
 end_index = length - 1;
 list.put(start_index, end_index);
 }
 return list;
 }
 public static void main(String[] arr)
 {
 int [] array1 = { 4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 20, 22, 23, 24, 27,34 };
 prog prg = new prog();
 Map<Integer, Integer> list1= new HashMap<Integer, Integer>();
 list1 = prg.findList(array1);
 for( Map.Entry<Integer,Integer> entry: list1.entrySet())
 {
 System.out.println( entry.getKey()+"--"+ entry.getValue());
 }
 }
}

Answer 1

Correctness:

Your code doesn't seem to actually produce the correct answer.

When I ran this code, I got:

0--5 6--6 7--10 11--11 12--14 15--15

However... the list has 17 elements, so 16--16 is missing.

The reason for this is that once you are done with the for loop, you do handle the case when the last two elements are part of a consecutive range, but in your test case, they aren't.

The way to fix this is very easy: remove the if. It should look like this:

for(int i = 1; i < length ; ++i) { 
 // same as yours
} 
end_index = length - 1;
list.put(start_index, end_index);
return list;

Style:

Aside from the things that Mayur already mentioned,

• Comment your code. It took me many more minutes than it should have to figure out what it does.

• Along the same vein, name things according to what they do. For example, I would rename findList (A completely pointless name... might as well have been foobar) to buildConsecutiveRangeMap. I would also change array1 to numbers, or at least drop the unnecessary "1". Lastly, prog is just a completely meaningless name for a class...rethink this.

• Make " "'s matter. Why do you have extra spaces between public and Map? > and findList? Right before the return? At the same time, you could use more to make length -2 into length - 2, array[index]+1 into array[index] + 1 and so on.

• Don't prematurely optimize. That's the only reason I could see for using another variable to store array1.length instead of using that everywhere. Little secret: It's just a field lookup that takes O(1) time and a modern day JIT will notice that that value is constant and optimize your loop for you.

• Import just the things you need. It's a waste to include everything under the sun.

Other comments

• Test, test, test. Testing would have led you to find the bug and helps developers figure out what you are trying to accomplish based on the expected output.

• To clean things up, I suggest checking if the range is something like 15--15 and instead just print 15.

• Don't waste your time allocating things when you don't need to. You allocate some memory for list1 in main and then in the findList method, you allocate some more. The garbage collector will of course clean this up...but it also makes your code uglier. Just replace your code in main with:

Map<Integer, Integer> rangeMap = findList(numbers);

• Another feature you might want is to print the numbers in order. The fact that the results happened to be in order is coincidence. A Map guarantees nothing about order and it is up to you to sort the data as you like. Testing different numbers and larger data sets will make this clear.

Answer 2

Style

Java coder usually use this style :

public void someFuntion(){
 //something here
}

Instead of C like style

public void someFunction
{
 //something 
}

Static Methods

You used following line in your code

prog prg = new prog();

You don't need to instantiate unnecessarily, instead you should make use of static methods, so a correct definition would be

public static Map<Integer, Integer> findList(int[] array1)

Naming conventions

Java uses Pascal Notation for classes and Camel Notation for methods. So, your class name should start with a capital letter.

Eg : public class MyLinkedList, public class SomeRelevantName

And, function name should begin with lower case, which you have already used.

Misc

1. Proper spacing should be used to improve readability eg : System.out.println(someIntValue + " = " + anotherIntValue);

2. Newlines should be used systematically and throughout the code, eg: 2 Newlines after end of every function, one newline before the class ends etc.