4
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! On this site we only review working code (which you admit your second code block is not). Have a look at the help center to learn about what is on/-off-topic here. \$\endgroup\$ – Graipher Apr 6 '17 at 6:03
  • 1
    \$\begingroup\$ @Graipher True, but since they're both versions of the same program, one could argue we only review the first block and see the second as a pseudo-code example of what the author would prefer. IMO, this is reviewable. \$\endgroup\$ – Mast Apr 6 '17 at 6:53
  • \$\begingroup\$ @Mast I see your point. Editing the question to make it explicit that only the first code is to be reviewed could help, though. \$\endgroup\$ – Graipher Apr 6 '17 at 7:11
  • 1
    \$\begingroup\$ @Graipher Fixed, kind-of. Fatso88, if you disagree with my edit, feel free to improve it ;-) \$\endgroup\$ – Mast Apr 6 '17 at 7:39
  • \$\begingroup\$ Thanks. I totally see your point there. And thanks @Mast for your edit! \$\endgroup\$ – fatso88 Apr 6 '17 at 7:50
5
\$\begingroup\$
    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.

\$\endgroup\$
  • \$\begingroup\$ wow! this works great. Thank you very much! I'm a little overwhelmed by this part: while (i + 1 < array.length && array[i] == array[++i]) ; I ran the debugger and it does exactly what you say, but why :-) And in that case, how does i++ differ to ++i \$\endgroup\$ – fatso88 Apr 6 '17 at 0:43
  • \$\begingroup\$ this is great. thank you so much for your effort :-) \$\endgroup\$ – fatso88 Apr 6 '17 at 6:46
  • \$\begingroup\$ @fatso88 Look-up the terms pre-increment and post-increment ;-) \$\endgroup\$ – Mast Apr 6 '17 at 6:56
1
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ You've presented an alternative approach without reviewing the code presented by the author. On Code Review, all answers should contain a review. \$\endgroup\$ – Mast Apr 6 '17 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.