Dominant Index with Strict Doubling Gaps
Updated
Problem statement
You are given a nonnegative integer array nums and a positive integer m. Take the m + 1 largest elements, counting equal values at different indices as separate elements. Sort those chosen values from smallest to largest as top.
Every adjacent pair must satisfy top[i] > 2 * top[i - 1]. If all pairs satisfy this strict inequality, return the original array index of the largest element. Otherwise, return -1.
When m == 1, this is the basic question: the largest value must be strictly greater than twice the second-largest value. Equality fails. Check the actual largest m + 1 elements; do not choose a different subset. Under these rules, a successful result has a unique largest element.
Function
dominantIndex(nums: int[], m: int) → intExamples
Example 1
nums = [1,7,2,3]m = 1return = 1The two largest values are [3,7]. Since 7 > 2 * 3, return the original index 1 of 7.
Example 2
nums = [1,2,4]m = 1return = -1The two largest values are [2,4]. The value 4 equals 2 * 2, so the strict condition fails and the result is -1.
Example 3
nums = [1,4,9,20,2]m = 2return = 3The three largest values sort to [4,9,20]. Both 9 > 2 * 4 and 20 > 2 * 9 hold. The largest value 20 was at index 3.
Constraints
2 <= nums.length <= 100000.0 <= nums[i] <= 1000000000.1 <= m < nums.length.
More Google Onsite Interview questions
- Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
- Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Filesystem Entity Total SizeONSITE INTERVIEW · Seen Nov 2026
- Longest Subarray Within an Absolute-Difference LimitONSITE INTERVIEW · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Tennis Court SchedulingAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Retrieve Vectors by Cosine SimilarityHarvey · ONSITE INTERVIEWHarvey interview questions
- Top K Largest Values from a StreamThe D.E. Shaw Group · ONSITE INTERVIEWThe D.E. Shaw Group interview questions
- Generate Complete Inputs for a Supplied ClassifierGeneral Motors · ONSITE INTERVIEW
- Minimum Meeting Rooms Without a Sweep LineGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Top K Largest Values with a HeapMeta · ONSITE INTERVIEWMeta interview questions
- Top K Frequent ElementsCapgemini · ONSITE INTERVIEWCapgemini interview questions
- Select K Paired Indices for Maximum ScoreAmazon · ONSITE INTERVIEW
- Kth Largest Element in an ArrayOneTrust · ONSITE INTERVIEW
- Kth Largest Element in an ArrayCognizant · ONSITE INTERVIEW