What is the time complexity of Count Subarrays With Median K?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Count Subarrays With Median K?

This problem uses Array, Hash Table, Prefix Sum. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Count Subarrays With Median K?

Insight 1: The core idea is to iterate through all possible subarrays and check their median, but this would lead to a higher time complexity. Instead, we look for subarrays containing `k`. Insight 2: We can optimize by focusing on the relationship between elements greater than and less than `k` within the subarray. If the number of elements greater than `k` equals the number of elements less than `k`, the subarray has an odd length and `k` is the median. If the number of elements greater than `k` is one more than the number of elements less than `k`, the subarray has an even length and `k` is the median.

Which companies ask LeetCode 2488. Count Subarrays With Median K in interviews?

This problem is frequently asked at Confluent, thoughtspot.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Count Subarrays With Median K - LeetCode 2488 Solution

Count Subarrays With Median K - Complete Solution Guide

Count Subarrays With Median K is LeetCode problem 2488, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given an array nums of size n consisting of distinct integers from 1 to n and a positive integer k . Return the number of non-empty subarrays in nums that have a median equal to k . Note : The median of an array is the middle element after sorting the array in ascending order. If the array is of even length, the median is the left middle element. For example, the median of [2,3,1,4] is 2 , and the median of [8,4,3,5,1] is 4 . A subarray is a contiguous part of an array. Example 1: Input:

Detailed Explanation

The problem asks us to count the number of non-empty subarrays within a given array `nums` whose median is equal to a specified value `k`. The `nums` array contains distinct integers from 1 to n. The median of a subarray is the middle element after sorting the subarray. If the subarray has an even length, the median is the left middle element. The core task is to efficiently identify and count all such subarrays.

Solution Approach

The solution efficiently counts subarrays with median `k` using a balance-based approach and a hash map (or array in C) to store the frequency of balances encountered to the left of `k`. First, it finds the index of `k` in the array. Then, it iterates from the element just to the left of `k` backwards to the beginning of the array, calculating the 'balance' (number of elements greater than `k` minus the number of elements less than `k`) for each subarray ending just before `k`. These balances and their frequencies are stored. Next, the solution iterates from `k` to the end of the array, calculating the balance for each subarray starting at `k`. For each of these subarrays, it checks what balance would be required on the left side of `k` to achieve a total balance of 0 (odd length subarray with `k` as the median) or 1 (even length subarray with `k` as the median). The count of such subarrays is incremented by the number of times those required balances appear in the precomputed frequencies from the left side.

Step-by-Step Algorithm

Step 1: Find the index `k_idx` of `k` in `nums`. Return 0 if `k` is not found.
Step 2: Create a hash map (or appropriately sized array in C) called `freq` to store the frequency of balances encountered to the left of `k`. Initialize `freq[0]` to 1, representing the empty subarray to the left of `k`.
Step 3: Iterate backwards from `k_idx - 1` to 0. For each element `nums[i]`, update the `balance`: increment if `nums[i] > k`, decrement if `nums[i] < k`. Update `freq[balance]` to reflect the count of subarrays ending at index `i` with the given balance.
Step 4: Initialize a counter `ans` to 0 and `balance` to 0.
Step 5: Iterate from `k_idx` to the end of the array `nums`. For each element `nums[j]`, update the `balance` as in step 3.
Step 6: Calculate the target balance values needed on the left to create a total balance of 0 and 1: `target_for_0 = -balance` and `target_for_1 = 1 - balance`.
Step 7: Increment `ans` by the frequency of `target_for_0` and `target_for_1` in `freq`. This is the number of subarrays ending at index `j` with median `k`.
Step 8: Return `ans`.

Key Insights

Insight 1: The core idea is to iterate through all possible subarrays and check their median, but this would lead to a higher time complexity. Instead, we look for subarrays containing `k`.
Insight 2: We can optimize by focusing on the relationship between elements greater than and less than `k` within the subarray. If the number of elements greater than `k` equals the number of elements less than `k`, the subarray has an odd length and `k` is the median. If the number of elements greater than `k` is one more than the number of elements less than `k`, the subarray has an even length and `k` is the median.
Insight 3: We use a balance (num_greater - num_less) concept to track whether k is the median. We can precompute and store frequencies of balances on the left side of k to speed up counting when processing elements to the right of k.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Prefix Sum.

Companies

Asked at: Confluent, thoughtspot.

Count Subarrays With Median K | LeetCode 2488

Hard

