LeetCode Q 209 - Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Solution

Method 1: Sliding Window

Time Complexity: O(n)

Code:

public int minSubArrayLen(int s, int[] nums) {
	if (nums == null || nums.length == 0) return 0;
	int left = 0, right = 0, minLength = Integer.MAX_VALUE, sum = 0;
	while (right < nums.length) {
		sum += nums[right];
		while (left <= right && sum >= s) {
			minLength = Math.min(minLength, right - left + 1);
			sum -= nums[left++];
		}
		right++;
	}
	return minLen == Integer.MAX_VALUE ? 0 : minLength;
}

Method 2: Binary Search

Since the given array contains only positive integers, the subarray sum can only increase by including more elements. Therefore, you don’t have to include more elements once the current subarray already has a sum large enough. This gives the linear time complexity solution by maintaining a minimum window with a two indices.

As to NLogN solution, logN immediately reminds you of binary search. In this case, you cannot sort as the current order actually matters. How does one get an ordered array then? Since all elements are positive, the cumulative sum must be strictly increasing. Then, a subarray sum can expressed as the difference between two cumulative sum. Hence, given a start index for the cumulative sum array, the other end index can be searched using binary search

Time Complexity: O(nlogn)

Code:

public int minSubArrayLen(int s, int[] nums) {
	
	int[] sums = new int[nums.length + 1];
	
	for (int i = 1; i < dp.length; i++) 
		sums[i] = nums[i - 1] + sums[i - 1];
	
	int minLength = Integer.MAX_VALUE
	
	for (int i = 0; i < nums.length; i++) {
		
		int end = binarySearch(sums, i + 1, sums.length - 1, s + sums[i]);
		
		if (end == sums.length) 
			break;
		else (end - i < minLength) 
			minLength = end - i;
	}

	return minLen == Integer.MAX_VALUE ? 0 : minLength;
}

private int binarySearch(int[] sums, int lo, int hi, int key) {
	
	while (lo < hi) {
		
		int mid = (sums[lo] + sums[hi]) / 2;
		
		if (nums[mid] >= key) 
			hi = mid - 1;
		else 
			lo = mid + 1;
	}
	
	return lo;
}

Reprint policy