Find Minimum Possible Variance

Problem Overview

• Given an array of building heights, this problem asks for the minimum possible variance over all valid groups.
• A valid group is a contiguous subarray of length ≥ 2 with equal first and last heights; variance = group size minus occurrences of the first height in the group.
• Input: n (2..2e5), heights (1..1e9); Output: minimal variance; at least one valid group exists.
• Real-world context: Amazon Real Estate Analytics Toolset for investor analysis.
• Asked in Amazon interviews; an array interview question for a coding interview.