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²)?