Java O(N) with thinking process


  • 0
    S

    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
    0_1508698861677_33d05b72-7b4f-45f7-b2f0-c41a0bb80277-image.png

    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;
        }
    }
    

Log in to reply
 

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