First negative integer in every window of size k with auxiliary space O(1) and O(n) time complexity

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

package com.slidingwindow;
public class demo2 {
public static void  maximum(int arr[], int k) {
int index = -1;
boolean flag = false;
int i = 0, j = 0, sum = 0;
while (j < arr.length) {
if(arr[j]<0 && !flag) {
index =j;
flag = true;
System.out.println(arr[index]);
}
if (j - i + 1 < k) {
j++;
} else if (j - i + 1 == k) {
if(!flag) {
System.out.println("0");
i++;
j++;
}else {
//slide window by incrementing i and j
i++;
j++;
flag = false;a
}
}
}
}
public static void main(String[] args) {
int arr[] = { -2, 5, 1, 8, -2, 9, -1 };
int k = 2;
maximum(arr, k);
}
}

Expected output

-2

0

0

-2

-2

-1

Actual

-2

0

0

-2

0

-1

I tried to understand your logic, but I couldn't quite get it. Here's what I came up with, starting pretty much from scratch:

class demo2 {
public static void maximum (int arr[], int k){
for (int j = 0; j < arr.length - k + 1; j++) {
boolean found = false;
for (int x = j; x < j + k; x++) {
if (arr[x] < 0) {
System.out.println(arr[x]);
found = true;
break;
}
}
if (!found)
System.out.println(0);
}
}
public static void main(String[] args) {
int arr[] = { -2, 5, 1, 8, -2, 9, -1 };
int k = 2;
maximum(arr, k);
}
}

Result:

-2
0
0
-2
-2
-1

I recognize that there might be a more efficient way of doing this to the point that it would matter, if both the array length and the window size were significantly large. But your question doesn't state that this is the case. This is a place where you need to be sure you want to spend the time to optimize beyond the simple and obvious solution.

It can be implemented with real linear complexity O(n) (as opposite to the naive implementation with <s>polynomial</s> complexity O(n*k)):

public static void maximum (int arr[], int k) {
    int index = -1;
    for (int i = arr.length - 1; i >= 0; i--) {
        if (index >= i + k) {
            index = -1;
        }
        if (arr[i] < 0) {
            index = i;
        }
        arr[i] = index >= 0 ? arr[index] : 0;
    }
    for(int i = 0; i <= arr.length - k; i++) {
        System.out.println(arr[i]);
    }
}

UPDATE: or even better, without writing to the arr array:

public static void maximum (int arr[], int k) {
    int index = -1;
    for (int i = 0; i < arr.length - k + 1; i++) {
        if(index < i) {
            // Find the index of the next negative number
            do {
                index++;
            } while (index < arr.length && arr[index] >= 0);
        }
        // If the next negative number is within the window print it,
        // otherwise print "0"
        System.out.println(index < i + k ? arr[index] : 0);
    }
}

Comparison with the naive algorithm O(n*k) in terms of the number of iterations of the (internal) loop (worst case scenario, i.e. when there are no negative numbers in the table at all):

            | naive        | dynamic |
| O((n-m+1)*m) | O(n)    |
--------------------------------------
n=7,  m=2 |           12 |       7 |
n=10,  m=2 |           18 |      10 |
n=100, m=10 |          910 |     100 |
n=100, m=50 |         2550 |     100 |     

I have a c++ solution, also i have submitted this code on gfgs practice problem and it got accepted. Time complexity is O(n) and auxiliary space complexity is O(K)

vector<int> firstNegative(vector<int> arr, int lenn, int k)
{
vector <int> ans;
int start = 0, end = 0;
queue <int> index;
while(start <= lenn-k)
{
if(arr[end] < 0)
index.push(end);
if(k == (end-start+1))
{
if(index.empty())
ans.push_back(0);
else
{
if(index.front()>=start && index.front()<=end)
ans.push_back(arr[index.front()]);
else
{
index.pop();
continue;
}
}
start++;
}
end++;
}
return ans;
}

     Deque<Long> queue = new LinkedList<>();
int C=N-K+1;
long[] output = new long[C];
int c = -1;
int startWindow = 0;
int endWindow =K;
boolean firstFlag=true;
while (true) {
for(int j=startWindow;j<endWindow;j++){
if(A[j] < 0 && firstFlag){
//  queue.add(A[j]);
if(c<C-1){
output[++c]=A[j];
}
firstFlag=false;
break;
}
if(j>=N-1) {
break;
}
}
if(firstFlag){
if(c<C-1){
output[++c]=0;
}
//  queue.add((long)0);
}
if(endWindow>=N){
break;
}
firstFlag=true;
startWindow=startWindow+K-1;
endWindow=startWindow+K;
}
// 		while(!queue.isEmpty())
// 		      output[++c] = queue.remove();
return output;

function one_loop() {
$arr = [-12, -1, 7, -8, 15, 30, -16, -30, 40, 3];
$arr_len = count($arr); // 7
$result = [];
$k = 2;
$i = 0;
$j = 0;
while ($j < $arr_len && $i < $arr_len-$k+1) {       
$flag = false;
$window_size = $j-$i+1;
if($arr[$j] < 0) {
array_push($result, $arr[$j]);
$flag = true;
}
if($window_size == $k && $flag == false){
array_push($result, 0);
$i++;
$j = $i;
} elseif ($flag == true) {
$i++;
$j = $i;
} elseif ($flag == false && $window_size != $k) {
$j++;
}
}
echo implode($result, ", ");
}