8
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ @Jamal how to get this yellow background effect in the editor, by the way thanks for the work. It certainly looks better. \$\endgroup\$ – John Doe Aug 10 '15 at 4:12
  • \$\begingroup\$ It's a blockquote, which is applied with the quotes button in the editor. \$\endgroup\$ – Jamal Aug 10 '15 at 4:17
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for the review. Thanks indeed. I don't feel mature enough to pass judgement on your answer, but I gladly accept it. \$\endgroup\$ – John Doe Aug 10 '15 at 10:42
2
\$\begingroup\$

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));
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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