Problem

Submissions

Hints & solutions

Discuss

First Negative Integer In Every Window Of Size K

Easy

0/40

Average time to solve is 10m

Contributed by

25 upvotes

Asked in companies

Problem statement

You have been given an array of integers 'ARR' and an integer ‘K’. You need to find the first negative integer in each window of size ‘K’.

Note :

If a window does not contain a negative integer, then print 0 for that window.

For example :

If N = 9, arr[ ] = {-10, 20, -30, -40, 50, 60, -70, 80, 90} and K = 3

then the output will be
{-10 -30 -30 -40 -70 -70 -70}

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains an integer ‘N’ which denotes the size of the array.

The second line of each test case contains elements of the array. The line consists of values of elements of the array separated by a single space.

The third line of each test case contains an integer ‘K’ which denotes the window size.

Output Format:

For each test case, print the first negative integer in each window of size ‘K’ separated by a space.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10^2
1 <= N <= 10^3
-10^4 <= data <= 10^4
1 <= K <= N

Where ‘N’ is the size of the array, “data” is the value of the element of the array 'ARR' and ‘K’ is the window size.

Time Limit: 1 sec

Sample Input 1:

1
9
-10 20 -30 -40 50 60 -70 80 90
3

Sample Output 1:

-10 -30 -30 -40 -70 -70 -70

Explanation For Sample Input 1:

Here the first negative integer in the window  of size K = 3 is [-10, -30, -30, -40, -70, -70, -70]

Sample Input 2:

1
6
-10 20 30 -40 -50 60
2

Sample Output 2:

-10 0 -40 -40 -50

Explanation For Sample Input 2:

Here the first negative integer in the window  of size 'K' is [-10, 0, -40, -40, -50]

Hint 1

Hint 2

Think of considering all windows possible and finding the first negative element in each window.

Approaches (2)

Approach 1

Approach 2

Brute Force

Run two loops. In the outer loop, take all windows of size ‘K’.

In the inner loop, get the first negative integer of the current window.

Time Complexity

O(N*K), where ‘N’ is the size of the array and ‘K’ is the size of each window.

There are a total of ‘N-K+1’ windows and in each window, K elements are considered for finding the first negative number. So time complexity is O((N-K+1)*K) which can also be written as O(N*K).

Space Complexity

O(1).

As we are not using an auxiliary space to store data. Hence, the Space complexity is O(1).

(100% EXP penalty)

First Negative Integer In Every Window Of Size K

Console