0
$\begingroup$

Problem statement: Given an array of N integers, find its number of negative subarrays (i.e sub arrays having negative summation). E.g: for an array $[1,-2, 4, -5, 1]$ there are 9 subarrays whose sum is negative. Subarray means sequential array within an array.

My code: It's complexity is $\theta(n^{2})$ as we can see. I have applied brute force technique. How can I improve my code/pseudocode?

    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;
        }
    }
$\endgroup$
  • $\begingroup$ Looks like $\Theta(n^3)$ to me. $\endgroup$ – gnasher729 Jul 20 '17 at 22:35
  • $\begingroup$ sum should be set to zero just before the "for (j = ..." loop and nowhere else. Try to prove the correctness of your code which requires that sum must be zero just at that point - much easier if that is the point where you set it. $\endgroup$ – gnasher729 Jul 20 '17 at 22:41
  • $\begingroup$ @gnasher729 This code has been successfully passed all the test cases on a competitive platform. We have to set sum = 0 always as to ensure previous summation doesn't reflect in newer summation. And this code checking all $\frac{n*(n+1)}{2}$ sub arrays individually so $\theta(n^{2})$ . $\endgroup$ – Mr. Sigma. Jul 21 '17 at 5:15
  • $\begingroup$ " This code has been successfully passed all the test cases on a competitive platform." -- That doesn't tell us anything about $\Theta$-s. $\endgroup$ – Raphael Jul 22 '17 at 10:00
  • $\begingroup$ And who told you the testcase statement was a reason of complexity question? @Raphael It was to answer code is correct. $\endgroup$ – Mr. Sigma. Jul 22 '17 at 11:27
1
$\begingroup$

An $O(n \log n)$ solution:

Find prefix sums $S[i] = \sum_{k=0}^{i} a[k]$

Set $S[-1] = 0$

Now count the number of inversion pairs in $S[-1], S[0], \dots, S[n-1]$

$\endgroup$
  • 1
    $\begingroup$ Thanks. how this work? Can you little elaborate. I checked with some examples but couldn't understand intuitively why it is working . $\endgroup$ – Mr. Sigma. Jul 22 '17 at 11:38
  • 1
    $\begingroup$ @Fire: $S[j+k], S[j]$ is an inversion pair implies $S[j+k] - S[j] < 0$ and so $a[j+1] + \dots + a[j+k] \lt 0$. The $S[-1]$ helps with sub-arrays starting at $a[0]$. $\endgroup$ – Aryabhata Jul 22 '17 at 16:32

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.