Min sub array size with a given sum

Question

How can the time complexity of the following code be improved (assuming it's \$O(N^2)\$)? What about style and patterns? This code is trying to find the minimum subarray size that adds up to given sum k. Elements should be adjacent.

/**
 * Created by mona on 5/24/16.
 */
public class MinSubArray {
 public static void minSubArray(int[] a, int k){
 int start=-1;
 int end=-1;
 int min=Integer.MAX_VALUE;
 for (int i=0; i<a.length; i++){
 int tmpSum=0;
 for (int j=i; j<a.length && (j-i+1)<min ; j++){
 tmpSum+=a[j];
 if (tmpSum==k){
 start=i;
 end=j;
 min=end-start+1;
 break;
 }
 if (tmpSum>k){
 break;
 }
 }
 }
 if (start==-1 || end==-1){
 System.out.println("No such array exists with sum of "+k);
 }
 while (start<=end){
 System.out.print(a[start]+" ");
 start++;
 }
 }
 public static void main(String[] args){
 int a[] ={1,2,3,-1,2,4,8,9,5,6,-2,-3,10};
 minSubArray(a,5);
 }
}

• Lee: I think this implementation is absolutely fine. You have captured the algorithm and its optimisations succinctly.

Answer 1

1 Coding conventions

The Java coding conventions dictate that any for, if, while construct is preceded by a blank line. So instead of

int dummy = 10;
for (int i = 0; i < dummy; ++i) {
 ...
}

you should write

int dummy = 10;
for (int i = 0; i < dummy; ++i) {
 ...
}

Next, you have no space after the conditions of if statements: Instead of

if (testCondition()){
 ...
}

you should write

if (testCondition()) { // Note the space before '{'!
 ...
}

2 Algorithm

Printing to standard output in an algorithm is a no-no. Suppose you want to use your implementation in a real-world project. Apart from flooding the stdout, you waste time since calling System.out.print* goes down through the Java virtual machine straight to the OS, and is, thus, expensive. So, it would be nicer just return an integer whose value is the index of the leftmost element of the solution.

3 Summa summarum

All in all, I thought about this reimplementation:

public static int minSubArrayV2(final int[] array, final int targetSum) {
 if (targetSum == 0) {
 // Special case: return the index of the first array component whose 
 // value is zero.
 for (int i = 0; i < array.length; ++i) {
 if (array[i] == 0) {
 return i;
 }
 }
 return -1;
 }
 if (targetSum > 0) {
 for (int startIndex = 0; startIndex < array.length; ++startIndex) {
 int sum = 0;
 for (int i = startIndex; i < array.length; ++i) {
 sum += array[i];
 if (sum > targetSum) {
 break;
 } else if (sum == targetSum) {
 return startIndex;
 }
 }
 }
 } else {
 for (int startIndex = 0; startIndex < array.length; ++startIndex) {
 int sum = 0;
 for (int i = startIndex; i < array.length; ++i) {
 sum += array[i];
 if (sum < targetSum) {
 break;
 } else if (sum == targetSum) {
 return startIndex;
 }
 }
 }
 }
 return -1;
} 

Hope that helps.

A note

I spent about two hours thinking about how to improve the time complexity of your algorithm, and did not find any opportunity. However, you could spent \$\Theta(N^2)\$ for preprocessing the array, after which you can do queries in constant time. Consider the following:

public static Map<Integer, Integer> preprocessArray(final int[] array) {
 final Map<Integer, Integer> map = new HashMap<>();
 for (int startIndex = 0; startIndex < array.length; ++startIndex) {
 int sum = 0;
 for (int i = startIndex; i < array.length; ++i) {
 map.putIfAbsent(sum += array[i], startIndex);
 }
 }
 return map;
}
void foo(int[] array) {
 Map<Integer, Integer> map = preprocessArray(array);
 System.out.println(map.get(6));
}

• Lee: Personally I think the for in the OP is a better way to describe the algorithm that your suggestion.
• Bruno Costa: Math.abs would simplify your algorithm.
• coderodde: @BrunoCosta Math.abs where?
• Bruno Costa: @coderodde My bad, does not quite work, but my intention was similar of putting that if (targetSum > 0) inside the for and do only one for.

Answer 2

I came up with a different algorithm with O(n) complexity. It works as follows:

1. We find the first interval that reaches k, this interval contains the start index and the end index.
2. We adjust this interval by removing elements from end if a[start] > a[end] otherwise we remove from the beginning
3. if the sum is less than k then we removed more elements then needed and need to readjust the interval
4. When there is a new interval candidate, repeat from 2, replacing the old interval if this candidate interval is smaller

The implementation in C# is as follows:

public static Tuple<int, int> MinSubArray(int[] a, int k, int fromIndex = 0)
{
 Tuple<int, int> min = null;
 int sum = 0;
 for (int i = fromIndex; i < a.Length; i++)
 {
 sum += a[i];
 int j = i;
 if (sum >= k)
 {
 while (sum >= k && fromIndex < j)
 {
 if (a[j] >= a[fromIndex])
 {
 sum -= a[fromIndex++];
 if (sum < k)
 {
 fromIndex -= 1;
 break;
 }
 }
 else
 {
 sum -= a[j--];
 if (sum < k)
 {
 j += 1;
 break;
 }
 }
 }
 if (min == null || j - fromIndex <= min.Item2 - min.Item1)
 {
 min = Tuple.Create(fromIndex, j);
 fromIndex = j;
 }
 }
 }
 return min;
}