Problem
The prompt that made me put this function together was sourced from CodingBat.
I was curious about cleaner, more correct methods of doing putting this together such as finding a cleaner way to tell if there is or is not a duplicate in the array. I am also trying to be as efficient as possible. I believe this is an O(n2) function. Let me know what I should change.
The code works just fine. I just feel like there is quite a lot I can streamline and I would like to be pointed in the right direction.
public int maxSpan(int[] nums) {
int highestSpan = 0;
int span;
boolean duplicate = false;
if (nums.length == 0)
return highestSpan;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++){
if ((nums[i] == nums[j])&& j != i){ //if duplicate
duplicate = true;
//get the absolute value of j - i
span = j - i + 1; //Add 1 because it needs to count itself
//if it is larger than the highestSpan then record it
if (span > highestSpan)
highestSpan = span;
}
}
}
if (duplicate)
return highestSpan;
else
return 1;
}
Solution
Getting rid of duplicate as Janos proposed and then QPaysTaxes wrote is a good step, but this useless variable introduced quite some useless code we should also get rid of. The following code builds up on QPaysTaxes’ answer; I’m commenting on changed things and presenting my variant:
public int maxSpan(int[] nums) {
int highestSpan = 0;
This is not the place where span should be defined. You don’t need it here.
The condition nums.length == 0 can go.
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
Changed the lower bound from i+1 to i to cover span equal to 1. Below removed the i != j test and used max to make the code a bit shorter.
if (nums[i] == nums[j]) {
int span = j - i + 1; // Add 1 to count itself
highestSpan = Math.max(highestSpan, span);
}
}
}
No need for a conditional here.
return highestSpan;
}
I guess, I saved some 6 lines without making it any more complicated. Now can also span be inlined to save 1 more line (but that’s not the objective).
—
Now it works exactly according to the explanation by QPaysTaxes in comment without any special tests:
An empty array doesn’t have any spans, so clearly it has to return 0. An array of unique elements is rather more confusing, but since the prompt states that a single (i.e. unduplicated) element has a span of 1, then an array of unique (i.e. unduplicated [i.e. single]) elements has a maximum span of the span of every unique number
An O(n) solution could look like this (untested):
public int maxSpan(int[] nums) {
int highestSpan = nums.length == 0 ? 0 : 1;
Map<Integer, Integer> firstOccurrenceMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer firstOccurrence = firstOccurrenceMap.get(nums[i]);
if (firstOccurrence == null) {
firstOccurrenceMap.put(nums[i], i);
} else {
highestSpan = Math.max(highestSpan, i - firstOccurrence + 1);
}
}
return highestSpan;
}
As the first occurrence of a number gets a special treatment, the empty array has to be handled specially, too (see the declaration of highestSpan).
Avoid unnecessary flag variables
The variable duplicate is unnecessary, because you could drive the same meaning from highestSpan > 0. It’s an extra hurdle to keep this flag, I suggest to drop it.
Improving the algorithm
I believe this can be solved in O(N) time and space, by using a map to record the position of the first occurrences of numbers. If a number was seen already, check the distance and update the max distance if necessary. Otherwise record the current position.
First: Always use brackets around conditionals, even one-liners. It makes it easier to update later. That’s not a big factor with this code, but it may well be with code you write in the future, and it’s a good habit to get in to.
Add a comment before return 1; explaining that 1 is the default amount because… [your reasoning here].
Comments like this:
//if it is larger than the highestSpan then record it
right before code that explains itself are entirely unnecessary.
Always put spaces both before and after every binary operator — things like &&.
if ((nums[i] == nums[j])&& j != i){ //if duplicate
The first set of parentheses is unnecessary, but doesn’t harm anything. However, you should always try to be consistent — if you parenthesize one side, parenthesize the other side, too. I decided to remove them altogether.
Newlines should separate logically separate code — I like to separate the variable declarations from the calculations bits, unless the variables are one-off little things that are just to make things readable. I also like to separate the bit that returns things from the rest. See the changed code that the bottom for what I mean.
As far as your actual algorithm: Just about the only improvement I could offer is that you should initialize j to i + 1 rather than 0 to avoid extra traversing that you already did, albeit backwards. To clarify, this is what your for blocks should look like (with the insides snipped):
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++){
// [snip!]
}
}
If you want, you can put a ternary instead of the if block at the end; something like this:
return duplicate ? highestSpan : 1;
(Note: I also stole something from janos’ answer — I got rid of duplicate.)
public int maxSpan(int[] nums) {
int highestSpan = 0;
int span;
if (nums.length == 0) {
return highestSpan;
}
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++){
if (nums[i] == nums[j] && j != i){ // if duplicate
//get the absolute value of j - i
span = j - i + 1; //Add 1 because it needs to count itself
if (span > highestSpan) {
highestSpan = span;
}
}
}
}
return highestSpan > 1 ? highestSpan : 1;
}
According to CodingBat, it still works.
You can cut the computational complexity nearly in half.
Your nested for-loop is actually checking each pair of objects twice. Try unwrapping the loop and write out each combination of i and j to see why.
Consider this loop:
for (i = 0 to nums.length) {
for (j = i+1 to nums.length) {
...
}
}
If you unwrap that one, you will see we end up with only unique combinations of i and j, and it eliminates the possibility that i>j (which could make your span variable negative).
You can clearly do this in linear time by writing the array to a multimap. Basically we are going to have a map from value -> list of places where it appears in the array.
So {1, 4, 2, 1, 4, 4, 4} from coding bat would become the map:
1 -> 0,3
2 -> 2
4 -> 1,4,5,6
The span is obviously largest – smallest + 1. You could write a custom map object which just stores the largest and smallest value on a given key.
This is obviously linear. This is similar to the classic trick for finding duplicates, you create a HashSet, and exploit the behaviour of HashSet.add(), which returns true only if add increases the size of the set, so it will return false at the first duplicate.