BackmediumTwo Pointers Salesforce

Subarray Product Validator Solution

Problem Statement

Given an array of integers nums and an integer K, return the number of subarrays where the product of all elements in the subarray is less than K.

Example 1
Input
[10, 5, 3, 7, 9]
Output
4

Explanation: Step-by-step: Given the array [10, 5, 3, 7, 9] and K=10, we iterate through the array using two pointers. We start with the first pointer at index 0 and the second pointer at index 1. The product of the subarray [10] is 10, which is not less than K. We move the second pointer to index 2. The product of the subarray [10, 5] is 50, which is not less than K. We move the second pointer to index 3. The product of the subarray [10, 5, 3] is 150, which is not less than K. We move the second pointer to index 4. The product of the subarray [10, 5, 3, 7] is 210, which is not less than K. We move the second pointer to index 5. The product of the subarray [10, 5, 3, 7, 9] is 1890, which is not less than K. We reset the second pointer to index 1 and move it to index 2. The product of the subarray [5] is 5, which is less than K. We reset the second pointer to index 1 and move it to index 3. The product of the subarray [5, 3] is 15, which is less than K. We reset the second pointer to index 1 and move it to index 4. The product of the subarray [5, 3, 7] is 105, which is less than K. We reset the second pointer to index 1 and move it to index 5. The product of the subarray [5, 3, 7, 9] is 945, which is not less than K. We reset the second pointer to index 1 and move it to index 2. The product of the subarray [3] is 3, which is less than K. We reset the second pointer to index 1 and move it to index 3. The product of the subarray [3, 7] is 21, which is less than K. We reset the second pointer to index 1 and move it to index 4. The product of the subarray [3, 7, 9] is 189, which is not less than K. We reset the second pointer to index 1 and move it to index 2. The product of the subarray [7] is 7, which is less than K. We reset the second pointer to index 1 and move it to index 3. The product of the subarray [7, 9] is 63, which is not less than K. We reset the second pointer to index 1 and move it to index 2. The product of the subarray [9] is 9, which is less than K. We count the subarrays [5], [3], [7], and [9] and return 4.

Example 2
Input
[1, 2, 3, 4, 5, 6, 7, 8, 9]
Output
9

Explanation: Step-by-step: Given the array [1, 2, 3, 4, 5, 6, 7, 8, 9] and K=10, we iterate through the array using two pointers. We start with the first pointer at index 0 and the second pointer at index 1. The product of the subarray [1] is 1, which is less than K. We move the second pointer to index 2. The product of the subarray [1, 2] is 2, which is less than K. We move the second pointer to index 3. The product of the subarray [1, 2, 3] is 6, which is less than K. We move the second pointer to index 4. The product of the subarray [1, 2, 3, 4] is 24, which is not less than K. We reset the second pointer to index 1 and move it to index 2. The product of the subarray [2] is 2, which is less than K. We reset the second pointer to index 1 and move it to index 3. The product of the subarray [2, 3] is 6, which is less than K. We reset the second pointer to index 1 and move it to index 4. The product of the subarray [2, 3, 4] is 24, which is not less than K. We reset the second pointer to index 1 and move it to index 2. The product of the subarray [3] is 3, which is less than K. We reset the second pointer to index 1 and move it to index 3. The product of the subarray [3, 4] is 12, which is not less than K. We reset the second pointer to index 1 and move it to index 2. The product of the subarray [4] is 4, which is less than K. We reset the second pointer to index 1 and move it to index 3. The product of the subarray [4, 5] is 20, which is not less than K. We reset the second pointer to index 1 and move it to index 2. The product of the subarray [5] is 5, which is less than K. We reset the second pointer to index 1 and move it to index 3. The product of the subarray [5, 6] is 30, which is not less than K. We reset the second pointer to index 1 and move it to index 2. The product of the subarray [6] is 6, which is less than K. We reset the second pointer to index 1 and move it to index 3. The product of the subarray [6, 7] is 42, which is not less than K. We reset the second pointer to index 1 and move it to index 2. The product of the subarray [7] is 7, which is less than K. We reset the second pointer to index 1 and move it to index 3. The product of the subarray [7, 8] is 56, which is not less than K. We reset the second pointer to index 1 and move it to index 2. The product of the subarray [8] is 8, which is less than K. We reset the second pointer to index 1 and move it to index 3. The product of the subarray [8, 9] is 72, which is not less than K. We reset the second pointer to index 1 and move it to index 2. The product of the subarray [9] is 9, which is less than K. We count the subarrays [1], [2], [3], [4], [5], [6], [7], [8], and [9] and return 9.

Constraints

  • 1 <= n <= 3 * 10^4
  • 1 <= arr[i] <= 1000
  • 0 <= k <= 10^6
Live Compiler
Loading...
Test Cases & Output
🔒 Sign up to run your code

🚀 Practice this problem

Run code, get AI hints & track streak

Sign Up Free