Checking whether if start and end has equal number of non-zero integers and contains 3 or more 0 in the center

Question

An array is said to be hollow if it contains 3 or more zeros in the middle that are preceded and followed by the same number of non-zero elements. Write a function named isHollow that accepts an integer array and returns 1 if it is a hollow array, otherwise it returns 0. The function signature is int isHollow(int[ ] a).

---

Note: Please do not use any String functions. No sorting allowed. No additional arrays or data structures allowed.

---

Test Cases:

1. isHollow({1,2,4,0,0,0,3,4,5}) returns true
2. isHollow({1,2,4,0,0,0,1,0,3,4,5}) returns false
3. isHollow({1,2,0,0,0,3,4,5}) returns false
4. isHollow({1,2,4,9, 0,0,0,3,4,5}) returns false
5. isHollow({1,2, 0,0, 3,4}) returns false

private static int isHollow(int[] array) {
    int length = array.length;
    int startCount = 0;
    int endCount = 0;
    int zeroCount = 0;
    int nonZeroCount = 0;

    if (array[0] == 0 || array[length - 1] == 0) return 0;

    for (int i = 0; i < length; i++) {
        if (array[i] != 0) {
            startCount++;
        } else {
            break;
        }
    }
    for (int i = 0; i < length; i++) {
        if (array[i] == 0) {
            zeroCount++;
        } else {
            nonZeroCount++;
        }
    }

    for (int i = length - 1; i >= 0; i--) {
        if (array[i] != 0) {
            endCount++;
        } else {
            break;
        }
    }

    if (startCount == endCount && (startCount + endCount) == nonZeroCount && zeroCount >= 3) {
        return 1;
    }
    return 0;
}

Answer 1

You can determine the correct answer in a single pass, by working your way from the middle of the array outward, or from the ends of the array inward. Let's get started.

Although the problem description states to return 1 if the array is hollow and 0 if it is not, such signature would make no sense in Java. It's only natural, and strongly recommended to use proper boolean true and false, respectively.

To work outward from the center, let's track left and right indexes. If the array has odd number of elements, left and right can both point to the middle element. Otherwise the array has two central elements, let's make left and right point at those.

int mid = nums.length / 2;
int left, right;
if (nums.length % 2 != 0) {
    left = right = mid;
} else {
    left = mid - 1;
    right = mid;
}

Now, let's start moving the left and right indexes outward, as long as both nums[left] and nums[right] are 0, and left > 0.

while (left > 0 && nums[left] == 0 && nums[right] == 0) {
    left--;
    right++;
}

The loop ends either when left reaches the second position of the array, or when nums[left] or nums[right] (or both) are not zero. If left and right were not moved enough, that is, we haven't moved over enough zeros, then the array is not hollow and we can return.

if (right - left < 4) {
    return false;
}

Finally, we need to verify that the rest of the elements are all non-zero. We can do that by continuing to move outward, and aborting if any of the values is 0.

while (left >= 0) {
    if (nums[left] == 0 || nums[right] == 0) {
        return false;
    }
    left--;
    right++;
}

When the loop completes without aborting, we know the array is hollow.

The complete solution, with some more test cases to verify it:

boolean isHollow(int... nums) {
    int mid = nums.length / 2;
    int left, right;
    if (nums.length % 2 == 0) {
        left = mid - 1;
        right = mid;
    } else {
        left = right = mid;
    }

    while (left > 0 && nums[left] == 0 && nums[right] == 0) {
        left--;
        right++;
    }

    if (right - left < 4) {
        return false;
    }

    while (left >= 0) {
        if (nums[left] == 0 || nums[right] == 0) {
            return false;
        }
        left--;
        right++;
    }

    return true;
}

