0
\$\begingroup\$

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();
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ This does not print anything. Did you forget to post something? \$\endgroup\$
    – t3chb0t
    Commented Jul 20, 2017 at 16:37
  • \$\begingroup\$ This is not a working code, Its something like interview or exam question. so Off Topic to be here. \$\endgroup\$
    – Maveňツ
    Commented Jul 21, 2017 at 13:45
  • \$\begingroup\$ @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). \$\endgroup\$
    – Graipher
    Commented Jul 21, 2017 at 18:29

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks for your efforts. Can there be more efficient code with Less complexity? \$\endgroup\$
    – Mr. Sigma.
    Commented Jul 22, 2017 at 6:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.