Solving Tape Equilibrium Problem in Java

Refactor Java code safely — and automatically — with OpenRewrite.

Refactoring big codebases by hand is slow, risky, and easy to put off. That’s where OpenRewrite comes in. The open-source framework for large-scale, automated code transformations helps teams modernize safely and consistently.

Each month, the creators and maintainers of OpenRewrite at Moderne run live, hands-on training sessions — one for newcomers and one for experienced users. You’ll see how recipes work, how to apply them across projects, and how to modernize code with confidence.

Join the next session, bring your questions, and learn how to automate the kind of work that usually eats your sprint time.

Distributed systems often come with complex challenges such as service-to-service communication, state management, asynchronous messaging, security, and more.

Dapr (Distributed Application Runtime) provides a set of APIs and building blocks to address these challenges, abstracting away infrastructure so we can focus on business logic.

In this tutorial, we'll focus on Dapr's pub/sub API for message brokering. Using its Spring Boot integration, we'll simplify the creation of a loosely coupled, portable, and easily testable pub/sub messaging system:

>> Flexible Pub/Sub Messaging With Spring Boot and Dapr

1. Overview

In this tutorial, we’ll introduce the tape equilibrium problem and find an efficient solution. This problem is a common interview question. We’ll see that a good way to approach this problem relies on identifying the equilibrium indexes of an array.

The term tape is a physical metaphor for a sequence of numbers, where cutting it in two creates two parts. Finding the equilibrium point highlights the goal of balancing these two parts to minimize their difference.

2. Presentation of the Problem

Given an array of integers A of size N, with N>=2, the goal is to find the minimum absolute difference between the sums of the two non-empty parts created by splitting the array at any position P (where 0<P<N).

For example, let’s consider the array {-1, 6, 8, -4, 7}:

|A[0] – (A[1] + A[2] + A[3] + A[4])| = |(-1) – (6 + 8 + (-4) + 7)| = 18
|(A[0] + A[1]) – (A[2] + A[3] + A[4])| = |((-1) + 6) – (8 + (-4) + 7)| = 6
|(A[0] + A[1] + A[2]) – (A[3] + A[4])| = |((-1) + 6 + 8) – ((-4) + 7)| = 10
|(A[0] + A[1] + A[2] + A[3]) – A[4]| = |((-1) + 6 + 8 + (-4)) – 7| = 2

As 2 is lower than 6, 10, and 18, in this case, the tape equilibrium of A is 2.

Because of how we write, the sum of lower index elements is commonly called the left sum, and respectively, the sum of upper index elements is the right sum.

3. Algorithm

The naive solution for calculating the tape equilibrium of an array is computing the difference between the left and right sums at every index. However, this requires an inner iteration of the array elements, which hurts the algorithm’s performance.

As a result, we’d prefer to start with computing the partial sums of the array. The partial sum at index i is the sum of all elements of A with indexes lower or equal to i.

In other words, the partial sum array contains the left sums at each index. Then, we can notice that the right sum at index i is the difference between the total sum and the partial sum at index i since A[i+1] + A[i+2] + … + A[N-1] = (A[0] + A[1] + … + A[i] + A[i+1] + … + A[N-1]) – (A[0] + A[1] + … + A[i]).

In a nutshell, we can retrieve both sums from the partial sum array. This solution only needs two consecutive iterations over the array: the algorithm complexity is O(N).

4. Computing Partial Sums

Let’s compute the partial sum array: the value at index i is the sum of all elements of the original array with indices lower or equal to i:

int[] partialSums = new int[array.length];
partialSums[0] = array[0];
for (int i = 1; i < array.length; i++) {
    partialSums[i] = partialSums[i - 1] + array[i];
}

5. Absolute Difference Between Right and Left Sums at a Given Index

Let’s write a method to calculate our absolute difference at a given index. As we remarked, the right sum at index i is equal to the total array sum minus the partial sum at index i. Additionally, we can notice that the total array sum is also the value of the partial sum array at index N-1:

int absoluteDifferenceAtIndex(int[] partialSums, int index) {
    return Math.abs((partialSums[partialSums.length - 1] - partialSums[index]) - partialSums[index]);
}

We have written the method in a way that makes it clear which sum is the right one and which is the left one.

6. Retrieving the Tape Equilibrium

We can now recap everything:

int calculateTapeEquilibrium(int[] array) {
    int[] partialSums = new int[array.length];
    partialSums[0] = array[0];
    for (int i = 1; i < array.length; i++) {
        partialSums[i] = partialSums[i - 1] + array[i];
    }
        
    int minimalDifference = absoluteDifferenceAtIndex(partialSums, 0);
    for (int i = 1; i < array.length - 1; i++) {
        minimalDifference = Math.min(minimalDifference, absoluteDifferenceAtIndex(partialSums, i));
    }
    return minimalDifference;
}

First, we computed the partial sums and then iterated over all array indices to look for the minimal difference between the left and right sums.

As we named our class TapeEquilibriumSolver, we can now check we get the correct result for our example array:

@Test
void whenCalculateTapeEquilibrium_thenReturnMinimalDifference() {
    int[] array = {-1, 6, 8, -4, 7};
    assertEquals(2, new TapeEquilibriumSolver().calculateTapeEquilibrium(array));
}