Problem
A sorted array is passed to my method and i have to find the minimum singular value. If no such value is found the method returns 0.
I have created two versions of this method. In the first version, I iterate trough the array twice which works fine but there has to be a way to find the value with one iteration.
In the second version, I iterate through it once but i need it fixed so, that it works if the last index of the array is my minimum singular value e.g {1, 1, 2, 2, 3}.
//First version with two iterations
public int findMinimumSingularValue(int[] array) {
for (int i = 0; i < array.length; i++) {
int countOccurence = 0;
for (int j = 0; j < array.length; j++) {
if (array[i] == array[j]) {
countOccurence ++;
}
}
if(countOccurence == 1) {
return array[i];
}
}
return 0;
}
I’ve tried to implement it with only one iteration, but couldn’t get it to work. Only the first version is up for review, but I’ll leave my attempt at improvement here to illustrate what I have in mind:
//Second version with one iteration which needs to be fixed
public int findMinimumSingularValue(int[] array) {
if(array.length == 0) {
return 0;
}
int isNotUnique = array[array.length - 1];
for (int i = 0; i < array.length; i++) {
if (array[i] != array[i + 1] && array[i] != isNotUnique) {
return array[i];
}
isNotUnique = array[i];
}
return 0;
}
Solution
for (int i = 0; i < array.length; i++) {
int countOccurence = 0;
for (int j = 0; j < array.length; j++) {
if (array[i] == array[j]) {
countOccurence ++;
}
}
if(countOccurence == 1) {
return array[i];
}
}
return 0;
When I look at this, the problem that I see is that you are scanning the entire array to look for duplicates. The array is sorted! Consider
int i = 0;
while (i + 1 < array.length) {
// array[i] has a duplicate iff it is the same as array[i + 1]
if (array[i] != array[i + 1]) {
return array[i];
}
// skip to the next possible smallest value not a duplicate
while (i + 1 < array.length && array[i] == array[++i]) ;
}
// figure out if the last element has no duplicate
return (array.length == 0 || array[i] == array[i - 1]) ? 0 : array[i];
While it may look like it has nested loops, both iterate over the same variable. So the number of comparisons is linear relative to the size of the array.
This works because the array is sorted. All duplicates are adjacent to each other.
The ++i increments i and then returns the now incremented value. i++ stores the value of i, then increments it, and finally returns it. So i++ + 1 is the same thing as ++i. Or vice versa.
class Incrementable {
private int i = 0;
// ++i
public int preincrement() {
i = i + 1;
return i;
}
// i++
public int postincrement() {
int original = i;
i = i + 1;
return original;
}
}
The two forms ++i and i++ are the equivalents of the preincrement and postincrement in this class.
So let’s go through
while (i + 1 < array.length && array[i] == array[++i]) ;
The form
while (isTrue()) ;
just keeps iterating until isTrue returns false. It does nothing in the body of the loop, thus the empty ;. We could also write it
while (isTrue()) {
}
But that just seems longer.
The i + 1 < array.length just keeps us from falling off the back of the array. I.e. we never want to do array[array.length], as that’s an error (attempt to access outside the array).
So the meat of the statement is the array[i] == array[++i]. On any particular iteration, this is just the same as array[i] == array[i + 1]. So long as that is true, we’re still processing the same duplicate. But replacing i + 1 with ++i has the same effect on an individual iteration and moves along. So we have something like an array of
1, 1, 2, 2, 2, 2, 3
i = 0, array[i] = 1, array[++i] = 1, i = 1; equal so keep going
i = 1, array[i] = 1, array[++i] = 2, i = 2; not equal so stop and do the outer while
i = 2, array[i] = 2, array[++i] = 2, i = 3; equal so keep going
i = 3, array[i] = 2, array[++i] = 2, i = 4; equal so keep going
i = 4, array[i] = 2, array[++i] = 2, i = 5; equal so keep going
i = 5, array[i] = 2, array[++i] = 3, i = 6; not equal so stop and do the outer while
While i is 6, we’ll drop out of the inner loop and the outer loop, because 6 + 1 is not less than array.length, which is 7.
(NOTE: While I was posting this answer: @mdfst13 posted his answer, very nice!
I especially like that nested while loop bit. )
I’m not a java programmer, but here is something in Javascript
function minUnique(set) {
for (var i = 0, last, next = set[1]; i < set.length; next = set[i + 2], i++) {
if (last === undefined && set[i] !== next) {
return set[i];
} else if (last !== undefined && next !== undefined && next !== set[i] && last !== set[i]) {
return set[i];
} else if (set[i] > last && next === undefined) {
return set[i];
}
last = set[i];
}
return 0; // nothing was found
}
This is essentially a problem with three phases
- first value
- mid values, those that are not the first and not the last.
- and the last value.
We simply need to test, for each phase, and do our comparisons in each branch of the if else statements.
My solution rely on some variables setup in the for loop initialization.
“last” is the last value seen,
“next” is the next value in the set
and set[i] is the current value.
if “last” is undefined, it’s our first time through the for loop, and if set[0] is not equal to “next”, we have found the lowest unique value the first time through the loop, if true we return set[i];
if “last” is not undefined, and “next” is not undefined, we are midstream. Now we simply need to check if “last” is not the same as set[i] and not equal to “next”, if true we return set[i];
if “next” is undefined, we are on our last iteration, we need to simply check if set[i] is not equal to “last”, if true we return set[i]
At the tail end of every iteration of the loop, we update “last” to set[i], for use in the next iteration.
otherwise, when/if we complete the for loop without returning, there must have been no unique values, so we just return 0.