The O(n) Club: Subarray Product Less Than K (Why Sliding Windows Aren’t Just For Sums)

The O(n) Club: Subarray Product Less Than K (Why Sliding Windows Aren’t Just For Sums)

⚡ TL;DR

Given an array of positive ints (nums) and some innocent integer k, your job is to count how many contiguous subarrays have a product strictly less than k. Brute force makes your CPU sweat, but a sliding window makes it purr. Example Java snippet—run this if you’re feeling like living in 2011:

// Brute force approach: makes your laptop weep
int res = 0;
for (int i = 0; i < nums.length; i++) {
    int prod = 1;
    for (int j = i; j < nums.length; j++) {
        prod *= nums[j];
        if (prod < k) res++;
        else break;
    }
}

🧠 How Devs Usually Mess This Up

Most folks mess this up by (a) thinking “less than k” is “less than or equal to k” (it isn’t, your test cases are laughing), and (b) writing a double-loop brute force that works for arrays sized “about three”. Also, don’t assume sliding windows are only for sums—multiplying works beautifully if you know when to cut your losses and shrink from the left.

🔍 What’s Actually Going On

Imagine you’re pouring drinks at a wild party and want to keep all the guests’ glasses (the window) under a certain alcohol limit (k). As you pour more (move right), if the table tips (product ≥ k), you grab glasses off the left until you’re back under control. Every time the product is safe, all the guest combos from left to right are valid: that’s (right - left + 1) ways to keep your party under control.

🛠️ PseudoCode

• Start with:

  int prod = 1, left = 0, res = 0;

  All sober and well-behaved.
• Expand the window from the right:

  for (int right = 0; right < nums.length; right++) {
      prod *= nums[right];

  Pour another one.
• Shrink the window from the left if needed:

  while (prod >= k && left <= right) {
      prod /= nums[left++];
  }

  Someone got tipsy, so start removing drinks from the left.
• Count valid subarrays at each step:

  res += right - left + 1;

  Every new right gives you this many fresh party combos.

💻 The Code

// Java sliding window; turns O(n^2) sadness into O(n) glory
public int numSubarrayProductLessThanK(int[] nums, int k) {
    if (k <= 1) return 0;
    int prod = 1, left = 0, res = 0;
    for (int right = 0; right < nums.length; right++) {
        prod *= nums[right];
        while (prod >= k && left <= right) {
            prod /= nums[left++];
        }
        res += right - left + 1;
    }
    return res;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Zeros? Chaos. If the input allows zero, your math will explode. The real problem: only positives.
• Ones Everywhere? If nums is packed with ones, you’ll get a flood of valid subarrays. Buckle up!
• k <= 1? No subarray can make product < k, since all are positive. Return 0 and go get coffee.
• Time/Space: O(n) time, O(1) space. Your interviewer will nod approvingly.

🧠 Interviewer Brain-Tattoo

Sliding window isn’t just a sum-only club—mul-tiply the fun, but only if all your members are positive, and you remember how to divide when things get out of hand.