Min Length Bimodal Subsequence — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Two Pointers and solve the Min Length Bimodal Subsequence problem optimally.
O(n)O(1)Problem Description
Given an integer array nums where every element is non‑zero, find the length of the shortest contiguous subarray that contains at least one strictly positive number and at least one strictly negative number. If the array lacks either a positive or a negative element, return -1. The algorithm must run in O(n) time and O(1) extra space.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Min Length Bimodal Subsequence"
WHY DOES IT MATTER?
The two‑pointer / sliding‑window pattern is a cornerstone for any problem that asks for optimal sub‑array length under a monotonic condition. Mastering it lets candidates solve a wide class of interview questions efficiently, from minimum size subarrays to longest substrings with constraints.
OPTIMIZATION CHALLENGE
Recognising that the presence of a positive and a negative is a monotone property lets us avoid recomputing the condition for every possible subarray; instead we only need to track the most recent indices of each sign, which collapses the search space to linear time.
REAL-WORLD CONNECTION
Think of a network packet inspector that continuously scans a stream of events and must raise an alert the moment it sees both a request and a corresponding error within the smallest possible time window. The inspector slides a time‑window forward, expanding when new events arrive and contracting once the alert condition is satisfied, mirroring the algorithm.
During coding, keep two variables lastPos and lastNeg; after each element update the relevant variable and, if both are set, compute candidate length = i - min(lastPos, lastNeg) + 1. This eliminates the explicit left pointer and reduces mental overhead.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem asks for the shortest contiguous subarray that contains both a positive and a negative number. A naïve solution would examine every possible subarray, leading to O(n^2) time, which quickly becomes infeasible for large n because the number of subarrays grows quadratically. The optimal solution leverages the two‑pointer (sliding window) paradigm: we expand a right pointer to include elements until the window satisfies the positivity/negativity condition, then we shrink the left pointer to try to minimise the window length while still satisfying the condition. Because each element is visited at most twice—once when the right pointer moves forward and once when the left pointer moves forward—the overall runtime is linear, O(n), and only a few scalar variables are needed, giving O(1) extra space. The key observation is that the property we need (presence of at least one positive and one negative) is monotonic with respect to window expansion: adding more elements cannot invalidate a window that already satisfies the condition. This monotonicity allows us to safely move the left pointer forward once the condition is met, guaranteeing we never miss a shorter valid window. By tracking the most recent indices of a positive and a negative element, we can also compute the minimal distance directly without an explicit left pointer, but the sliding‑window formulation is more intuitive and aligns with the two‑pointer pattern taught in interview settings.
Interview Questions on This Problem
Q1How would you modify the algorithm if the array could contain zeros, and zeros should be ignored when checking for positive/negative presence?
Treat zeros as neutral; they don’t affect the condition. While scanning, only update the last seen positive or negative index when the element is non‑zero. The sliding window logic remains unchanged, still O(n) time and O(1) space.
Q2Can you extend the solution to find the shortest subarray that contains at least k distinct signs (e.g., positive, negative, and zero)?
Yes. Generalise the sliding window to maintain a count of each sign type in a hashmap of size at most 3. Expand the right pointer until the map size reaches k, then contract from the left while preserving the count, updating the answer each time. The complexity stays O(n) because each element enters and leaves the window at most once.
Q3What is the worst‑case scenario for the two‑pointer approach, and why does it still guarantee linear time?
The worst case occurs when the array alternates signs, causing the left pointer to move almost as often as the right pointer. Nevertheless each index is processed a constant number of times (once by each pointer), so the total number of operations is bounded by 2n, i.e., O(n).
Examples
Input
[3,-1,2,5]
Output
2
Explanation: The subarray [-1,2] (indices 1‑2) includes a negative and a positive number. Its length is 2, which is the smallest possible.
Input
[-4,-2,-7]
Output
-1
Explanation: All numbers are negative, so no subarray can contain both signs. The function returns -1.
Input
[1,2,3,4,-5]
Output
5
Explanation: The only negative number is at index 4. The nearest positive is at index 0, so the smallest subarray that contains both signs spans indices 0‑4, i.e., [1,2,3,4,-5]. Its length is 5.
Constraints
- 1 <= nums.length <= 100000
- -10^9 <= nums[i] <= 10^9
- nums[i] != 0
Optimal Approach & Strategy
Use a sliding window or track last positive/negative indices to update the answer in a single linear pass – O(n) time, O(1) space.
Brute Force Approach
Check every possible subarray, test if it contains both signs, and keep the minimum length – O(n^2) time.
Code Solutions
function minLengthBimodalSubsequence(nums) {
const n = nums.length;
if (n === 0) return -1;
// Check if both positive and negative numbers exist
let hasPos = false, hasNeg = false;
for (const x of nums) {
if (x > 0) hasPos = true;
if (x < 0) hasNeg = true;
}
if (!hasPos || !hasNeg) return -1;
let minLen = Infinity;
let lastPos = -1, lastNeg = -1;
for (let i = 0; i < n; i++) {
if (nums[i] > 0) {
lastPos = i;
if (lastNeg !== -1) {
minLen = Math.min(minLen, lastPos - lastNeg + 1);
}
} else if (nums[i] < 0) {
lastNeg = i;
if (lastPos !== -1) {
minLen = Math.min(minLen, lastNeg - lastPos + 1);
}
}
}
return minLen;
}
// Driver code
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
rl.on('line', line => {
lines.push(line);
});
rl.on('close', () => {
const n = parseInt(lines[0]);
const nums = lines[1].split(' ').map(Number);
console.log(minLengthBimodalSubsequence(nums));
});#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int minLengthBimodalSubsequence(vector<int>& nums) {
int n = nums.size();
if (n == 0) return -1;
// Check if both positive and negative numbers exist
bool hasPos = false, hasNeg = false;
for (int x : nums) {
if (x > 0) hasPos = true;
if (x < 0) hasNeg = true;
}
if (!hasPos || !hasNeg) return -1;
int minLen = INT_MAX;
int lastPos = -1, lastNeg = -1;
for (int i = 0; i < n; ++i) {
if (nums[i] > 0) {
lastPos = i;
if (lastNeg != -1) {
minLen = min(minLen, lastPos - lastNeg + 1);
}
} else if (nums[i] < 0) {
lastNeg = i;
if (lastPos != -1) {
minLen = min(minLen, lastNeg - lastPos + 1);
}
}
}
return minLen;
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
cout << minLengthBimodalSubsequence(nums) << endl;
return 0;
}import java.util.*;
import java.io.*;
public class Main {
public static int minLengthBimodalSubsequence(int[] nums) {
int n = nums.length;
if (n == 0) return -1;
// Check if both positive and negative numbers exist
boolean hasPos = false, hasNeg = false;
for (int x : nums) {
if (x > 0) hasPos = true;
if (x < 0) hasNeg = true;
}
if (!hasPos || !hasNeg) return -1;
int minLen = Integer.MAX_VALUE;
int lastPos = -1, lastNeg = -1;
for (int i = 0; i < n; i++) {
if (nums[i] > 0) {
lastPos = i;
if (lastNeg != -1) {
minLen = Math.min(minLen, lastPos - lastNeg + 1);
}
} else if (nums[i] < 0) {
lastNeg = i;
if (lastPos != -1) {
minLen = Math.min(minLen, lastNeg - lastPos + 1);
}
}
}
return minLen;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine().trim());
String[] parts = br.readLine().trim().split("\\s+");
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = Integer.parseInt(parts[i]);
}
System.out.println(minLengthBimodalSubsequence(nums));
}
}def min_length_bimodal_subsequence(nums):
n = len(nums)
if n == 0:
return -1
# Check if both positive and negative numbers exist
has_pos = any(x > 0 for x in nums)
has_neg = any(x < 0 for x in nums)
if not has_pos or not has_neg:
return -1
min_len = float('inf')
last_pos = -1
last_neg = -1
for i, x in enumerate(nums):
if x > 0:
last_pos = i
if last_neg != -1:
min_len = min(min_len, last_pos - last_neg + 1)
elif x < 0:
last_neg = i
if last_pos != -1:
min_len = min(min_len, last_neg - last_pos + 1)
return min_len
if __name__ == "__main__":
import sys
input = sys.stdin.read
data = input().split()
n = int(data[0])
nums = list(map(int, data[1:n+1]))
print(min_length_bimodal_subsequence(nums))function minLengthBimodalSubsequence(nums) {
const n = nums.length;
if (n === 0) return -1;
// Check if both positive and negative numbers exist
let hasPos = false, hasNeg = false;
for (const x of nums) {
if (x > 0) hasPos = true;
if (x < 0) hasNeg = true;
}
if (!hasPos || !hasNeg) return -1;
let minLen = Infinity;
let lastPos = -1, lastNeg = -1;
for (let i = 0; i < n; i++) {
if (nums[i] > 0) {
lastPos = i;
if (lastNeg !== -1) {
minLen = Math.min(minLen, lastPos - lastNeg + 1);
}
} else if (nums[i] < 0) {
lastNeg = i;
if (lastPos !== -1) {
minLen = Math.min(minLen, lastNeg - lastPos + 1);
}
}
}
return minLen;
}
// Driver code
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
terminal: false
});
let lines = [];
rl.on('line', line => {
lines.push(line);
});
rl.on('close', () => {
const n = parseInt(lines[0]);
const nums = lines[1].split(' ').map(Number);
console.log(minLengthBimodalSubsequence(nums));
});Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.