First Negative Number in Every Window of Size K - 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

In this blog post, we address a problem that involves finding the first negative number in every window of a given size in an array of integers. This problem is a variant of the sliding window technique and demonstrates how to handle subarrays within a given range.

Problem

Given an array of integers a and a positive integer k, the task is to find the first negative integer for each and every window (contiguous subarray) of size k. If a window does not contain a negative integer, then print 0 for that window.

2. Solution Steps

1. Use a deque (double-ended queue) to keep track of the negative numbers in the current window.

2. Slide the window across the array, adding and removing elements from the deque.

3. Print the front of the deque as the first negative number for each window. If the deque is empty, print 0.

4. Ensure that the deque only contains elements from the current window.

3. Code Program

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        int[] a1 = {-5, 1, 2, -6, 9};
        printFirstNegativeNumber(a1, 2);

        int[] a2 = {10, -1, -5, 7, -15, 20, 18, 24};
        printFirstNegativeNumber(a2, 3);
    }

    // Method to print the first negative number in every window of size k
    public static void printFirstNegativeNumber(int[] a, int k) {
        Deque<Integer> deque = new LinkedList<>();

        // Process the first window
        for (int i = 0; i < k; i++) {
            if (a[i] < 0) {
                deque.addLast(i);
            }
        }

        for (int i = k; i < a.length; i++) {
            // Print the first negative number of the previous window
            if (!deque.isEmpty()) {
                System.out.print(a[deque.peek()] + " ");
            } else {
                System.out.print("0 ");
            }

            // Remove the elements which are out of this window
            while (!deque.isEmpty() && deque.peek() <= i - k) {
                deque.removeFirst();
            }

            // Add the current element to the deque if it is negative
            if (a[i] < 0) {
                deque.addLast(i);
            }
        }

        // Print the first negative number for the last window
        if (!deque.isEmpty()) {
            System.out.print(a[deque.peek()]);
        } else {
            System.out.print("0");
        }
        System.out.println();
    }
}

Output:

-5 0 -6 -6
-1 -1 -5 -15 -15 0

Explanation:

The printFirstNegativeNumber method uses a deque to track negative numbers in each sliding window of size k. It prints the first negative number from the deque for each window. If the deque is empty (meaning no negative number in the window), it prints 0. 

For instance, in the first example with a[] = {-5, 1, 2, -6, 9} and k = 2, the output is -5 (from window {-5, 1}), 0 (from {1, 2}), -6 (from {2, -6}), and -6 (from {-6, 9}).

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