Sliding Window is an efficient approach to solve problems involving contiguous subarrays. It can be used to find the maximum or minimum sum of a contiguous subarray of size k. This approach involves maintaining a "window" that moves from the left to the right of the array, keeping track of the sum of the elements within the window.
Variable Size Sliding Window.
The Variable Size Sliding Window Algorithm, also known as Dynamic Sliding Window, is a technique used for efficiently processing arrays or lists to avoid unnecessary re-computation. Unlike the Fixed Size Sliding Window, where the window size remains constant, the Variable Size Sliding Window allows the window to dynamically adjust its size based on certain conditions.
Approach of Variable Size Sliding Window:
Input: num[] = {2, 3, 1, 2, 4, 3} target = 7 Output: 2 Explanation: The subarray [4,3] has the minimum length among the contiguous subarrays whose sum is greater than or equal to 7.
Algorithm:
// C++ code implementation of finding the minimum length //of the subarray for given sum #include <iostream> #include <vector> #include <climits>
using namespace std;
int minSubarrayLen(int target, vector<int>& nums) { int n = nums.size(); int left = 0, right = 0; int minLen = INT_MAX; int sum = 0; while (right < n) { sum += nums[right]; while (sum >= target) { minLen = min(minLen, right - left + 1); sum -= nums[left]; left++; } right++; } return (minLen == INT_MAX) ? 0 : minLen; } int main() { vector<int> nums = {2, 3, 1, 2, 4, 3}; int target = 7; cout << minSubarrayLen(target, nums) << endl; return 0; }
2
// Java code to find minimum length subarray // for the given target public class VariableSizeSlidingWindow { public static int minSubArrayLen(int target, int[] nums) { int left = 0, right = 0, sum = 0; int minLength = Integer.MAX_VALUE; while (right < nums.length) { sum += nums[right]; while (sum >= target) { minLength = Math.min(minLength, right - left + 1); sum -= nums[left]; left++; } right++; } return minLength == Integer.MAX_VALUE ? 0 : minLength; } public static void main(String[] args) { int[] nums = {2, 3, 1, 2, 4, 3}; int target = 7; int result = minSubArrayLen(target, nums); System.out.println("Minimum Length: " + result); } }
Minimum Length: 2
- Time Complexity: The time complexity is O(n), where n is the length of the input array. This is because each element in the array is processed exactly once.
- Space Complexity: The space complexity is O(1), as we only use a constant amount of space to store the necessary variables.
No comments:
Post a Comment