Problem Statement

Given an array of integers nums and an integer k, return the first negative integer in every window of size k. If there are no negative integers in the window, consider the result as 0.

Examples

Example 1:

Input: nums = [1, -2, 3, -4, 5], k = 2

Output: [-2, 0, -4, -4]

Explanation:

Window [1, -2] contains the first negative integer -2.
Window [-2, 3] does not contain any negative integers. Hence, the result is 0.
Window [3, -4] contains the first negative integer -4.
Window [-4, 5] contains the first negative integer -4.

Example 2:

Input: nums = [2, 1, -3, 4, -1, -2], k = 3

Output: [-3, -3, -3, -1]

Explanation:

Window [2, 1, -3] contains the first negative integer -3.
Window [1, -3, 4] contains the first negative integer -3.
Window [-3, 4, -1] contains the first negative integer -3.
Window [4, -1, -2] contains the first negative integer -1.

Different Approaches

1 Brute Force Approach

Algorithm:

1. Iterate through the array from index 0 to n - k.
2. For each window of size k, check if there is any negative integer.
3. If a negative integer is found, add it to the result. Otherwise, add 0 to the result.

Code Implementation in C++:

#include <iostream>
#include <vector>

using namespace std;

vector<int> firstNegative(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> result;

    for (int i = 0; i <= n - k; i++) {
        bool found = false;
        for (int j = i; j < i + k; j++) {
            if (nums[j] < 0) {
                result.push_back(nums[j]);
                found = true;
                break;
            }
        }
        if (!found) {
            result.push_back(0);
        }
    }

    return result;
}

Complexity Analysis:

Time Complexity:O(n*k), where n is number of elements, while k is the size of the window.

Space Complexity:O(1), we use a constant space of extra space.

2 Sliding Window with Deque

Algorithm:

1. Initialize two pointers left and right to 0.
2. Initialize an empty deque dq to store indices of negative integers within the window.
3. Iterate through the array using the sliding window approach:
   1. If the element at the current index right is negative, push it to the back of the deque.
   2. If the window size equals k:
      1. If the deque is not empty, the front of the deque contains the first negative integer within the window. Append it to the result vector.
      2. If the deque is empty, there is no negative integer in the window. Append 0 to the result vector.
      3. Move the left pointer left to slide the window:
         1. If the element at the left pointer is negative and the deque is not empty, remove the left element from the deque.
   3. Move the right pointer right to expand the window.
4. Return the result vector containing the first negative integer in every window of size k.

Code Implementation in C++:

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

vector<int> firstNegative(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> result;
    deque<int> dq; // Deque to store indices of negative integers within the window

    int right = 0, left = 0; // Initialize two pointers for the sliding window

    while(right < n) {
        // If the element at the current index is negative, push it to the back of the deque
        if (nums[right] < 0) {
            dq.push_back(nums[right]);
        }
        
        // If the window size equals k
        if (right - left + 1 == k) {
            // If the deque is not empty, the front of the deque contains the first negative integer within the window
            if (!dq.empty()) {
                result.push_back(dq.front());
            } else {
                // If the deque is empty, there is no negative integer in the window, so add 0 to the result
                result.push_back(0);
            }
            
            // Move the left pointer to slide the window
            // If the element at the left pointer is negative and the deque is not empty, remove the left element from the deque
            if (nums[left] < 0 && !dq.empty()) {
                dq.pop_front();
            }
            left++;
        }
        
        // Move the right pointer to expand the window
        right++;
    }

    return result;
}

int main() {
    vector<int> nums = {-1, -2, 3, -4, 5};
    int k = 2;
    vector<int> result = firstNegative(nums, k);
    cout << "First negative integer in every window of size " << k << ":" << endl;
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

Complexity Analysis:

Time Complexity:O(n)

• We iterate through the array only once.

Space Complexity:O(k)

• We use a deque dq to store negative integers within the window.
• The maximum size of the deque is k.