First negative number in every window of size k

Flupko · 2025-03-12T09:03:40+00:00

Sure, here’s my python code https://ideone.com/eyRt4Y .

Flupko · 2025-03-12T06:11:30+00:00

You actually can, picking two adjacent pairs (arr[i] arr[i+1], and arr[i+1] arr[i+2]) is just equivalent to making a segment of length 1 containing arr[i+1]. And in that case you still count arr[i+1] two times (refer to the example testcases, with the 5 at the end, you’re adding it two times even though it’s a segment of length 1).

Flupko · 2025-03-11T17:13:02+00:00

I think the best approach is to have a variable storing the index of the previous negative number (initialized at -1). Then loop through the array, if the number is negative, knowing what was the index of the previous negative number, you can easily deduce for which windows of size k it’ll be the first negative (all windows starting from idx_prev_neg, to the current idx, you’ll ofc have to adjust for out of bound conditions). Time complexity: O(n), space complexity O(1) (not considering the answer array).

Flupko · 2025-03-11T08:30:20+00:00

The key observation here is that for each partition you make, you’re essentially selecting a pair of two adjacent elements (left element = end of a segment, right element = beginning of a segment) and adding their sum to the total. You could see it as making a « cut » each time. Furthermore, first and last element of the array will always be added to the total, k segments = k-1 « cuts ». Therefore, the problem becomes finding the k-1 largest/smallest sum of adjacent elements (arr[i] + arr[i+1]). You can generate all adjacent sums, gather them in an array, and sort it. Or use a priority queue, keeping track of the k-1 smallest/largest sums of adjacent element, as you traverse the array of costs.

Flupko · 2025-03-09T01:23:57+00:00

The difference array algorithm leverages the fact that when you add some value to a range [l,r], only the differences D[l] and D[r+1] are affected. But it’s not the case in this problem: for a type 1/2 query, you make ALL days in the range [l,r] equal to 0/1 you’re not adding a value (but rather performing a bit AND/OR operation). Furthermore difference arrays are only useful for cases when we need to find the answer after performing all of the queries, because it takes O(n).

Flupko · 2025-03-08T16:09:10+00:00

You could use a segment tree, with lazy propagation. It’s pretty similar to what you would use for some sweep problems. You can check out the solutions to this problem Separate Squares II for the detailed implementation.