This post isn’t really on topic, but anyone with a general interest in algorithms might find it useful.

The following is my entry for Codility’s LongestNonNegativeSumSlice challenge. The temporal and spatial complexity are both O(N). The solution uses a combination of dynamic programming and prefix summation.

The problem definition is that for a given array input parameter — a sequence of integers with possible elemental values of -1, 0 and 1 — return the size of the longest sequence in the array with a sum larger than or equal to zero. For example, the longest sequence in [-1, -1, 0, 0, 1] is four, because the sum of the second to fifth elements is zero.

This problem really highlights the importance of considering the specific details of the problem carefully before implementing a solution. It’s very easy to implement a brute force solution with temporal complexity on the order of or even chase red herrings by looking at the solutions for other similar looking problems, such as those looking for the size of the slice with the maximum sum or the same problem allowing input values from a wider range of values.

Ultimately, the key to the problem lies in the restricted range of possible array element values. Because the smallest and largest values that can be held in the array are -1 and 1 respectively, the sum can only change in either direction by a maximum of 1 in each iteration. Therefore, if you encounter a particular negative value more than once in the prefix sum, the distance between the element following the index recorded the first time you encountered that value and that of any subsequent time you encounter it, necessarily has a sum of 0.

If the input values are [-1,-1, 0, 0, 0, 1], the prefix sum sequence runs as -1, -2, -2, -2, -2, -1. From this sequence, you can see that the element following the first -1 prefix-sum value is the second and the element presenting the subsequent -1 prefix-sum value is the sixth. The size of the sub-array (slice) contributing to this sum is 5 (the number of elements between the second and sixth inclusive). We can also see that the sum of the values from the third to fourth and third to fifth are zero, using the same technique.

There is, of course, an edge case where the prefix-sum value does not fall below zero before the largest sub-array with a sum >= 0 is found. For example: [ 0, 0, 0, 0, 0,-1], [ 0, 0, 0, 0, 0, 0] or [ 1,-1, 1,-1, 1,-1,-1]. For this reason, we also need to keep track of the edge case where the prefix sum is >= 0.

The solution — written in Java here — is relatively simple. A hash map keeps track of the first index location in which each of the negative prefix-sum values are encountered. Each time we re-encounter a previously recorded negative prefix-sum value, we know we have found a sum of zero, so we check whether the size of the sub-array that produces the zero sum value is greater than the incumbent maximum slice and if it is, it becomes the incumbent maximum slice. If the prefix sum is >= 0, then the current index (plus one if the array is zero indexed) becomes the maximum slice.

import java.util.HashMap; import java.util.Map; class Solution { public int solution(int[] A) { int sum = 0; int maxslice = 0; Map<Integer,Integer> sumindex = new HashMap<Integer,Integer>(); for(int i = 0; i<A.length; i++) { sum += A[i]; if(sum >= 0) maxslice = i + 1; else if(sumindex.containsKey(sum)) maxslice = Math.max(maxslice, i - sumindex.get(sum)); else sumindex.put(sum,i); } return maxslice; } }

This implementation iterates over the list of array elements in A once (N iterations). The containsKey and get methods of the HashMap have O(1) temporal complexity, so the temporal complexity of this implementation is therefore O(N) despite the challenge statement predicting worst-case complexity of O(N log N). Spatial complexity is O(N), which is in line with Codility’s expectation for worst-case space complexity. The entry received a score of 100% for correctness and scalability.