Sliding Window:
@DSA

Sliding Window:

Day 1/75:

Question: Leetcode (Medium)

Minimum Size Subarray Sum: Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Input: target = 7, nums = [2,3,1,2,4,3]

Output: 2

Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Intuition: This question is really interesting and help us to solve any Sliding Window Problem with little change. We'll maintain two pointers to track the current subarray's start and end. By adjusting these pointers and updating the sum, we aim to find the smallest subarray satisfying the target condition.

Approach:

Initialization: Initialize start and end pointers, minLength to infinity, and sum to 0.

Here start and end pointer defines the starting and end point of window.

Sliding Window Technique:

  • Traverse through the array with the end pointer.
  • Add nums[end] to the sum.
  • While the sum is greater than or equal to the target:Update minLength as the minimum between current minLength and the window size.Subtract nums[start] from the sum and move the start pointer.Increment the end pointer.

Result: Return minLength if found, else return 0.

GitHub Solution : SlidingWindow/MinimumSIzeSubArraySum.java

Time Complexity: The time complexity of this approach is O(n), as we iterate through the array once with two pointers.

Space Complexity: Space complexity is O(1) since we use a constant amount of extra space for variables.


Related Questions:

  • Subarray Product Less Than K(Medium)
  • Count Subarrays With Score Less Than K(Hard)
  • Binary Subarrays With Sum

Reflection: Today's coding session was productive, reinforcing understanding of the sliding window technique. Excited to explore related questions with the same approach and continue the coding journey in the 75 Days Code Challenge!






要查看或添加评论,请登录

Suyash Awathe的更多文章

  • Tree: Add One Row to Tree

    Tree: Add One Row to Tree

    Day 17: Problem Statement: Given the root of a binary tree and two integers val and depth, add a row of nodes with…

  • Monotonic Array / TwoPointer :Trapping Rain Water: Most Asked !!

    Monotonic Array / TwoPointer :Trapping Rain Water: Most Asked !!

    Day 16/75 : Problem : Trapping Rain Water -(Hard) Given n non-negative integers representing an elevation map where the…

  • Stack: April POTD

    Stack: April POTD

    Question: Remove K Digits -(Medium) Given string num representing a non-negative integer num, and an integer k, return…

  • Queue-Array: April POTD

    Queue-Array: April POTD

    Day 14/75: Question: Reveal Cards In Increasing Order -(Medium) You are given an integer array . There is a deck of…

    1 条评论
  • Array: 9 April POTD

    Array: 9 April POTD

    Day 13/75: Question: Time Needed to Buy Tickets -(Easy) There are people in a line queuing to buy tickets, where the…

  • Queue : April POTD

    Queue : April POTD

    Day 12/75: Question: Number of Students Unable to Eat Lunch -(Easy) The school cafeteria offers circular and square…

    1 条评论
  • String : Parentheses : April-POTD

    String : Parentheses : April-POTD

    Day 11/75: Question: Minimum Remove to Make Valid Parentheses -(Medium) Given a string s of , and lowercase English…

    3 条评论
  • String : 5April POTD

    String : 5April POTD

    Day 10/75: Question: Make The String Great -(Easy) Given a string of lower and upper case English letters. A good…

  • String Parentheses : 4April POTD

    String Parentheses : 4April POTD

    Day 9/75: Question: Maximum Nesting Depth of the Parentheses -(Easy) A string is a valid parentheses string (denoted…

  • BackTracking : WordSearch :4April POTD

    BackTracking : WordSearch :4April POTD

    Day 9/75: Question: Word Search -(Medium) Given an m x n grid of characters board and a string word, return true if…

    1 条评论

社区洞察

其他会员也浏览了