# Java O(N) with thinking process

• For a given position `i`, we can find another position `endPositions[i]` as the rightmost position that satisfies the condition:
`nums[i] * nums[i + 1] * ... * nums[endPositions[i]] < k`

We can easily see `nums[i, ..., endPositions[i]]` and any of its subarray satisfy the above condition and shall be counted towards the result.

Here is the function to calculate `endPositions` (note if `nums[i] > k`, `endPositions[i]` does not exist, and we mark it as `i-1`)

``````private int[] getEndPositions(int[] nums, int k) {
int n = nums.length;
int[] endPositions = new int[n];

int product = 0;
for (int i = 0; i < n; i++) {
if (nums[i] >= k) {
endPositions[i] = i - 1;
product = 0;
continue;
}
if (product == 0) {
product = nums[i];
endPositions[i] = i;
} else {
product = product / nums[i - 1];
endPositions[i] = endPositions[i - 1];
}

while (endPositions[i] + 1 < n && product * nums[endPositions[i] + 1] < k) {
endPositions[i]++;
product *= nums[endPositions[i]];
}
}
return endPositions;
}
``````

If we consider `nums[i-1, ..., endPositions[i-1]]`, apparently some of the subarray of `nums[i, ..., endPositions[i]]` are also subarray of `nums[i-1, ..., endPositions[i-1]]`, we shall exclude them when counting towards the result, and only include the NEW subarrays only exist in `nums[i, ..., endPositions[i]]`. Apparently, subarrays ending in `endPositions[i-1]+1` to `endPositions[i]` are the NEW subarrays and we can count them towards the result as

``````    public int numSubarrayProductLessThanK(int[] nums, int k) {
long result = 0;
int n = nums.length;
int[] endPositions = getEndPositions(nums, k);

for (int i = 0; i < n; i++) {
for (int j = i; j <= endPositions[i]; j++) {
if (i == 0 || j > endPositions[i - 1]) {
result += j - i + 1;
}
}
}
return (int)result;
}
``````

However, the inner loop makes it worst case `O(N^2)`. Because the inner loop just add numbers of a geometric sequence to the result, we can actually calculate the sum of the geometric sequence in one step, see the graph below

Here is the solution with `O(N)` complexity

``````class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
long result = 0;
int n = nums.length;
int[] endPositions = getEndPositions(nums, k);

for (int i = 0; i < n; i++) {
int last = i > 0 ? endPositions[i - 1] : -1;
result += (long)(endPositions[i] + last - i * 2 + 3) * (endPositions[i] - last) / 2;
}
return (int)result;
}
private int[] getEndPositions(int[] nums, int k) {
//omit here, see above
}
}
``````

We can further optimize the algorithm to combine the step of calculate EndPosition and update the result:

``````class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int result = 0;
int n = nums.length;

int product = 0;
int lastEndPosition = -1;
int currentEndPosition = 0;
for (int i = 0; i < n; i++) {
if (nums[i] >= k) {
lastEndPosition = i - 1;
product = 0;
continue;
}

if (product == 0) {
product = nums[i];
currentEndPosition = i;
result++;
} else {
product = product / nums[i - 1];
currentEndPosition = lastEndPosition;
}

while (currentEndPosition + 1 < n && product * nums[currentEndPosition + 1] < k) {
currentEndPosition++;
product *= nums[currentEndPosition];
result += currentEndPosition - i + 1;
}

lastEndPosition = currentEndPosition;
}
return result;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.