First negative integer in every window of size k

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.

Examples:  

Input : arr[] = {-8, 2, 3, -6, 10}, k = 2
Output : -8 0 -6 -6

First negative integer for each window of size k
{-8, 2} = -8
{2, 3} = 0 (does not contain a negative integer)
{3, -6} = -6
{-6, 10} = -6

Input : arr[] = {12, -1, -7, 8, -15, 30, 16, 28} , k = 3
Output : -1 -1 -7 -15 -15 0

Run two loops. In the outer loop, take all subarrays(windows) of size k. In the inner loop, get the first negative integer of the current subarray(window).

-1 -1 -7 -15 -15 0 

Time Complexity : The outer loop runs n-k+1 times and the inner loop runs k times for every iteration of outer loop. So time complexity is O((n-k+1)*k) which can also be written as O(nk) when k is comparatively much smaller than n, otherwise when k tends to reach n, complexity becomes O(k). 

Auxiliary Space: O(1) as it is using constant space for variables

Approach 2: Efficient Approach

We create a Dequeue, Di of capacity k, that stores only useful elements of the current window of k elements. An element is useful if it is in the current window and it is a negative integer. We process all array elements one by one and maintain Di to contain useful elements of current window and these useful elements are all negative integers. For a particular window, if Di is not empty then the element at front of the Di is the first negative integer for that window, else that window does not contain a negative integer.

It is a variation of the problem of Sliding Window Maximum. 

Implementation:

-1 -1 -7 -15 -15 0 

Time Complexity: O(n) 

Auxiliary Space: O(k)

Optimized Approach:: It is also possible to accomplish this with constant space. The idea is to have a variable firstNegativeIndex to keep track of the first negative element in the k sized window. At every iteration, we skip the elements which no longer fall under the current k size window (firstNegativeIndex <= i – k) as well as the non-negative elements(zero or positive). 

Below is the solution based on this approach.

-1 -1 -7 -15 -15 0 

Time Complexity: O(n) 

Auxiliary Space: O(1)

This article is contributed by Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on GeeksforGeek’s main page and help other Geeks.
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.

Using Segment Tree:

Basic Idea towards the approach

The problem requires us to find the first negative integer in each window of size k. To solve this problem efficiently, we can use the segment tree data structure. We can build a segment tree from the input array, where each node in the tree represents a segment of the array. We can store the minimum value of each segment in the node of the segment tree.
To find the first negative integer in each window of size k, we can query the segment tree for the minimum value in each window. If the minimum value in the current window is negative, then it is the first negative integer in that window. Otherwise, we can print 0 for that window.

Follow the steps below to implement the above idea: 

• Define a segment tree data structure that supports range queries for minimum values. The tree should be built from the input array, with each node representing a range of values in the array.
• Traverse the input array, and for each window of size k, query the minimum value from the segment tree. If the minimum value is negative, print it. Otherwise, print 0.
• Implement the segment tree using an array representation, where each node is represented by an index in the array. The root of the tree is at index 0, and for each node at index i, its left child is at index 2i + 1, and its right child is at index 2i + 2.
• To build the segment tree, recursively compute the minimum value for each node in the tree. The minimum value for the root node should be the minimum value of the entire array, and for each non-leaf node, its minimum value should be the minimum of its left and right child nodes.
• To query the minimum value for a given range [l, r], start at the root of the tree and recursively traverse the tree as follows:
• If the current node’s range [i, j] is completely outside the query range [l, r], return a large positive number (such as INT_MAX).
  If the current node’s range [i, j] is completely inside the query range [l, r], return the minimum value stored at the node.
  Otherwise, recursively query the left and right child nodes, and return the minimum of the two values.
  Traverse the input array and for each window of size k, compute the starting and ending indices of the window, and query the minimum value of the range [start_index, end_index] from the segment tree. If the minimum value is negative, print it. Otherwise, print 0.
• Finally, the output will be the list of negative values or 0s for each window of size k in the input array.

Below is the implementation of the above approach:

-8 0 -6 -6 

Time Complexity: O((n + k) log n),

• Building the segment tree takes O(n log n) time, where n is the length of the input array. This is because the tree has at most 4n nodes, and we need to visit each node once to compute its value.
• Querying the minimum value for each window of size k takes O(log n) time, because the height of the tree is log n, and we need to visit at most two nodes at each level of the tree.
• Since we need to do this for each window of size k, the total time complexity of the algorithm is O((n + k) log n).

Space Complexity: O(n),

• Building the segment tree takes O(n) space, because the tree has at most 4n nodes.
• Since we only need to store the segment tree and a few variables to keep track of the indices, the space complexity of the algorithm is O(n).

Using Sliding Window Approach:

Follow the steps below to implement the above idea:

• Initialize a deque dq to store the indices of the negative elements, and initialize a variable start to 0.
• Loop through the array from index 0 to n-1, where n is the size of the array.
• If the deque is not empty and the first index in the deque is less than or equal to the current index minus the window size k, remove it from the deque.
• If the current element is negative, add its index to the back of the deque.
• If the current index is greater than or equal to k-1, output the first negative element in the deque. If the deque is empty, output 0.
• Increment the start variable by 1 to move the window to the right.

Below is the implementation for the above approach:

-1 -1 -7 -15 -15 0 

Time Complexity: O(n), where n is the size of the input array.

Auxiliary Space: O(K) , where K is the Size of the window.