Find the index that divides an array into two non-empty subarrays with equal sum | O(n) || Code in Java

Given an integer array, find an index that divides it into two non-empty subarrays having an equal sum.

For example, consider array {-1, 6, 3, 1, -2, 3, 3}. The element 3 at index 2 divides it into two non-empty subarrays {-1, 6} and {1, -2, 3, 3} having the same sum. Please note that the problem specifically targets subarrays that are contiguous (i.e., occupy consecutive positions) and inherently maintains the order of elements.

We can solve this problem in O(n) time by using extra space. The idea is to preprocess the array and store the sum of every index’s left and right subarray in two auxiliary arrays. Then we can calculate the left and right sum in constant time for any index.To improve the space complexity to constant, preprocess the given array and store the sum of all array elements in a variable. Then traverse the array and maintain another variable to store the left subarray sum till the current item. Now we can calculate the right subarray sum in constant time by using the following formula:

Right subarray sum = Sum of all elements – (Current element + Left subarray sum)

import java.util.*;

import java.util.stream.IntStream;

public class IndexEqualSum {

   

        public static void main(String[] args) throws Exception {

            Scanner sc = new Scanner(System.in);

           

            String[] str = sc.nextLine().split(" ");

            int i=0, arr[] = new int[str.length];            

            for(String s:str)

                arr[i++] = Integer.parseInt(s);

           

            System.out.println(getIndex(arr));

            sc.close();

        }

        public static int getIndex(int[] arr){

            if(arr.length == 0)

                return -1;

            int total = IntStream.of(arr).sum();

            int lftsum = arr[0];

            for(int i=1;i<arr.length;i++){

                if(lftsum == (total - (arr[i]+lftsum)))

                    return i;

                lftsum += arr[i];

            }

            return -1;

        }

       

}