# Current online judgement provides wrong answers for some cases; My O(n) and O(nlogn) solutions

• The current online judgement didn't consider the potential integer overflow problem when calculating the subarray sum.
Below are some test case examples that the online judgement provides wrong answers:

• input:
7
[1,2147483647,6]
output should be 1 while it's 0
• intput :
7
[1,6,2147483647]
output should be 1 while it's 2
• input:
2147483647
[2,2147483646,1]
output should be 2 while it's 0
• input:
2147483647
[1,2147483645,2]
output should be 2 while it's 0

To get right answer, the variable `sum` should be `long` type instead of `int`.

``````public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int result = Integer.MAX_VALUE;
long sum = 0;
int i = 0, j = 0;
while (j < nums.length) {
sum += nums[j++];
while (sum >= s) {
result = Math.min(result, j - i);
sum -= nums[i++];
}
}
// the result can't be equal to Integer.MAX_VALUE,
// because the maximum array length in Java is smaller than Integer.MAX_VALUE
return result == Integer.MAX_VALUE ? 0 : result;
}
}
``````

If we're not supposed to use `long` type, we can use the following solution:

``````public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int result = Integer.MAX_VALUE;
int sum = 0;
int i = 0, j = 0;
while (j < nums.length) {
int newSum = sum + nums[j++];
if (newSum <= 0) {    // integer overflow
// cancel the current step and move pointer i forward
j--;
sum -= nums[i++];
} else {
sum = newSum;
while (sum >= s) {
result = Math.min(result, j - i);
sum -= nums[i++];
}
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
``````

Above are two `O(n)` solutions with two pointers. Below are two binary search solutions run in `O(nlogn)`.

• binary search solution 1:
``````/**
* Calculate the accumulative sum of array nums, then the sum of subarray nums[i:j] should be sums[j] - sums[i - 1].
Iterate through all possible start index of target subarray, and use binary search to find the corresponding minimum end index.
*/
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int result = Integer.MAX_VALUE;
int[] sums = new int[nums.length];//
for (int i = 0; i < sums.length; i++) {
sums[i] = (i == 0 ? 0 : sums[i - 1]) + nums[i];
}
for (int i = 0; i < sums.length; i++) {
int l = i, r = sums.length;
int target = s + (l == 0 ? 0 : sums[l - 1]); //
while (l < r) {
int mid = l + (r - l) / 2;
if (sums[mid] < target) l = mid + 1;
else r = mid;
}
if (l == sums.length) break;    // sum of nums[i:nums.length-1] is smaller than s
result = Math.min(result, l - i + 1);
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
``````
• binary search solution 2:
``````/**
* The possible length is in range [0:n], use binary search to check
whether there exists a subarray with length `mid` and has sum >= s.
If no, there's no subarray with length than `mid` satisfy the condition as well.
*/
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int result = 0;
int l = 1, r = nums.length;    // l starts from 1 because our target is subarray of minimum positive length
while (l <= r) {
int mid = l + (r - l) / 2;
if (existSubArray(s, nums, mid)) {
result = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return result;
}
// check if there exists a subarray of length k that has sum >= s
private boolean existSubArray(int s, int[] nums, int size) {//
int sum = 0;//
for (int i = 0; i < nums.length; i++) {
if (i >= size) sum -= nums[i - size];
sum += nums[i];
if (sum >= s) return true;
}
return false;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.