Print the number of subarrays of an array having negative sums

Question

Problem statement: Given an array of N integers, find and print its number of negative subarrays (i.e sub arrays having negative summation) on a new line.

My code: Taking order of 3 time. How can I improve my java code?

 import java.util.Scanner;
 public class NegativeSumOfArray {
 public static void main(String[] args) {
 Scanner in = new Scanner(System.in);
 int N = in.nextInt(); //Taking size of an array
 int[] arr = new int[N]; 
 for(int i=0;i<N;i++){
 arr[i] = in.nextInt(); // Taking content of the array.
 }
 // Counting number of sub arrays whose summation is negative.
 int sum=0,count=0;
 for(int i=1,k,j;i<=N;i++){
 for(k=1;k<=N-i+1;k++){
 for(j=0;j<i;j++){
 sum += arr[j+k-1];
 }
 if(sum<0)
 count++;
 sum = 0;
 }
 }
 System.out.print(count);
 in.close();
 }
}

• t3chb0t: This does not print anything. Did you forget to post something?
• Maveňツ: This is not a working code, Its something like interview or exam question. so Off Topic to be here.
• Graipher: @Gattsu Interview and exam questions are fine. If you actually solved them correctly yourself and you are actually legally allowed to post everything you post (including the problem description).

Answer 1

Consistency

 for(j=0;j<i;j++){
 sum += arr[j+k-1];
 }
 if(sum<0)
 count++;

It's more common to write the latter control structure

 if (sum < 0) count++;

That is the clearest way to write the single statement version.

But if you're doing that, why not say

 for (int j = 0; j < i; j++) sum += arr[j+k-1];

How do you choose when to use or not use the single statement form?

I find it easiest to never use it. So I'd say

 if (sum < 0) {
 count++;
 }

Then I don't have to consider whether I should use it this time or not.

There are also advantages if someone has to edit it in the future. In particular, it's harder to make editing mistakes.

Keep it simple

 for(int i=1,k,j;i<=N;i++){
 for(k=1;k<=N-i+1;k++){
 for(j=0;j<i;j++){
 sum += arr[j+k-1];

Consider

 for (int i = 0; i < arr.length; i++) {
 for (int k = 1; k <= arr.length - i; k++) {
 for (int j = 0; j <= i; j++) {
 sum += arr[j+k-1];

In the second for, you had N-i+1, which is the same as N-(i-1). But you can change the bounds of i from 1 to N to 0 to N-1. Then you don't need the extra 1. But then you need to change the third for loop to j <= i.

I would rather use arr.length than N, as that's the actual limiting factor.

I added some whitespace for readability.

 for (int i = 0; i < arr.length; i++) {
 for (int k = 0; k < arr.length - i; k++) {
 for (int j = 0; j <= i; j++) {
 sum += arr[j+k];

In the summation step, you have j+k-1. But if we change the bounds of k from 1 to N-i to 0 to N-i-1, we can just do j+k.

I find this version easier to follow when I read it.

 for (int i = 0; i < arr.length; i++) {
 for (int k = 0; k < arr.length - i; k++) {
 long sum = 0;
 for (int j = 0; j <= i; j++) {
 sum += arr[j+k];

You declare sum outside all the for loops. That's not necessary. You could define it just before the third. Then you don't have to reset it at the end of that loop. It will be automatically set whenever you need it.

Using long instead of int avoids the possibility of overflow.

Alternatives

If you have plenty of space or are willing to modify the input array, you can do this with only two levels of loop nesting. You can calculate the sums prior to checking them.

 long[][] sums = new long[arr.length][arr.length];
 for (int i = 0; i < arr.length; i++) {
 sums[i][i] = arr[i];
 }
 for (int start = 0; start < arr.length; start++) {
 for (int end = start + 1; end < arr.length; end++) {
 sums[start][end] = sums[start][end - 1] + arr[end];
 }
 }
 int count = 0;
 for (int start = 0; start < arr.length; start++) {
 for (int end = start; end < arr.length; end++) {
 if (sums[start][end] < 0) {
 count++;
 }
 }
 }

But we can actually do better.

 long[] sums = new long[arr.length];
 sums[0] = arr[0];
 for (int i = 1; i < arr.length; i++) {
 sums[i] = sums[i - 1] + arr[i];
 }
 int count = 0;
 // count the arrays starting with the first element
 for (int end = 0; end < arr.length; end++) {
 if (sums[end] < 0) {
 count++;
 }
 }
 // count the arrays starting with start+1
 for (int start = 0; start < arr.length; start++) {
 for (int end = start + 1; end < arr.length; end++) {
 if (sums[end] - sums[start] < 0) {
 count++;
 }
 }
 }

Less space but the same runtime growth.

Both solutions make use of the fact that a sum of N elements is equal to a sum of N-1 elements plus the Nth element. So we don't have to keep recalculating that, which is the slow part of the original code.

• Mr. Sigma.: Thanks for your efforts. Can there be more efficient code with Less complexity?