-
Notifications
You must be signed in to change notification settings - Fork 25
/
First_negative_integer_in_every_window_of_size_k.java
61 lines (51 loc) · 1.56 KB
/
First_negative_integer_in_every_window_of_size_k.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// { Driver Code Starts
//Initial Template for Java
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine().trim()); // Inputting the testcases
while (t-- > 0) {
int n = Integer.parseInt(br.readLine().trim());
long a[] = new long[(int) (n)];
// long getAnswer[] = new long[(int)(n)];
String inputLine[] = br.readLine().trim().split(" ");
for (int i = 0; i < n; i++) {
a[i] = Long.parseLong(inputLine[i]);
}
int k = Integer.parseInt(br.readLine().trim());
Compute obj = new Compute();
long answer[] = obj.printFirstNegativeInteger(a, n, k);
int sz = answer.length;
StringBuilder output = new StringBuilder();
for (int i = 0; i < sz; i++)
output.append(answer[i] + " ");
System.out.println(output);
}
}
}
class Compute {
public long[] printFirstNegativeInteger(long A[], int N, int K) {
long[] ans = new long[N + 1 - K];
int index = 0;
Deque<Integer> q = new LinkedList<Integer>();
for (int i = 0; i < K; i++) {
if (A[i] < 0) {
q.addLast(i);
}
}
for (int i = K; i < N; i++) {
ans[index++] = q.isEmpty() ? 0 : A[q.peek()];
while (!q.isEmpty() && q.peek() <= i - K) {
q.removeFirst();
}
if (A[i] < 0) {
q.addLast(i);
}
}
ans[index++] = q.isEmpty() ? 0 : A[q.peek()];
return ans;
}
}