PracHub
QuestionsPremiumLearningGuidesCheatsheetNEW

Quick Overview

This question evaluates algorithmic problem-solving skills for array manipulation with multiplicative constraints, specifically reasoning about subarray products and boundary behaviors; it belongs to the Coding & Algorithms domain and emphasizes practical application of efficient, linear-time algorithm design rather than purely conceptual theory.

  • Medium
  • Bloomberg
  • Coding & Algorithms
  • Software Engineer

Count subarrays with product under target

Company: Bloomberg

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given an array of positive integers nums and an integer T > 1, return the number of contiguous subarrays whose product is strictly less than T. Provide an algorithm that runs in O(n) time with O( 1) extra space beyond the input. Discuss edge cases such as T <= 1 and the presence of 1s in nums, and explain why your approach is correct.

Quick Answer: This question evaluates algorithmic problem-solving skills for array manipulation with multiplicative constraints, specifically reasoning about subarray products and boundary behaviors; it belongs to the Coding & Algorithms domain and emphasizes practical application of efficient, linear-time algorithm design rather than purely conceptual theory.

Given an array of positive integers `nums` and an integer `T`, return the number of contiguous subarrays whose product is strictly less than `T`. Your algorithm should run in `O(n)` time and use `O(1)` extra space beyond the input. Important edge cases: - If `T <= 1`, the answer is `0` because every subarray product of positive integers is at least `1`. - Arrays may contain `1`s. This does not break the sliding-window approach, but it means the product may stay the same when the window expands. Why a sliding window works: because all numbers are positive, multiplying by a new right-end element can only keep the product the same or increase it, and moving the left end rightward can only keep the product the same or decrease it. So we can maintain the smallest valid window ending at each position. If the current valid window is `nums[left:right+1]`, then every subarray ending at `right` and starting anywhere from `left` to `right` is also valid, contributing `right - left + 1` new subarrays.

Constraints

  • `0 <= len(nums) <= 200000`
  • `1 <= nums[i] <= 10^9`
  • `T` may be any integer
  • An `O(n)` time, `O(1)` extra space solution is expected

Examples

Input: ([10, 5, 2, 6], 100)

Expected Output: 8

Explanation: The valid subarrays are [10], [10,5], [5], [5,2], [5,2,6], [2], [2,6], and [6].

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

Expected Output: 6

Explanation: All contiguous subarrays have product 1, so all 3 * 4 / 2 = 6 subarrays are valid.

Input: ([1, 2, 3], 1)

Expected Output: 0

Explanation: Since all numbers are positive, every subarray product is at least 1, so none are strictly less than 1.

Input: ([], 10)

Expected Output: 0

Explanation: An empty array has no subarrays.

Input: ([100], 100)

Expected Output: 0

Explanation: The only subarray has product 100, which is not strictly less than 100.

Input: ([1, 2, 1, 1], 3)

Expected Output: 10

Explanation: Every contiguous subarray in this array has product 1 or 2, both of which are less than 3.

Solution

def solution(nums, T):
    if T <= 1:
        return 0

    left = 0
    product = 1
    count = 0

    for right in range(len(nums)):
        product *= nums[right]

        while left <= right and product >= T:
            product //= nums[left]
            left += 1

        count += right - left + 1

    return count

Time complexity: O(n). Space complexity: O(1).

Hints

  1. Because all elements are positive, try maintaining a window whose product is always less than `T`.
  2. For each right endpoint, once the window is valid, how many different starting positions produce valid subarrays ending there?
Last updated: Apr 28, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Solve meeting and tree problems - Bloomberg (easy)
  • Minimize travel cost with two cities - Bloomberg (easy)
  • Check connectivity between two subway stations - Bloomberg (easy)
  • Design a data structure for dynamic top‑K frequency - Bloomberg (hard)
  • Find tree root and bucket numbers - Bloomberg (hard)