Number of Centered Subarrays - Solution & Explanation

Problem Overview: You are given an integer array and need to count how many subarrays are centered. A subarray is centered if there exists an index inside it that acts as the center and the elements around it balance in a way that keeps the center as the median of the subarray.

Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)

Enumerate every possible subarray using two nested loops. For each subarray, test every index as a potential center and verify whether it remains the median of the elements inside that subarray. This requires scanning the subarray and counting elements smaller and larger than the candidate center. The approach is straightforward but expensive: generating all subarrays costs O(n^2) and validating the center takes O(n). It works only for very small inputs and mainly helps you reason about the centered property before optimizing.

Approach 2: Hash Table + Enumeration (O(n^2) time, O(n) space)

Fix each index i as the center and expand outward. Track the balance between numbers greater than nums[i] and numbers smaller than it. Define a running balance such as +1 for greater elements and -1 for smaller ones. When the balance of the left and right sides cancel out, the center behaves like the median of that subarray.

A hash table stores frequencies of balance values observed on one side while expanding. As you enumerate elements on the other side, look up complementary balances that form a valid centered configuration. This converts repeated scans into constant‑time lookups. The outer loop enumerates every possible center (O(n)), while expansions and hash lookups take another O(n), giving O(n^2) time overall and O(n) extra space.

This strategy combines array traversal with hash table frequency counting to avoid recomputing comparisons for every candidate subarray. Instead of validating each subarray independently, you reuse balance information around the center.

Recommended for interviews: The hash table + enumeration method is the expected solution. Interviewers want to see that you first reason about the brute force definition of a centered subarray, then convert repeated checks into prefix balance counts with constant‑time hash lookups. That shift from repeated scanning to balance tracking demonstrates strong problem‑solving and familiarity with enumeration patterns.