Minimum Size Subarray Sum - Java Solution

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

1. Introduction

This blog post addresses a common problem in array processing using the sliding window technique: finding the length of the smallest contiguous subarray whose sum is greater than or equal to a given number K.

Problem

Given an array of positive integers a and a positive number K, find the length of the smallest contiguous subarray whose sum is greater than or equal to K. Return 0 if no such subarray exists.

2. Solution Steps

1. Use a sliding window approach to find the smallest subarray with the required sum.

2. Maintain a running sum of the elements in the current window.

3. Expand the window until the sum is greater than or equal to K.

4. Once the sum is sufficient, contract the window from the left and update the minimum length.

5. Return the minimum length found; if no such length is found, return 0.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] a1 = {2, 1, 4, 3, 2, 5};
        System.out.println("Smallest subarray length: " + findMinSubArray(a1, 7));

        int[] a2 = {3, 4, 1, 1, 6};
        System.out.println("Smallest subarray length: " + findMinSubArray(a2, 8));

        int[] a3 = {1, 3, 2, 1, 5};
        System.out.println("Smallest subarray length: " + findMinSubArray(a3, 15));
    }

    // Method to find the smallest subarray with a sum greater than or equal to K
    public static int findMinSubArray(int[] a, int K) {
        int windowSum = 0, minLength = Integer.MAX_VALUE;
        int windowStart = 0;

        for (int windowEnd = 0; windowEnd < a.length; windowEnd++) {
            windowSum += a[windowEnd]; // Add the next element

            // Shrink the window as small as possible until the window's sum is smaller than K
            while (windowSum >= K) {
                minLength = Math.min(minLength, windowEnd - windowStart + 1);
                windowSum -= a[windowStart]; // Subtract the element going out
                windowStart++; // Slide the window ahead
            }
        }

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

Output:

Smallest subarray length: 2
Smallest subarray length: 3
Smallest subarray length: 0

Explanation:

The findMinSubArray method applies the sliding window technique to find the smallest subarray whose sum is greater than or equal to K. 

For the input array [2, 1, 4, 3, 2, 5] and K = 7, it calculates the smallest subarray length as 2 ([4, 3]). 

For the second input [3, 4, 1, 1, 6] and K = 8, the smallest subarrays are [3, 4, 1] or [1, 1, 6], both of length 3. In the third example, there is no subarray with a sum greater than or equal to 15, hence the output is 0.

My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:

Build REST APIs with Spring Boot 4, Spring Security 7, and JWT

🆕 High-Demand 80–90% OFF

[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25

🆕 High-Demand 80–90% OFF

ChatGPT + Generative AI + Prompt Engineering for Beginners

🚀 Trending Now 80–90% OFF

Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Real-Time REST APIs with Spring Boot - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Microservices with Spring Boot and Spring Cloud

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Java Full-Stack Developer Course with Spring Boot and React JS

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Build 5 Spring Boot Projects with Java: Line-by-Line Coding

🌟 Top Rated 80–90% OFF

Testing Spring Boot Application with JUnit and Mockito

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot Thymeleaf Real-Time Web Application - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Master Spring Data JPA with Hibernate

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot + Apache Kafka Course - The Practical Guide

🎓 Student Favorite 80–90% OFF
Available in Udemy for Business

Java Testing: Mastering JUnit 5 Framework

🆕 New 80–90% OFF

Reactive Programming in Java: Spring WebFlux and Testing

🌟 Top Rated 80–90% OFF

Spring Boot + RabbitMQ Course - The Practical Guide

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Functional Programming in Java (Includes Java Collections)

🎓 Student Favorite 80–90% OFF

ChatGPT for Java Developers: Boost Your Productivity with AI

🚀 Trending Now 80–90% OFF