Array Hash Table Prefix Sum

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int countSubarrays(int[] nums, int k) {
        int n = nums.length;
        int k_idx = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] == k) {
                k_idx = i;
                break;
            }
        }

        if (k_idx == -1) {
            return 0;
        }

        // freq stores the frequency of balances for subarrays starting
        // to the left of k and ending just before k.
        // A balance is defined as (num_greater - num_less).
        Map<Integer, Integer> freq = new HashMap<>();
        freq.put(0, 1); // For the empty subarray to the left of k
        int balance = 0;
        for (int i = k_idx - 1; i >= 0; i--) {
            if (nums[i] > k) {
                balance += 1;
            } else {
                balance -= 1;
            }
            freq.put(balance, freq.getOrDefault(balance, 0) + 1);
        }

        int ans = 0;
        balance = 0;
        // Iterate through subarrays starting at k and expanding to the right.
        for (int j = k_idx; j < n; j++) {
            if (nums[j] > k) {
                balance += 1;
            } else if (nums[j] < k) {
                balance -= 1;
            }

            // For a subarray nums[i..j] containing k, its balance is the sum of
            // the balance of the left part (nums[i..k_idx-1]) and the balance
            // of the part from k to j (nums[k_idx..j]).
            // The current `balance` is for nums[k_idx..j].

            // We need the total balance to be 0 (for odd length subarrays)
            // or 1 (for even length subarrays).

            // Case 1: Total balance = 0
            // left_balance + current_balance = 0  => left_balance = -current_balance
            int target_for_0 = -balance;
            ans += freq.getOrDefault(target_for_0, 0);

            // Case 2: Total balance = 1
            // left_balance + current_balance = 1  => left_balance = 1 - current_balance
            int target_for_1 = 1 - balance;
            ans += freq.getOrDefault(target_for_1, 0);
        }

        return ans;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2488: Count Subarrays With Median K - Detailed explanation and solution approaches.

Topics

Array Hash Table Prefix Sum

Companies

Confluentthoughtspot

Stats

Difficulty:Hard

Languages:4

Companies:2

Problem #:2488

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Find the index `k_idx` of `k` in `nums`. Return 0 if `k` is not found.
2
Step 2: Create a hash map (or appropriately sized array in C) called `freq` to store the frequency of balances encountered to the left of `k`. Initialize `freq[0]` to 1, representing the empty subarray to the left of `k`.
3
Step 3: Iterate backwards from `k_idx - 1` to 0. For each element `nums[i]`, update the `balance`: increment if `nums[i] > k`, decrement if `nums[i] < k`. Update `freq[balance]` to reflect the count of subarrays ending at index `i` with the given balance.
4
Step 4: Initialize a counter `ans` to 0 and `balance` to 0.
5
Step 5: Iterate from `k_idx` to the end of the array `nums`. For each element `nums[j]`, update the `balance` as in step 3.
6
Step 6: Calculate the target balance values needed on the left to create a total balance of 0 and 1: `target_for_0 = -balance` and `target_for_1 = 1 - balance`.
7
Step 7: Increment `ans` by the frequency of `target_for_0` and `target_for_1` in `freq`. This is the number of subarrays ending at index `j` with median `k`.
8
Step 8: Return `ans`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is determined by the two linear scans of the array. The space complexity is determined by the size of the hash map used to store the frequencies of the balances to the left of `k`. In the worst case, all possible balance values could be unique, resulting in a space complexity proportional to the size of the array.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute-Force Approach

Iterate through all possible subarrays and check if each subarray's median is equal to `k`. This involves sorting each subarray, which is inefficient.

Time: O(n^2 * n log n) in the worst case, where n is the length of `nums`. n^2 subarrays, and each sort takes n log n.Space: O(n) in the worst case, for storing the sorted subarray.

Trade-offs: This approach is very simple to understand but is extremely inefficient for larger input sizes. It should only be considered for small arrays.

✨

Key Insights

1Insight 1: The core idea is to iterate through all possible subarrays and check their median, but this would lead to a higher time complexity. Instead, we look for subarrays containing `k`.
2Insight 2: We can optimize by focusing on the relationship between elements greater than and less than `k` within the subarray. If the number of elements greater than `k` equals the number of elements less than `k`, the subarray has an odd length and `k` is the median. If the number of elements greater than `k` is one more than the number of elements less than `k`, the subarray has an even length and `k` is the median.
3Insight 3: We use a balance (num_greater - num_less) concept to track whether k is the median. We can precompute and store frequencies of balances on the left side of k to speed up counting when processing elements to the right of k.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Edge Cases

Edge case 1: `k` is not present in `nums`. The solution returns 0 correctly after searching the array.
Edge case 2: The array contains only `k`. The algorithm will find k_idx, the first balance will be 0, ans will increment with freq[0] = 1, and the algorithm will correctly return 1.
Edge case 3: Empty array or an array with only one element. While not explicitly covered in the constraints, handling an empty array gracefully would add to the robustness of the code. This is implicitly handled since the loop won't execute. A single element array needs to contain `k` to return 1.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the even/odd length subarray conditions correctly. Remembering that the balance needs to be 0 or 1 is crucial.

✗Common mistake 2: Forgetting to initialize the frequency of balance 0 to 1. This accounts for the case where the subarray containing `k` is itself a valid subarray.

✗Common mistake 3: Not handling negative balances correctly. Especially relevant in C where you must use an offset for array indices.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: In data analysis, this approach can be used to identify specific ranges of data where a particular value is the median, which can be used for analyzing trends or identifying important segments.

🏦Real-world scenario 2: In signal processing, this could be used to find time windows where a specific signal strength (represented by `k`) is the median. This is useful for filtering noise or extracting important signal characteristics.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

It's okay to not finish hard problems in interviews. Show your problem-solving process.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 27, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 13

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

How do I approach hard algorithm problems?

Hard problems often require: 1) Breaking down into subproblems, 2) Combining multiple advanced techniques, 3) Careful optimization of brute force. Start with a working solution (even O(n²) or worse), then optimize. Draw examples, identify patterns, and think about what makes this problem unique.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Count Subarrays With Median K"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?