Equilibrium Index Problem in Java
Given a sequence of size n, array[], we will construct the function int equilibrium(int[] a, int n) that returns -1 in the event of an absence of an equilibrium index or an equilibrium index, if exists.
An array's equilibrium index is an index where the total of the elements at lower and higher indices equals each other.
Example 1:
Input:
int a[] = {-4, 1, 5, 2, -6, 8, 0}
Output:
The equilibrium index of an array is 3.
Explanation:
The given array is {-4, 1, 5, 2, -6, 8, 0} Now according to the definition, we need to perform the sum of the elements at lower indices and the sum of the elements at higher indices, i.e., a[0] + a[1] + a[2] = 2 (lower indices sum) and a[4] + a[5] + a[6] = 2 (higher indices sum) as the lower indices sum is equal to the higher indices sum. Hence, it returns the equilibrium index as 3 for the given array.
Example 2:
Input:
int a[] = {-2, 7, 5, 3, -6}
Output:
The equilibrium index of an array is -1.
Explanation:
The given array is {-2, 7, 5, 3, -6} now, according to the definition, we need to perform the sum of the elements at lower indices and the sum of the elements at higher indices, i.e., a[0] + a[1] = 5 (lower indices sum) and a[3] + a[4] = -3 (higher indices sum) as the lower indices sum is not equal to the higher indices sum. Hence, it returns the equilibrium index as -1 for the given array.
Example 3:
Input:
int a[] = {-2, 7, 5, 4}
Output:
The equilibrium index of an array is -1.
Explanation:
The given array is {-2, 7, 5, 4} since the array consists of an even number of elements (i.e., 4). Therefore, it returns the equilibrium index as -1.
Approach: Naïve Approach
Create use of two loops. The inner loop determines whether the current index selected by the outer loop is an equilibrium index or not after the outer loop iterates through every element.
Algorithm:
Step 1: loop iteration from i=1 to n
Step 1.1: Set a left-sum variable's value to zero.
Step 1.2: Add a[i] to leftsum after iterating through 0 to i
Step 1.3: Set the value of a rightsum variable to 0.
Step 1.4: Iterate through i+1 until n and perform the addition of a[i] to rightsum.
Step 1.5: Check if leftsum and rightsum are equal and then return a[i].
Step 2: If there are no such points exist, then return -1.
Implementation:
FileName: NaiveEquiliIndex.java
import java.io.*;
import java.util.*;
public class NaiveEquiliIndex
{
int equilibriumindex(int a[], int n)
{
int i, j;
int lsum, rsum;
// Check for each index individually until an equilibrium index has been identified.
for (i = 0; i < n; ++i)
{
// performing the left sum
lsum = 0;
for (j = 0; j < i; j++)
lsum += a[j];
// performing the right sum
rsum = 0;
for (j = i + 1; j < n; j++)
rsum += a[j];
// We return the equilibrium index in the instance that the left and right sums are equal.
if (lsum == rsum)
return i;
}
// if an equilibrium index cannot be found, return -1.
return -1;
}
public static void main(String[] args)
{
NaiveEquiliIndex obj = new NaiveEquiliIndex();
int a[] = {-4, 1, 5, 2, -6, 8, 0};
int a_size = a.length;
System.out.println("The Equilibrium index of the given array is: " + obj.equilibriumindex(a, a_size));
}
}
Output:
The Equilibrium index of the given array is: 3
Complexity Analysis:
The time complexity for the equilibrium index problem of the above approach is O(N2), where 'N' represents the number of elements present in an array, and the space complexity is given by O(1).
Approach: Using Array-Sum
The primary objective is to obtain the array's total sum. The left sum, which is initially set to zero, is then updated as you iterate through the array. One by one subtraction of the elements within the loop allows us to obtain the correct sum.
Algorithm:
Step 1: Set the left sum to zero
Step 2: Determine the array's total sum as the sum
Step 3: Continue over the array iteratively, performing the following steps for each index i:
Step 3.1: Adjust the total to obtain the correct amount.
Step 3.2: total = total - a[i]
Step 3.3: The sum obtained is now the rightsum.
Step 3.4: The current index is returned if leftsum equals sum.
Step 3.5: Update the left sum for the subsequent iteration.
Step 3.6: leftsum + a[i] = leftsum
Step4: return -1
Step 5: The equilibrium index is absent if we exit the loop without making a return.
Implementation:
FileName: ArraySumEquiliIndex.java
import java.io.*;
import java.util.*;
public class ArraySumEquiliIndex
{
int equilibriumindex(int a[], int num)
{
int sum = 0; // initializtion of sum of the whole array to zero.
int lsum = 0; // set up leftsum
// Determine the total sum of the array
for (int i = 0; i < num; ++i)
sum += a[i];
for (int i = 0; i < num; ++i)
{
sum -= a[i]; // For index i, the sum obtained is now the rightsum.
if (lsum == sum)
return i;
lsum += a[i];
}
// return 0 if there isn't an equilibrium index found.
return -1;
}
public static void main(String[] args)
{
ArraySumEquiliIndex obj = new ArraySumEquiliIndex();
int a[] = {-4, 1, 5, 2, -6, 8, 0};
int a_size = a.length;
System.out.println("The Equilibrium index of the given array is: " + obj.equilibriumindex(a, a_size));
}
}
Output:
The Equilibrium index of the given array is: 3
Complexity Analysis:
The time complexity for the equilibrium index problem of the above approach is O(N), where 'N' represents the number of elements present in an array, and the space complexity is given by O(1).
Approach: Using Prefix-Sum
The approach is very easy to use and uncomplicated. Making two duplicates of the array's prefix sum is the concept. The array is accessed twice, once from its front end and once from its rear. Once we've calculated the prefix sums for both arrays, run a loop and see if there are any points where the prefix sums from the two arrays are equal. If so, that equilibrium point can be identified.
Algorithm:
Step 1: Create two arrays to hold the array's prefix sum from the front and back.
Step 2: Execute a loop from 1 to N and determine whether, at any given time, the prefix sum of the array from the front and back are equivalent.
Step 3: Return the index if any such index is discovered.
Step 4: Return -1 in the absence of such index
Implementation:
FileName: PrefixSumEquiliIndex.java
import java.io.*;
import java.util.*;
public class PrefixSumEquiliIndex
{
static int equilibriumindex(int a[], int num)
{
if (num == 1)
return (0);
int[] f = new int[num];
int[] b = new int[num];
// Obtaining the prefixsum from the front-end array
for (int i = 0; i < num; i++)
{
if (i != 0)
{
f[i] = f[i - 1] + a[i];
}
else
{
f[i] = a[i];
}
}
// Obtaining the prefixsum from the array's back end
for (int i = num - 1; i > 0; i--)
{
if (i <= num - 2)
{
b[i] = b[i + 1] + a[i];
}
else
{
b[i] = a[i];
}
}
// Determining the equilibrium index by a
// comparison of the front and back sums
for (int i = 0; i < num; i++)
{
if (f[i] == b[i])
{
return i;
}
}
// Return -1 if there is no equilibrium index found.
return -1;
}
public static void main(String[] args)
{
PrefixSumEquiliIndex obj = new PrefixSumEquiliIndex();
int a[] = {-4, 1, 5, 2, -6, 8, 0};
int a_size = a.length;
System.out.println("The Equilibrium index of the given array is: " + obj.equilibriumindex(a, a_size));
}
}
Output:
The Equilibrium index of the given array is: 3
Complexity Analysis:
The time complexity for the equilibrium index problem of the above approach is O(N), where 'N' represents the number of elements present in an array, and the space complexity is given by O(N).
Approach: Using Two Pointers
The approach provided aims to determine an array's equilibrium index, which is defined as an index at which the total of the elements at all lower and higher indexes equals one another.
The sum of the elements to the left and right of the pivot index is tracked by the code using the left and right pointers.
Algorithm:
Step 1: First, the left pointer is initialized to 0, the pivot is set to 0, and the right pointer is set to the total of all the elements in the array, less the first element.
Step 2: After that, the algorithm goes into a while loop, incrementing the pivot index until the pivot index becomes the last index in the array or the left and right pointers are equal.
Step 3: The pivot index is raised and the right pointer is lowered by the value of the element at the current pivot index for each iteration of the loop.
Step 4: The value of an element at the preceding pivot index is added to the left pointer.
Step 5: Next, the method determines whether the left and right pointers are equal. The equilibrium index is returned as the current pivot index if such is the case.
Step 6: The function returns -1, showing that no equilibrium index was reached if the pivot index is the final index in the given array and the left pointer remains not equal to the right pointer.
Implementation:
FileName: PointersEquiliIndex.java
import java.util.List;
import java.io.*;
public class PointersEquiliIndex
{
public int EquilibriumIndex(List<Integer> num)
{
int leftptr = 0, pivot = 0, rightptr = 0;
for (int i = 1; i < num.size(); i++)
{
rightptr += num.get(i);
}
while (pivot < num.size() - 1 && rightptr != leftptr)
{
pivot++;
rightptr -= num.get(pivot);
leftptr += num.get(pivot - 1);
}
return (leftptr == rightptr) ? pivot : -1;
}
public static void main(String[] args)
{
List<Integer> num = List.of(-4, 1, 5, 2, -6, 8, 0);
int index = new PointersEquiliIndex().EquilibriumIndex(num);
System.out.println("The Equilibrium index of the given array is: " + index);
}
}
Output:
The Equilibrium index of the given array is: 3
Complexity Analysis:
The time complexity for the equilibrium index problem of the above approach is O(N), where 'N' represents the number of elements present in an array, and the space complexity is given by O(1).