educative.io

Educative

Shouldn't this be O(N^2) using sliding window?

using namespace std;

#include <iostream>
#include <vector>

class SubarrayProductLessThanK {
 public:
  static vector<vector<int>> findSubarrays(const vector<int>& arr, int target) {
    vector<vector<int>> result;
  
    for(int startWindow = 0; startWindow < arr.size(); startWindow++){
      int currProd = 1;
      vector<int> runningSubarr;
      for(int endWindow = startWindow; endWindow < arr.size(); endWindow++){
        int currVal = arr[endWindow];
        currProd *= currVal;

        if(currProd < target){
          runningSubarr.push_back(currVal);
          result.push_back(runningSubarr);
        }
        else{
          break;
        }
      }
    }

    return result;
  }
};

int main(int argc, char* argv[]) {
  auto result = SubarrayProductLessThanK::findSubarrays(vector<int>{2, 5, 3, 10}, 30);
  for (auto vec : result) {
    cout << "[";
    for (auto num : vec) {
      cout << num << " ";
    }
    cout << "]";
  }
  cout << endl;

  result = SubarrayProductLessThanK::findSubarrays(vector<int>{8, 2, 6, 5}, 50);
  for (auto vec : result) {
    cout << "[";
    for (auto num : vec) {
      cout << num << " ";
    }
    cout << "]";
  }
}