Sliding Subarray Beauty - Practice Coding Problems

Sliding Subarray Beauty - Problem

Given an integer array nums containing n integers, find the beauty of each subarray of size k.

The beauty of a subarray is the xth smallest integer in the subarray if it is negative, or 0 if there are fewer than x negative integers.

Return an integer array containing n - k + 1 integers, which denote the beauty of the subarrays in order from the first index in the array.

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

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,-1,-3,-2,3], k = 3, x = 2

› Output: [-1,-2,-2]

💡 Note: Window [1,-1,-3]: negatives [-3,-1], 2nd smallest is -1. Window [-1,-3,-2]: negatives [-3,-2,-1], 2nd smallest is -2. Window [-3,-2,3]: negatives [-3,-2], 2nd smallest is -2.

Example 2 — Insufficient Negatives

$ Input: nums = [-1,2,-3,4,-5], k = 2, x = 3

› Output: [0,0,0,0]

💡 Note: Each window of size 2 has at most 2 elements, so fewer than 3 negatives. Beauty is 0 for all windows.

Example 3 — All Positives

$ Input: nums = [1,2,3,4,5], k = 3, x = 1

› Output: [0,0,0]

💡 Note: No negative numbers in any window, so beauty is always 0.

Constraints

1 ≤ n == nums.length ≤ 10⁵
1 ≤ k ≤ n
1 ≤ x ≤ k
-50 ≤ nums[i] ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input

Array with mixed positive/negative values and parameters k, x

Sliding Windows

Process each subarray of size k, tracking only negatives

Beauty Calculation

Find x-th smallest negative or return 0

Key Takeaway

🎯 Key Insight: Only negative numbers matter for beauty calculation - use sliding window to efficiently track their frequencies

Asked in

a Amazon 35 M Microsoft 28 G Google 22 Apple 15

The key insight is that only negative numbers contribute to subarray beauty, and they're bounded (-50 to 50). The optimal approach uses a sliding window with fixed-size frequency array for O(1) updates and O(50) queries per window. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Fixed Array Frequency Counter	O(n × 50)	O(50)	Use fixed-size array for frequency counting since negatives are bounded
Brute Force	O(n × k × log k)	O(k)	For each subarray, collect negatives, sort them, and find x-th smallest
Sliding Window with Frequency Map	O(n × 50)	O(50)	Maintain a frequency map of negative numbers as window slides

Fixed Array Frequency Counter — Algorithm Steps

Use array of size 51 for values -50 to -1
Map negative value n to index (n + 50)
Update frequency array as window slides
Linear scan to find x-th smallest in O(50)

Visualization

Tap to expand

Step-by-Step Walkthrough

Map Values

Map -50 to -1 onto array indices 0-50

Update Array

O(1) increment/decrement at specific index

Linear Scan

O(50) scan to find x-th smallest

Code -

solution.c — C

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

int findXthSmallest(int freq[], int x) {
    int count = 0;
    for (int i = 0; i < 51; i++) { // -50 to 0
        count += freq[i];
        if (count >= x) {
            return i - 50; // Convert back to actual value
        }
    }
    return 0;
}

int* solution(int* nums, int numsSize, int k, int x, int* returnSize) {
    *returnSize = numsSize - k + 1;
    int* result = (int*)malloc(*returnSize * sizeof(int));
    int freq[51] = {0}; // -50 to -1 mapped to indices 0-50
    
    // Initialize first window
    for (int i = 0; i < k; i++) {
        if (nums[i] < 0 && nums[i] >= -50) {
            freq[nums[i] + 50]++;
        }
    }
    
    result[0] = findXthSmallest(freq, x);
    
    // Slide the window
    for (int i = k; i < numsSize; i++) {
        // Remove leftmost element
        int left = nums[i - k];
        if (left < 0 && left >= -50) {
            freq[left + 50]--;
        }
        
        // Add rightmost element
        if (nums[i] < 0 && nums[i] >= -50) {
            freq[nums[i] + 50]++;
        }
        
        result[i - k + 1] = findXthSmallest(freq, x);
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k, x;
    scanf("%d", &k);
    scanf("%d", &x);
    
    int returnSize;
    int* result = solution(nums, numsSize, k, x, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 50)

n windows, each scans up to 50 array positions to find x-th smallest

✓ Linear Growth

Space Complexity

O(50)

Fixed-size array for frequency counting of negative values

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

847 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

Fixed Array Frequency Counter — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler