LeetCode 2653: Sliding Subarray Beauty Solution

Master LeetCode problem 2653 (Sliding Subarray Beauty), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2653. Sliding Subarray Beauty

Medium

Array Hash Table Sliding Window

Problem Explanation

Explanation

To solve this problem, we can use a sliding window approach. We will maintain a sliding window of size k and keep track of the count of negative numbers in the window. At each step, we update the beauty value for the current subarray based on the xth smallest negative number in the window.

Initialize a hashmap to store the count of each number in the current window.
Initialize pointers left and right to define the window boundaries.
Iterate through the array:
- Update the count of the number at right in the hashmap.
- Increment right until the window size is k.
- While the window size is greater than k:
  - Decrement the count of the number at left in the hashmap.
  - Increment left.
- Update the beauty value for the current window based on the xth smallest negative number.
- Move to the next window by incrementing right.

Solution Code

import java.util.*;

class Solution {
    public int[] slidingSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        Map<Integer, Integer> countMap = new HashMap<>();
        int left = 0, right = 0;
        
        while (right < n) {
            countMap.put(nums[right], countMap.getOrDefault(nums[right], 0) + 1);
            
            if (right - left + 1 == k) {
                int negatives = 0;
                PriorityQueue<Integer> pq = new PriorityQueue<>();
                for (int i = left; i <= right; i++) {
                    if (nums[i] < 0) {
                        pq.offer(nums[i]);
                        negatives++;
                    }
                }
                
                if (negatives < x) {
                    result[left] = 0;
                } else {
                    int count = 0;
                    int beauty = 0;
                    while (!pq.isEmpty() && count < x) {
                        beauty = pq.poll();
                        count++;
                    }
                    result[left] = beauty;
                }
                
                countMap.put(nums[left], countMap.get(nums[left]) - 1);
                if (countMap.get(nums[left]) == 0) {
                    countMap.remove(nums[left]);
                }
                
                left++;
            }
            
            right++;
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2653 (Sliding Subarray Beauty)?

This page provides optimized solutions for LeetCode problem 2653 (Sliding Subarray Beauty) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2653 (Sliding Subarray Beauty)?

The time complexity for LeetCode 2653 (Sliding Subarray Beauty) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2653 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2653 in Java, C++, or Python.

Back to LeetCode Solutions