Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Subarrays with Product Less than a Target (medium)

Problem Statement

Try it yourself

Problem Statement

Given an array with positive numbers and a positive target number, find all of its contiguous subarrays whose product is less than the target number.

Example 1:

Input: [2, 5, 3, 10], target=30                                              
Output: [2], [5], [2, 5], [3], [5, 3], [10]                           
Explanation: There are six contiguous subarrays whose product is less than the target.

Example 2:

Input: [8, 2, 6, 5], target=50                                              
Output: [8], [2], [8, 2], [6], [2, 6], [5], [6, 5]                         
Explanation: There are seven contiguous subarrays whose product is less than the target.

Constraints:

  • 1 <= arr.length <= 3 * 10<sup>4</sup>
  • 1 <= arr[i] <= 1000
  • 0 <= k <= 10<sup>6</sup>

Try it yourself

Try solving this question here:

Python3
Python3
. . . .
A

Anonymous

· 2 years ago

I have a slightly different approach which I believe is O(n^2) time complexity, I imagine the space complexity is the same O(n^3) but correct me if I'm wrong.

class Solution {
  findSubarrays(arr, target) {
    let result = [];
    let l = 0;
    let r = 0;
    let runningSum = 1;

    while (r <= arr.length) {
      runningSum *= arr[r];
      
      if (runningSum < target) {
        result.push(arr.slice(l, r + 1));
        r++
      } else {
        l += 1
        runningSum = 1;
        r = l
      }
    }

    return result;
  }
}
A

Anonymous

· 2 years ago

As others have said, this is a sliding window problem rather than two pointers. Using the sliding window pattern, we get O(N^2) instead of O(N^3).

  def findSubarrays(self, arr, target):
    result = []

    # Use a sliding window
    for start in range(0, len(arr)):
      product = 1.0   # reset for every iteration of start pointer
      subArray = []   # reset new subarray

      # Iterate the end pointer from the start pointer until product exceeds target
      for end in range(start, len(arr)):
        product *= arr[end]
        if product >= target:
          break
         
        subArray.append(arr[end])
        result.append(list(subArray))
    
    return result
A

Anonymous

· 2 years ago

class Solution:
  def findSubarrays(self, arr, target):
    result = []
    
    for i in range(len(arr)):
      left = i
      right = i
      product = 1

      while product < target:
        print(left, right, result)
        if left == right and arr[left] < target:
          result.append([arr[left]])
          right += 1
        elif left < right and right < len(arr):
          start = left
          end = right+1
          
          product = 1
          for i in range(start, end):
            product *= arr[i]
          
          if product < target:
            result.append(arr[start:end])
            right += 1
          else:
            break
        else:
          break
          
    return result
A

Anonymous

· 2 years ago

According to other "two pointers" and "sliding window" medium exercises this one is a little bit harder. Like Medium++ :D

Maybe it is just personal experience, because I see new pattern to memorize ...

A

Anonymous

· 2 years ago

The pattern of this problem is sliding window rather than two pointers

A

Anonymous

· 2 years ago

This is a better O(N)^2 solution . the official solution is not ideal and confusing .

Simply do a double loop as below

 def findSubarrays(self, arr, target):
    result = []
    for i in range(len(arr)):
      if arr[i] < target:
        result.append([arr[i]])

      mpy = arr[i]
      path = [arr[i]]

      for j in range(i + 1, len(arr)):
        mpy *= arr[j]
        path.append(arr[j])
        if mpy < target:
          result.append(path[:])
A

Anonymous

· 2 years ago

I have my own solution that I think is way less complex and similar efficiency.

We have outer loop which is O(N) and then we do an inner loop to get subarrays and we unpack arrays as we add them making the overall time complexity O(N^3)

Space O(N^3)

class Solution:
  def findSubarrays(self, arr, target):
    result = []
    end = len(arr)
    # TODO: Write your code here
    # Go through the entire array
    for i, num in enumerate(arr):
      # Pointer starts after current index (for continuous array)
      pointer = i+1
      product = num
      product_arr = [num]
      # Technically it is possible to have a current number that is more than target
      # But 0 as the next number - this would mean individual target is not but joined it is
      if product < target:
A

Anonymous

· 3 years ago

I think we shouldn't have to create all the subarrays because that makes the solution O(n^2) instead of O(n) thus kind of defeating the purpose of learning sliding window pattern

A

Anonymous

· 3 years ago

I has a different solution and yield the same result just in different order and the grading system mark me as wrong.

A

Anonymous

· 3 years ago

In the solution, each element is inserted into the temp_list array with temp_list.insert(0, arr[i]). According to this Python wiki, List insert has O(n) time complexity, so I used a deque, for which appendleft has O(1) time complexity, instead. Should the solution be changed to use a deque as well? The empty solution imports deque, so it seems to me that it might have been the intention to use it.

Show 2 replies

Reading Progress

0%

Vote for new content

On This Page

Problem Statement

Try it yourself