# O(N),O(NLogN) solutions, both O(1) space

• O(N) - keep a moving window expand until sum>=s, then shrink util sum<s. Each time after shrinking, update length. (similar to other solutions, just removed unnecessary min value assignment)

``````public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int i = 0, j = 0, sum = 0, min = Integer.MAX_VALUE;
while (j < nums.length) {
while (sum < s && j < nums.length) sum += nums[j++];
if(sum>=s){
while (sum >= s && i < j) sum -= nums[i++];
min = Math.min(min, j - i + 1);
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
}
``````

O(NLogN) - search if a window of size k exists that satisfy the condition

``````public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int i = 1, j = nums.length, min = 0;
while (i <= j) {
int mid = (i + j) / 2;
if (windowExist(mid, nums, s)) {
j = mid - 1;
min = mid;
} else i = mid + 1;
}
return min;
}

private boolean windowExist(int size, int[] nums, int s) {
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;
}
}
``````

Another O(NLogN) solution that first calculate cumulative sum and then for each starting point binary search for end position. This uses O(N) space

``````public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int sum = 0, min = Integer.MAX_VALUE;

int[] sums = new int[nums.length];
for (int i = 0; i < nums.length; i++)
sums[i] = nums[i] + (i == 0 ? 0 : sums[i - 1]);

for (int i = 0; i < nums.length; i++) {
int j = findWindowEnd(i, sums, s);
if (j == nums.length) break;
min = Math.min(j - i + 1, min);
}

return min == Integer.MAX_VALUE ? 0 : min;
}

private int findWindowEnd(int start, int[] sums, int s) {
int i = start, j = sums.length - 1, offset = start == 0 ? 0 : sums[start - 1];
while (i <= j) {
int m = (i + j) / 2;
int sum = sums[m] - offset;
if (sum >= s) j = m - 1;
else i = m + 1;
}
return i;
}
``````

}

• Excellent answer! Thanks you for sharing!

• the 2nd O(N*lgN) is innovative!

• Amazing, are you binary search the size of the window? It's really a out of the box idea!

• @crackAlgo The two pointer solution : while (sum < s && j < nums.length) this can be removed

• @crackAlgo the second solution is not O(NlogN); it need visit from 1 to n, and find the sum great than s is not constant value. (depends on the min length).

• I love your second solution! I rewrite it in C++:

``````class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int left = 1, right = nums.size(), min_len = 0;
while(left <= right) {
int mid = left + (right - left) / 2;
// if the current window size satisfy, we can try to find smaller window size;
if(windowExist(mid, nums, s)) {
right = mid - 1;
min_len = mid;
}
else {
left = mid + 1;
}
}
return min_len;
}

bool windowExist(int size, vector<int>& nums, int s) {
int sum = 0;
for(int i = 0; i < nums.size(); ++i) {
if(i >= size) sum -= nums[i - size];
sum += nums[i];
if(sum >= s) return true;
}
return false;
}
};
``````

• Very nice O(NlogN) solution. Learned a lot! Thanks!

• I think the third version is more efficient in time since it utilize more space compared to version 2 which is O(1) space. Essentially, they are the "same", we are just changing the order of two loops. Anyway, as a practice, the following is a c++ implementation. I like to use left < right in while-loop. Finally, just test whether the last number we found is valid or not.

``````class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int left = 1, right = nums.size();
while (left < right) {
int mid = left + ((right - left) >> 1);
if (existWindow(nums, mid, s)) right = mid;
else left = mid + 1;
}
return existWindow(nums, right, s) ? right : 0;
}
bool existWindow(vector<int> &nums, int size, int s) {
int sum = 0;
for (int i = 0; i < nums.size(); ++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.