Solve median extremes and segment flips

Part A — Sliding-window median extremes:

• Input: an integer k (1 ≤ k ≤ n) and an array nums of length n.
• For every contiguous subarray of length k, compute its median (for even k, use the lower median).
• Output: the maximum and the minimum among these medians.
• Design an algorithm that runs in O(n log k) time and O(k) space, and describe the data structures used.

Part B — Even-length uniform segmenting with minimal flips:

• Input: a binary array frames of length n.
• You may flip any bits (0↔ 1).
• After flipping, the array must be partitionable into contiguous segments, each of even length and containing identical values (all 0s or all 1s).
• Objective: minimize the number of segments; subject to that minimum, minimize the total number of flips.
• Output: the minimal number of segments and the minimal flips needed to achieve it.
• Describe an algorithm and provide its time and space complexity.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Sliding-Window Median Extremes

You are given an integer k (1 ≤ k ≤ n) and an integer array nums of length n. For every contiguous subarray (window) of length k, compute its median. For even k, use the lower median (the element at 0-based sorted index (k-1)/2). Return a two-element array [maxMedian, minMedian]: the maximum and the minimum among all the window medians.

If k > n, no window of length k exists; return an empty array.

Aim for O(n log k) time and O(k) space. The intended approach maintains a balanced/ordered multiset of the current window (e.g., two heaps, an order-statistics structure, or a sorted container with binary-search insert/delete) so each slide is O(log k).

Constraints

• 1 ≤ k ≤ n is the valid case; if k > n return [].
• 0 ≤ n ≤ 10^5
• -10^9 ≤ nums[i] ≤ 10^9
• For even k, the median is the lower of the two middle elements (sorted index (k-1)/2).

Examples

Example 1

Input: (3, [1, 3, -1, -3, 5, 3, 6, 7])
Output: [6, -1]

Explanation: Windows of size 3 have medians 1, -1, -1, 3, 5, 6; max=6, min=-1.

Example 2

Input: (1, [5, 2, 8, 1])
Output: [8, 1]

Explanation: k=1: each element is its own median; max=8, min=1.

Hints

1. Maintain the current window as an ordered multiset; the lower median is always at sorted index (k-1)//2.
2. On each slide, delete the element leaving the window and insert the one entering it, then read the element at the fixed median index.
3. Track a running max and min of the medians as you go, or collect all medians and reduce — either way the answer is [max, min].
4. Edge case: when k > n there are no windows, so return an empty array.

Even-Length Uniform Segmenting with Minimal Flips

You are given a binary array frames of length n (each value 0 or 1). You may flip any bits (0↔1). After flipping, frames must be partitionable into contiguous segments such that every segment has even length and contains identical values (all 0s or all 1s). First minimize the number of segments; subject to that minimum, minimize the total number of flips. Return a two-element array [minSegments, minFlips].

Because every segment must have even length, the lengths sum to an even number, so a valid partition exists only when n is even. When n is even, the fewest segments is 1 (the whole array as a single even-length uniform block), and the minimal flips to make it uniform is min(count of 1s, count of 0s). For an empty array return [0, 0]. If n is odd, no valid partition exists; return [-1, -1].

Constraints

• 0 ≤ n ≤ 10^5
• frames[i] ∈ {0, 1}
• A valid partition (all segments even-length) exists iff n is even.
• Minimize segment count first, then total flips.

Examples

Example 1

Input: ([1, 0, 0, 1],)
Output: [1, 2]

Explanation: n=4 even; two 1s and two 0s, flip the two of the minority value -> 1 segment, 2 flips.

Example 2

Input: ([0, 0, 0, 0],)
Output: [1, 0]

Explanation: Already uniform and even length: 1 segment, 0 flips.

Hints

1. Every segment has even length, so the segment lengths sum to an even number — a valid partition exists only when n is even.
2. When n is even, one single even-length uniform segment covering the whole array is always valid, so the minimum segment count is 1.
3. With one segment the whole array must be uniform; the cheapest way is to flip the minority value, costing min(#ones, #zeros) flips.
4. Handle the empty array as [0, 0] and odd-length n as impossible ([-1, -1]).

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Part A — Sliding-window median extremes: - Input: an integer k (1 ≤ k ≤ n) and an array nums of length n. - For every contiguous subarray of length k, compute its median (for even k, use the lower median). - Output: the maximum and the minimum among these medians. - Design an algorithm that runs in O(n log k) time and O(k) space, and describe the data structures used. Part B — Even-length uniform segmenting with minimal flips: - Input: a binary array frames of length n. - You may flip any bits (0↔ 1). - After flipping, the array must be partitionable into contiguous segments, each of even length and containing identical values (all 0s or all 1s). - Objective: minimize the number of segments;...

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.