Minimum Variance Sum Split
Updated
Problem statement
You are given an integer array nums and an integer k. Split nums into exactly k groups. Each group is a non-empty run of neighboring elements, and every element belongs to exactly one group.
The variance of a group is the average of the squared differences between its numbers and the group's mean. For a group of m numbers with mean avg, it is the sum of (x - avg) * (x - avg) over the group's numbers x, divided by m. A group with one number has variance 0.
Return the smallest possible sum of the variances of the k groups.
An answer is accepted if it differs from the correct answer by at most 10-9, or by a relative error of at most 10-9 when the correct answer is larger than 1.
Function
minVarianceSum(nums: int[], k: int) → doubleExamples
Example 1
nums = [1,2,10,11]k = 2return = 0.5The best split is [1,2] and [10,11]. The first group has mean 1.5, and both numbers are 0.5 away from it, so its variance is (0.25 + 0.25) / 2 = 0.25. The second group also has variance 0.25. The total is 0.5.
Any other split puts a small and a large number together, which gives a much bigger variance.
Example 2
nums = [0,10,0,10]k = 2return = 22.22222222222222There are three ways to make two groups:
[0]and[10,0,10]: the second group has mean20/3and variance200/9, so the total is200/9, about22.2222.[0,10]and[0,10]: each group has mean5and variance25, so the total is50.[0,10,0]and[10]: the same as the first way by symmetry,200/9.
The smallest total is 200/9 = 22.22222222222222. Splitting into the two halves [0,10] and [0,10] is the worst choice, because each half still holds both a 0 and a 10.
Example 3
nums = [3,1,4,1,5]k = 1return = 2.56With k = 1, the whole array is one group. Its mean is 14 / 5 = 2.8. The squared differences are 0.04, 3.24, 1.44, 3.24 and 4.84, which add up to 12.8. The variance is 12.8 / 5 = 2.56.
Constraints
1 <= k <= nums.length <= 200-104 <= nums[i] <= 104
More Airbnb Phone Screen questions
- Read Across Sound TracksPHONE SCREEN · Seen Nov 2026
- Text JustificationPHONE SCREEN · Seen Nov 2026
- Decode and Store StringsPHONE SCREEN · Seen Oct 2026
- Print Sentences as TablePHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Detonate Bombs with Chain ReactionsPHONE SCREEN · Seen Aug 2026
- Smallest Common RegionPHONE SCREEN · Seen Aug 2026
- Longest Chain BookingPHONE SCREEN · Seen Aug 2026
- Nested List Iterator with RemovePHONE SCREEN · Seen Jul 2026
- Parse Query StringPHONE SCREEN · Seen May 2026
- Pacific Atlantic Water FlowPHONE SCREEN · Seen May 2023
Similar questions at other companies
- Best Improvement Period of at Least K IntervalsAmazon · PHONE SCREEN
- Maximum Subarray SumCapital One · PHONE SCREEN · ONSITE INTERVIEWCapital One interview questions
- Largest All-One Square Area and CountNVIDIA · PHONE SCREENNVIDIA interview questions
- Minimum Cost to Merge StonesGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Maximum Game Score with Fixed Forward JumpsStripe · OAStripe interview questions
- Maximum Apples from Two Disjoint Fixed-Length SegmentsMarshall Wace · OAMarshall Wace interview questions
- Maximum Non-Decreasing Array LengthVisa · OAVisa interview questions
- Maximize CollaborationTikTok · OATikTok interview questions
- Maximum Sum RectangleDeloitte · OADeloitte interview questions
- Maximum Subarray Sum with One DeletionServiceNow · PHONE SCREENServiceNow interview questions
Interview reports that mention this question
Airbnb interview experiences
- Airbnb SWE OA: Four-Level Banking System: 1 Experience
- Airbnb Campus and Full-Time SWE OA / Interviews: 9 Experiences
- Airbnb Intern OA and Phone Screens: 17 Experiences (Part 6 of 7)
- Airbnb Intern OA and Onsite Rounds: 16 Experiences (Part 5 of 7)
- Airbnb Intern OA, Diplomacy Game: 19 Experiences (Part 4 of 7)