Count the Number of Sign Changes in an Array

1. Overview

In this tutorial, we’ll see two approaches to count the number of sign changes in an array. First, we’ll check a straightforward iterative algorithm that traverses the array and increments a counter whenever it encounters a change in sign.

Then, we’ll leverage Java treams to achieve the same result in a concise, functional style. Along the way, we’ll discuss edge cases, such as zero values. By the end, we’ll understand the problem and the strategies to implement an efficient and readable solution.

2. Iterative Approach

Let’s begin with a straightforward loop that examines each pair of consecutive elements and counts when their signs differ.

To illustrate each approach consistently, we use the following array as an example:

int[] sampleArray = {1, -2, -3, 4, 0, -1, 5};

Let’s implement a method that iterates through the array. Our method will compare the sign of each element with the previous non-zero sign. Then, it increments a counter when a change is detected:

int countSignChanges(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int count = 0;

    int prevSign = Integer.signum(arr[0]);

    for (int i = 1; i < arr.length; i++) {
        int currentSign = Integer.signum(arr[i]);

        if (currentSign != 0 && prevSign != 0 && currentSign != prevSign) {
            count++;
        }

        if (currentSign != 0) {
            prevSign = currentSign;
        }
    }

    return count;
}

This method uses Integer.signum() to normalize values to -1, 0, or 1, which allows for direct sign comparisons. The method skips zero values to avoid counting them as sign changes. Finally, it updates the previous sign only when it encounters a non-zero value.

The algorithm runs in linear time, O(n), where n is the number of elements in the array. It also uses constant space, O(1), making it efficient and suitable for moderate datasets.

Let’s see how the method behaves when applied to the sample array:

@Test
void givenArray_whenExistsSignChanges_thenReturnSignChangesQuantity() {
    int result = countSignChanges(sampleArray);
    assertThat(result).isEqualTo(4);
}

This example shows a complete method invocation. It verifies the expected result based on the sign transitions in the sample array. The count reflects only the valid sign changes, ignoring zeros during the iteration.

3. Using Java Streams

Counting sign changes is naturally an iterative task. However, we can express the same logic using streams. This involves pairing each element with its predecessor and filtering based on sign differences.

First, let’s implement a method that uses streams to calculate the number of sign changes:

int countSignChangesStream(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }

    int[] signs = Arrays.stream(arr)
        .map(Integer::signum)
        .filter(s -> s != 0)
        .toArray();

    return (int) IntStream.range(1, signs.length)
        .filter(i -> signs[i] != signs[i - 1])
        .count();
}

Although more declarative and concise, this approach creates intermediate arrays and streams. Its time complexity remains O(n), but with increased memory usage compared to the imperative version.

Let’s test the stream-based method against the sample array:

@Test
void givenArray_whenUsingStreams_thenReturnSignChangesQuantity() {
    int result = countSignChangesStream(sampleArray);
    assertThat(result).isEqualTo(4);
}

This execution confirms that the functional stream-based approach yields the same result as the imperative one.

4. Conclusion

In this article, we explored two practical approaches to the problem of counting sign changes in an array. The iterative approach provides a clear and efficient solution using simple control structures. It avoids unnecessary memory allocations and is ideal when performance and resource constraints are important.

On the other hand, the Java 8 Streams approach offers a more expressive and declarative alternative. It makes the logic easier to follow for those familiar with functional programming. However, it introduces additional overhead due to intermediate data structures.

Both solutions have the same time complexity of O(n), but they differ in memory usage and style. Choosing between them depends on the context, whether clarity, performance, or adherence to modern Java practices is the priority.