Need help understanding how Binary Search works on prefix sum arrays

Question

I was solving the problem Minimum Size Subarray Sum. I am trying to solve it by using binary search on a prefix sum array that solves the problem in n*log(n) complexity.

I managed to get it working however I do not understand why my solution worked.

---

Thought Process

My thought process is as follows:

• Step 1: Given the original array nums, first I create a prefix sum array as follows:

• Step 2: I then apply the following logic:

    /*
        need to find min r-l+1 such that
        prefix[r] - prefix[l-1] >= k
        prefix[r] - k >= prefix[l-1]
        tgt >= prefix[l-1]
    */
  

• Step 3: I iterate over the prefix[] array - this represents prefix[r]. Since nums has all positive values, the prefix array is always increasing - ie it is sorted. I then use binary search on prefix to find prefix[l-1] values that satisfy the property described above where tgt >= prefix[l-1].

---

Code

My code is as follows:

public int minSubArrayLen(int s, int[] nums) {
    int[] prefix = new int[nums.length];
    int res = Integer.MAX_VALUE;

    for(int i=0; i<nums.length; i++) {
        if(i==0)
            prefix[i] = nums[i];
        else
            prefix[i] = nums[i] + prefix[i-1];
    }

    for(int i = 0; i<prefix.length; i++) {
        int tgt = prefix[i] - s;
        int index = binarySearch(0, i, tgt, prefix);
        if(index >= 0) {
            res = Math.min(res, i-index+1);
        }
    }
    return res == Integer.MAX_VALUE? 0 : res;
}

private int binarySearch(int l, int r, int tgt, int[] a) {
    int res = -1;
    while(l<=r) {
        int mid = l + (r-l)/2;
        if(tgt >= a[mid]) {
            res = mid;
            l = mid+1;
        } else {
            r = mid-1;
        }
    }
    return res;
}

This does not work. So I made the following change to the prefix array such that it starts with 0:

int[] prefix = new int[nums.length+1];
for(int i=0; i<nums.length; i++)
    prefix[i+1] = nums[i] + prefix[i];

And I edited the way the subarray is calculated to account for these changes:

res = Math.min(res, i-index);

And my algorithm now worked.

---

My questions

1. I dont really understand what is happening here. Why did my initial code not work and why did it work when I changed the prefix sum array?

2. What changes do I need to make to my algorithm if I want to use the original prefix sum array (ie the one that does not start with 0)

Answer 1

Your flaw in logic lies at the line

res = Math.min(res, i-index+1);

Because for prefix array, the difference of 2 consecutive elements represent only ONE-length segment of the original array. So on, the formula to calculate the length of the original segment is always i-index, NOT i-index+1.

Yet, if you only fix that line, there is another corner case: what if the valid sum of segment in the original array starts from the beginning? What will you subtract in your prefix array? Henceforth, adding a 0 element at the beginning of the prefix array will resolve this problem, as any other element now have a 0 element to do the subtraction.

Hope that explains how your fix really works.