Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 6: Subarrays with Product Less than a Target (hard)

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.

Note: This problem is very similar to the previous one. Here, we are trying to find all the subarrays, whereas in the previous problem, we focused on finding only the count of such subarrays.

Example 1:

Input: [2, 5, 3, 10], target=30                                              
Output: [2], [5], [2, 5], [3], [5, 3], [10]

.....

.....

.....

Like the course? Get enrolled and start learning!
S

stephen

· 4 years ago

Your solution explanation is pointless. What happened to pictures and a walk-through? You might as well just remove it and jump right into the code.

Stating we use two pointers to solve this is obvious since we are in the two pointer section. Furthermore pointing out the obvious 2 differences between problems doesn't add any value and doesn;t help anyone create a mental image of the logic of the solution. Piss poor content.

Abdullah AlKheshen

Abdullah AlKheshen

· 2 years ago

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

S

Shannon Wang

· 4 years ago

in the while loop while (product >= target && left < arr.length) why is left bound by arr.length? shouldn't it be left < right?

Show 1 reply
D

Dario Avetisov

· 3 years ago

Start at the declaration of tempList and the following for loop, that is some very poorly explained code. I'm sure you guys can put together a much better and more readable explanation.

Ashwin Ramesh

Ashwin Ramesh

· 3 years ago

My solution lists the sub arrays in a different order but it is not getting accepted. Also I don't understand how best case is of cubic complexity. Am I missing something in my solution? Feel like this is getting done in O(n*n) complexity?

  public static List<List<Integer>> findSubarrays(int[] arr, int target) {
    List<List<Integer>> result = new ArrayList<>();
    for(int i=0;i<arr.length;i++) {
      if(arr[i]<target) {
        result.add(Arrays.asList(arr[i]));
      } else {
        continue;
      }
      int product=arr[i];
      List<Integer> subArray = new ArrayList<>();
      subArray.add(arr[i]);
      for(int j=i+1;j<arr.length;j++) {
        product*=arr[j];
        if(product<target) {
          subArray.add(arr[j]);
          result.add(new ArrayList<>(subAr
Show 1 reply
Some Dude

Some Dude

· 3 years ago

Hi folks,

Am I missing something or is the below nested loop solution not a simpler alternative to this problem?

I understand the benefit of sliding window when you are trying to get the count, but when you have to return the sub-arrays this just seems more straight-forward?

import .*;

class Solution {

  public static List<List<Integer>> findSubarrays(int[] arr, int target) {
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < ; i++) {
      int product = 1;
      List<Integer> temp = new ArrayList<>();
      for (int j = i; j < ; j++) {
        temp.add(arr[j]);
        product = product * arr[j];
        if (product < target) {
          (new ArrayList<Integer>(temp));
        } else {
          break;
        }
      }
    }
    return result;
Show 2 replies
D

Daven L

· 3 years ago

In the solution snippet, the answer is:

        # Iterate from 'right' to 'left' and add all these subarrays to the result.
        for i in range(right, left - 1, -1):
            # Add the current element at the beginning of the list.
            temp_list.insert(0, arr[i])

            # Add the current subarray to the result.
            result.append(list(temp_list))

But what I don't understand is why we should do it this way.

What I had was:

    left, right = 0, 0
    product = 1
    ans = []
    while right < len(arr):
        product *= arr[right]
        # move left until product < target
        while product >= target and left < len(arr):
            product /= arr[left]
            left += 1
        # guaranteed to have product < target, get
J

John O'Neill

· 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
T

tahriris

· 2 years ago

Given that the optimal runtime is quadratic, why not just use nested for-loops?

def find_subarrays(arr, target):
    subarrays = []
    for i in range(len(arr)):
        product = 1
        for j in range(i, len(arr)):
            product *= arr[j]
            if product >= target:
                break
            subarrays.append(arr[i : j + 1])
    return subarrays
S

Smoke

· 4 years ago

"product" not square so must be two numbers at least.