Finding the count of negative sub-arrays for a given array

Question

I want to improve my implementation for the following problem:

You are given an array of n integers. A sub-array is "Negative" if sum of all the integers in that sub-array is negative. Count the number of "Negative sub-arrays" in the input array.

Note: Subarrays are contiguous chunks of the main array. For example if the array is {1,2,3,5} then some of the subarrays are {1}, {1,2,3}, {2,3,5}, {1,2,3,5} etc. But {1,2,5} is not an subarray as it is not contiguous.

Input Format:

The first line consists an integer n. The next line will contain n space seperated integers. Value of n will be at most \$100\$. The numbers in the array will range between \$-10000\$ to \$10000\$.

Output Format:

Print the answer to the problem.

I am using two loops. It's clearing the test cases, but can I do it with only one loop?

import java.io.*; import java.util.*; public class Solution { public static void main(String[] args)throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); byte T = Byte.parseByte(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine()); int[] arr = new int[T]; for(int i = 0; i < T; i++){ arr[i] = Integer.parseInt(st.nextToken()); } int sum = 0, count = 0;; for(int i = 0; i < T; i++){ sum = 0; sum += arr[i];// If the number itself is negative count++ if(sum < 0){ count++; } for(int j = i + 1; j < T; j++){ sum += arr[j]; if(sum < 0){// If the most recent sum is -ve, count++ count++; } } } System.out.println(count); } } 

Answer 1

Simplifications

If you look at your main loop:

 int sum = 0, count = 0;; for(int i = 0; i < T; i++){ sum = 0; sum += arr[i];// If the number itself is negative count++ if(sum < 0){ count++; } for(int j = i + 1; j < T; j++){ sum += arr[j]; if(sum < 0){// If the most recent sum is -ve, count++ count++; } } } 

you can see that there are two blocks of code that do the same thing. You can remove one block by noticing that starting the j loop at i instead of i+1 will do the initial check of the number itself. Another thing you could do is move the int sum declaration inside the for loop. So the final result would look like this:

 int count = 0; for (int i = 0; i < T; i++) { int sum = 0; for (int j = i; j < T; j++) { sum += arr[j]; if (sum < 0) {// If the most recent sum is -ve, count++ count++; } } } 

Complexity

As far as your complexity question, I don't believe that you can solve this problem with better than an \$O(n^2)\$ solution, so your two loops seem fine.

Answer 2

It can actually be solved in O(n*logn) using the fact that the total number of negative subarrays will be equal to the number of inversions in the partial sum array accumulator (where accumulator[i] = sum of all elements in arr from 0 to i), plus the number of negative elements in accumulator. We can use a merge-sort variant to obtain this quantity in a divide and conquer fashion. Feel free to ask questions about this approach, it's my first Stack Exchange post!

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static int merge(int[] arr, int left1, int right1, int left2, int right2) { int[] temp = new int[right2 - left1 + 1]; int index1 = left1; int index2 = left2; int temp_index = 0; int inversion_count = 0; while(index1 <= right1 && index2 <= right2) { if(arr[index1] <= arr[index2]) { temp[temp_index] = arr[index1]; index1++; temp_index++; } else { //In this case we add to our inversion count: inversion_count += right1 - index1 + 1; temp[temp_index] = arr[index2]; index2++; temp_index++; } } while(index1 <= right1) { temp[temp_index] = arr[index1]; index1++; temp_index++; } while(index2 <= right2) { temp[temp_index] = arr[index2]; index2++; temp_index++; } for(int i = 0; i < temp.length; i++) { arr[left1 + i] = temp[i]; } return inversion_count; } public static int findNegativeSubarrays(int[] arr, int left, int right) { if(right < left) { return 0; } if(right == left) { if(arr[left] < 0) { return 1; } else{ return 0; } } int mid = (left + right)/2; int num1 = findNegativeSubarrays(arr, left, mid); int num2 = findNegativeSubarrays(arr, mid+1, right); int num3 = merge(arr, left, mid, mid+1, right); return num1 + num2 + num3; } public static void main(String[] args) { int n; Scanner scan = new Scanner(System.in); n = scan.nextInt(); scan.nextLine(); int arr[] = new int[n]; for(int i = 0; i < n; i++) { arr[i] = scan.nextInt(); } int accumulator[] = new int[n]; accumulator[0] = arr[0]; for(int i = 1; i < n; i++) { accumulator[i] = accumulator[i-1] + arr[i]; } System.out.println(findNegativeSubarrays(accumulator, 0, n-1)); } }