Counting contiguous subarrays with a negative sum

Question

I'm doing a coding challenge that asks to count the number of contiguous subarrays that have a negative sum:

A subarray of an n-element array is an array composed from a contiguous block of the original array'selements. For example, if array = [1,2,3], then the subarrays are [1], [2], [3], [1,2], [2,3], and [1,2,3]. Something like [1,3] would not be a subarray as it's not a contiguous subsection of the original array.

The sum of an array is the total sum of its elements. An array's sum is negative if the total sum of its elements is negative. An array's sum is positive if the total sum of its elements is positive. Given an array of integers, find and print its number of negative subarrays on a new line.

I wrote this method and I'm trying to figure out the runtime for it but I'm not sure how to handle the loop and the recursion. Assume the length of array a is > 0.

int numNegatives(int[] a){

    if(a.length == 1){ 
        if(a[0] < 0){ return 1; } else { return 0; } 
    }
    
    int count = 0;
    int sum = 0;

    for(int i = 0; i < a.length; i++){ //N
        sum += a[i];
        if(sum < 0){ count++; }
    }
    count += numNegatives(Arrays.copyOfRange(a, 1, a.length));//N-1
    
    return count;
}

The for loop will be O(N), since it loops over the array, and I believe the recursion call will then be O(N-1). Since the recursion call is outside the for loop, does that make the total O(N)? Most solutions to this challenge are two nested for loops with O(N²) runtime, and so I'm not sure if I actually made any improvement. Is it worse than O(N²)?

Answer 1

To get a rough idea, you could consider: how 'deep' does the recursion go, and for each layer, how much work has to be done? See for example the tree in 8.2 Worst-case partitioning, as this is similar to what we have here.

• Recurse for every element in the list, so the depth of the recursion tree is of the order n.
  • For each layer, there is the for loop, which is of the order n, and the array copying, which is also of the order n. So for each layer, there of the order O(n) amount of work to do.

So the algorithm does have complexity O(n^2). Also, is it really necessary to make the copy of the array each time? If your function had a second int start parameter (which is incremented with each recursive call), you could begin the for loop from further down the array with each recursive call, without the need for copies.

This might be a bit crude (and perhaps misleading if you choose the wrong scale), but you can always test it out with some different input sizes to see what happens. Note that with arrays above around 25000 elements I was getting StackOverflowErrors (although rereading the HR task, it was given the array size <= 100). You could do this by generating some random input of different sizes, and timing your function: