2
\$\begingroup\$

I'm working on the problem:

Given array with positive and negative values, return the maximum alternating slice size; two elements are alternating if they have different signs, zero is treated as both negative and positive.

Time complexity: \$O(N)\$

Space complexity: \$O(1)\$

I developed a working code and would like to know if there is any method to make the code shorter or faster.

public static int maxSizeAlterSlice(int[] a){
    int max_size_so_far = -1;
    int cur_max_size = -1;
    if(a.length == 1)
        return 1;
    int startInd = 0;
    int endInd = 0;
    int i=1;
    int compareInd=0;
    while(i<a.length){
        if((a[compareInd]>=0 && a[i]<=0)||(a[compareInd]<=0 && a[i]>=0)){
            compareInd=i;
            endInd++;
            i++;
        }else{
            cur_max_size = endInd-startInd+1;
            if(max_size_so_far<cur_max_size){
                max_size_so_far = cur_max_size;
            }
            startInd = i;
            compareInd=startInd;
            endInd=startInd;
            i=startInd+1;
        }
    }
    return max_size_so_far;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ I get the result -1 for the array {-1, 1} with your code ... \$\endgroup\$ – Martin R Oct 24 '17 at 11:33
  • 2
    \$\begingroup\$ Are you going to fix this? CR is about reviewing working code. – Btw, does -1, 0, 1 count as an alternating sequence of length 3? \$\endgroup\$ – Martin R Oct 24 '17 at 13:00
  • 1
    \$\begingroup\$ If zero is both negative and positive; are 1, 0, 1 and 1, 0, -1 both valid alternating sequences? \$\endgroup\$ – CiaPan Oct 24 '17 at 15:45
  • 1
    \$\begingroup\$ @SarahM: Note that incorporating feedback from an answer into the question is not allowed on this site, please see What to do when someone answers and what you may and may not do after receiving answers. \$\endgroup\$ – Martin R Oct 25 '17 at 6:50
  • 1
    \$\begingroup\$ I've rolled back you question to Rev 2, as you still included some of wildbagel's advice in your question. \$\endgroup\$ – Peilonrayz Oct 25 '17 at 8:13
4
\$\begingroup\$

Hmm. I'm not sure about faster, but you can shorten your code by about 6 lines by doing things a little more efficiently.

First, I'd move your two initializations at the top to be below your if statement. That if statement short-circuits the whole function (which is fine), but since the statement doesn't use those two variables, we shouldn't instantiate them unless it fails to return: that's more efficient. I would also return a.length rather than 1 (to eliminate a 'magic number').

Next, you can eliminate the cur_max_size variable and its usage. Remove the declaration, then take the whole block involving cur_max_size and max_size_so_far and replace with this:

max_size_so_far = Math.max(endInd - startInd + 1, max_size_so_far);

Next, there are two places where you can use i++ inside of another statement, rather than having it stand on its own. i++ means "increment after the original value is used" so this is safe:

  • Inside of your if conditional (inside the while), delete i++; and change the first statement to be compareInd = i++;
  • Inside of your else statement, remove i = startInd + 1; and change the startInd=i; line to be startInd = i++;. (Yes, the logic works out.)
\$\endgroup\$
1
\$\begingroup\$
  • Give your operators some breathing space.

  • compareInd is confusing. Logically, it is always equal to i - 1, but it is quite hard to infer from the code. Better drop it entirely, and explicitly use i - 1.

  • endInd is equally confusing. It also follows i, and therefore is unnecessary as well.

  • The if...else construct begs to become a loop:

        while (i < a.length) {
            while (alternating(i)) {
                i++;
            }
            length = i - startInd;
            ....
            startInd = i++;
        }
    

    Now it becomes obvious that the outer while is in fact a for:

        for (i = 1; i < a.length; i++) {
            while (alternating(i)) {
                i++;
            }
            ....
            startInd = i;
        }
    
  • An alternation condition could be simplified as a[i-1] * a[i] <= 0, but it is a matter of taste.

\$\endgroup\$
  • 1
    \$\begingroup\$ Depending on the range of the given numbers, a[i-1] * a[i] can overflow. One could cast them to long to be on the safe side. \$\endgroup\$ – Martin R Oct 24 '17 at 17:37

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.