Subarray With Elements Greater Than Varying Threshold

Subarray With Elements Greater Than Varying Threshold - Problem

You are given an integer array nums and an integer threshold.

Find any subarray of nums of length k such that every element in the subarray is greater than threshold / k.

Return the size of any such subarray. If there is no such subarray, return -1.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,3,3,3], threshold = 6

› Output: 3

💡 Note: For k=3, threshold/k = 6/3 = 2. The subarray [3,3,3] has all elements > 2, so return 3.

Example 2 — Single Element

$ Input: nums = [6,5,6,5,8], threshold = 7

› Output: 1

💡 Note: For k=1, threshold/k = 7/1 = 7. Element 8 > 7, so return 1.

Example 3 — No Valid Subarray

$ Input: nums = [1,1,1,1], threshold = 8

› Output: -1

💡 Note: No subarray satisfies the condition since all elements are 1 and 1 ≤ 8/k for any k ≥ 1.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹
1 ≤ threshold ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,3,3,3] with threshold = 6

Process

Find subarray where all elements > threshold/k

Output

Return size of valid subarray: 3

Key Takeaway

🎯 Key Insight: Use monotonic stack to find maximum valid ranges efficiently, then check threshold conditions

Asked in

G Google 12 f Facebook 8 a Amazon 6

The key insight is to use a monotonic stack to efficiently find the maximum range where each element can serve as the minimum value. For each element, we determine the longest subarray where all elements are ≥ current element, then check which lengths k satisfy the condition element > threshold/k. Best approach is monotonic stack. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Check all possible subarrays of all lengths
Monotonic Stack	O(n)	O(n)	Use monotonic stack to find maximum valid subarray efficiently

Brute Force — Algorithm Steps

Try each possible subarray length k
For each k, check all subarrays of length k
Verify all elements > threshold/k
Return the largest valid k found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Length k=1

Check each single element

Try Length k=2

Check each pair of consecutive elements

Continue

Keep trying larger lengths until valid subarray found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int threshold) {
    int maxSize = -1;
    
    // Try all possible lengths k
    for (int k = 1; k <= numsSize; k++) {
        double required = (double) threshold / k;
        
        // Check all subarrays of length k
        for (int i = 0; i <= numsSize - k; i++) {
            int valid = 1;
            for (int j = i; j < i + k; j++) {
                if (nums[j] <= required) {
                    valid = 0;
                    break;
                }
            }
            
            if (valid) {
                maxSize = k;
                break;
            }
        }
    }
    
    return maxSize;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '[' && token[0] != ']') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int threshold;
    scanf("%d", &threshold);
    
    int result = solution(nums, numsSize, threshold);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: length k, starting position, and element verification

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

18.5K Views

Medium Frequency

~35 min Avg. Time

412 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler