I found this question by accident. Although it's been a while, I just post it. O(nlogn) time, O(n) space algorithm. This is running Java code. Hope this help people.
import java.util.*;
public class FindSubarrayClosestToZero {
void findSubarrayClosestToZero(int[] A) {
int curSum = 0;
List<Pair> list = new ArrayList<Pair>();
// 1. create prefix array: curSum array
for(int i = 0; i < A.length; i++) {
curSum += A[i];
Pair pair = new Pair(curSum, i);
list.add(pair);
}
// 2. sort the prefix array by value
Collections.sort(list, valueComparator);
// printPairList(list);
System.out.println();
// 3. compute pair-wise value diff: Triple< diff, i, i+1>
List<Triple> tList = new ArrayList<Triple>();
for(int i=0; i < A.length-1; i++) {
Pair p1 = list.get(i);
Pair p2 = list.get(i+1);
int valueDiff = p2.value - p1.value;
Triple Triple = new Triple(valueDiff, p1.index, p2.index);
tList.add(Triple);
}
// printTripleList(tList);
System.out.println();
// 4. Sort by min diff
Collections.sort(tList, valueDiffComparator);
// printTripleList(tList);
Triple res = tList.get(0);
int startIndex = Math.min(res.index1 + 1, res.index2);
int endIndex = Math.max(res.index1 + 1, res.index2);
System.out.println("\n\nThe subarray whose sum is closest to 0 is: ");
for(int i= startIndex; i<=endIndex; i++) {
System.out.print(" " + A[i]);
}
}
class Pair {
int value;
int index;
public Pair(int value, int index) {
this.value = value;
this.index = index;
}
}
class Triple {
int valueDiff;
int index1;
int index2;
public Triple(int valueDiff, int index1, int index2) {
this.valueDiff = valueDiff;
this.index1 = index1;
this.index2 = index2;
}
}
public static Comparator<Pair> valueComparator = new Comparator<Pair>() {
public int compare(Pair p1, Pair p2) {
return p1.value - p2.value;
}
};
public static Comparator<Triple> valueDiffComparator = new Comparator<Triple>() {
public int compare(Triple t1, Triple t2) {
return t1.valueDiff - t2.valueDiff;
}
};
void printPairList(List<Pair> list) {
for(Pair pair : list) {
System.out.println("<" + pair.value + " : " + pair.index + ">");
}
}
void printTripleList(List<Triple> list) {
for(Triple t : list) {
System.out.println("<" + t.valueDiff + " : " + t.index1 + " , " + t.index2 + ">");
}
}
public static void main(String[] args) {
int A1[] = {8, -3, 2, 1, -4, 10, -5}; // -3, 2, 1
int A2[] = {-3, 2, 4, -6, -8, 10, 11}; // 2, 4, 6
int A3[] = {10, -2, -7}; // 10, -2, -7
FindSubarrayClosestToZero f = new FindSubarrayClosestToZero();
f.findSubarrayClosestToZero(A1);
f.findSubarrayClosestToZero(A2);
f.findSubarrayClosestToZero(A3);
}
}