@Test
public void verify_isHollow() {
    assertThat(isHollow(1, 2, 4, 0, 0, 0, 3, 4, 5)).isTrue();
    assertThat(isHollow(1, 2, 4, 0, 0, 0, 1, 0, 3, 4, 5)).isFalse();
    assertThat(isHollow(1, 2, 0, 0, 0, 3, 4, 5)).isFalse();
    assertThat(isHollow(1, 2, 4, 9, 0, 0, 0, 3, 4, 5)).isFalse();
    assertThat(isHollow(1, 2, 0, 0, 3, 4)).isFalse();
    assertThat(isHollow(1, 2, 0, 0, 0, 0, 3, 4)).isTrue();
    assertThat(isHollow(1, 0, 0, 0, 3)).isTrue();
    assertThat(isHollow(1, 2, 0, 0, 0, 0, 3, 4, 5)).isFalse();
    assertThat(isHollow(1, 2, 1, 0, 0, 0, 0, 3, 4)).isFalse();
    assertThat(isHollow(0, 0, 0)).isFalse();
    assertThat(isHollow(0, 0, 0, 0, 0)).isFalse();
    assertThat(isHollow(0, 0, 0, 0, 0, 1)).isFalse();
    assertThat(isHollow(1, 0, 0, 0, 0, 0)).isFalse();
    assertThat(isHollow(1, 0, 0, 0, 0, 0, 2)).isTrue();
}

Answer 2

This looks for a palindrome, similar to the other answers. I prefer to work from the ends inwards rather than from the centre outwards. That way there is no danger of falling off the end of a non-hollow array.

I check for short arrays to avoid problems with indexes falling off the ends of arrays length 0 or 1. Since I'm checking anyway, I throw out length 2 as well.

I have written and commented the code for clarity, since the other answers appear to concentrate more on speed.

I changed the name of the array variable from array to ary. The first is too close to the class name Array.

private static int isHollow(int[] ary) {

    // Return values.
    final int hollow = 1;
    final int notHollow = 0;

    // Shortest possible hollow array is length 3: [0, 0, 0].
    int length = ary.length;
    if (length < 3) {
        return notHollow;
    }

    // Scan outer non-zero numbers.
    // Also check for indexes crossing: [1, 2, 3, 4, 5, 6].
    int lo = 0;           // Low index.
    int hi = length - 1;  // High index.
    while (ary[lo] != 0 && ary[hi] != 0 && hi > lo) {
        lo++;
        hi--;
    }

    // Check for non-zero at either index: not palindrome: [1, 2, 3, 0, 0, 1, 2].
    if (ary[lo] != 0 || ary[hi] != 0) {
        return notHollow;
    }

    // Check for enough space for zeros: [1, 2, 0, 0, 1, 2].
    if (hi - lo < 2) {
        return notHollow;
    }

    // Scan for all zeros between lo and hi: [1, 2, 0, 3, 0, 1, 2].
    // Values at lo and hi already checked.
    for (lo++ ; lo < hi; lo++) {
        if (ary[lo] != 0) {
            return notHollow;
        }
    }

    // If we get here the array is hollow.
    return hollow;

} // end isHollow()

Answer 3

You currently run this algorithm in \$O(n)\$; while you can't cut that down according to Big-O you can still cut it down. If we look at the actual algorithm, you're doing it in three loops that all loop the entire array, so really it's \$O(3n)\$, we can make it \$O(n/2)\$.

First, remember that our elements have to be palindromes as far as how many zero vs. non-zero elements there are. If we theoretically replace non-zero elements with 1, our array has to be a palindrome.

I.e.: 1,2,4,0,0,0,3,4,5 replace non-zero's with 1 => 1,1,1,0,0,0,1,1,1 => isPalindrome = true.

To determine if it's a palindrome we only need to loop \$\lceil{n/2}\rceil\$ times (the \$\lceil\$\$\rceil\$ indicate round-up).

So, that said, let's rewrite this a little:

private static int isHollow(int[] array) {
    int arrayLength = array.length;
    int length = (int)Math.ceil(arrayLength / 2.0);
    int zeros = 0;
    int notZeros = 0;

    for (int i = 0; i < length; i++) {
        int currentElement = array[i] == 0 ? 0 : 1;
        int oppositeElement = array[arrayLength - 1 - i] == 0 ? 0 : 1;
        if (currentElement == 0 && notZeros > 0) {
            zeros++;
        } else {
            if (zeros > 0 || notZeros == 0) {
                return 0;
            }
            notZeros++;
        }

        if (currentElement == oppositeElement) {
            return 0;
        }
    }

    return zeros >= 3;
}