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++){
                sum += arr[j+k-1];
            sum = 0;
  • $\begingroup$ Looks like $\Theta(n^3)$ to me. $\endgroup$
    – gnasher729
    Jul 20, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 11:27

1 Answer 1


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]$

  • 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, 2017 at 11:38
  • 2
    $\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, 2017 at 16:32

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.