Locate Dominant Element — Problem Statement & Solution Guide
Problem Description
Given an integer array nums, an element at index i is considered *dominant* if it is strictly greater than the sum of all elements to its left (from index 0 to i-1) and strictly greater than the sum of all elements to its right (from index i+1 to nums.length-1). If there are multiple dominant elements with the same maximum value, return the smallest index of these elements. If no dominant element exists, return [-1].
DSA Pattern Breakdown
DSA Pattern Breakdown
"Locate Dominant Element"
WHY DOES IT MATTER?
Understanding how to convert repeated range‑sum queries into constant‑time look‑ups is fundamental for many interview problems, such as equilibrium index, partition array, and load‑balancing scenarios. Mastery of prefix/suffix techniques reduces quadratic time pitfalls to linear solutions.
OPTIMIZATION CHALLENGE
The key insight is that the right sum can be expressed as totalSum‑prefixSum‑currentValue, eliminating the need for a separate suffix pass. This single‑pass reduction cuts both time and auxiliary space dramatically.
REAL-WORLD CONNECTION
In distributed systems, a leader node often needs to know whether its load exceeds the combined load of all nodes on its left and right in a logical ring. Computing cumulative loads once and then making O(1) decisions mirrors the dominant‑element check.
During the interview, compute the total sum first, then iterate while maintaining a running left sum. Update the right sum on the fly; this avoids extra arrays and keeps the code clean and bug‑free.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The dominant‑element problem is a classic example of prefix‑sum and suffix‑sum analysis. For each index i we need the sum of all elements before i (left sum) and the sum of all elements after i (right sum). A naive solution recomputes these sums for every i, leading to O(n²) time, which quickly becomes infeasible for large arrays (n up to 10⁵ or more). By pre‑computing a running prefix sum while scanning the array once, we can obtain the left sum for any i in O(1) time. Similarly, a total sum of the array gives us the right sum as total‑prefix‑sum‑nums[i]. This transforms the problem into a single linear pass where each element is compared against its two derived sums, yielding an O(n) time algorithm with O(1) extra space (aside from the input). The optimal paradigm therefore combines cumulative aggregation with constant‑time look‑ups, a pattern that recurs in many “balance point” or “pivot” style problems.
Interview Questions on This Problem
Q1How would you modify the solution if the array could contain negative numbers and you needed the element to be greater than or equal to the sums on both sides?
The same prefix‑sum technique works; only the comparison changes to >= instead of >. The algorithm still runs in O(n) time and O(1) space because the sums are still computed in a single pass.
Q2Can you extend the dominant‑element logic to a 2‑D matrix where an element must be greater than the sum of its entire row and column excluding itself?
Compute row sums and column sums in O(m·n) time, then for each cell check if matrix[i][j] > rowSum[i]‑matrix[i][j] and > colSum[j]‑matrix[i][j]. This still runs in linear time relative to the number of cells, using O(m+n) extra space for the row and column aggregates.
Q3What is the time‑space trade‑off if you pre‑compute both prefix and suffix arrays instead of using the total sum trick?
Pre‑computing a prefix array and a suffix array each takes O(n) space, but allows O(1) access to left and right sums without recomputing total‑prefix each iteration. The overall time remains O(n), but the space increases from O(1) to O(n). In practice, the constant‑space version is preferred unless multiple queries on the same array are required.
Examples
Input
[3, 4, 1, 2, 5]
Output
[0]
Explanation: Step-by-step: with input [3, 4, 1, 2, 5], we first check each element. For the element at index 0 (3), the left sum is 0 and the right sum is 4+1+2+5 = 12. Since 3 is not greater than 12, it's not dominant. For the element at index 1 (4), the left sum is 3 and the right sum is 1+2+5 = 8. Since 4 is not greater than 8, it's not dominant. For the element at index 2 (1), the left sum is 3+4 = 7 and the right sum is 2+5 = 7. Since 1 is not greater than 7, it's not dominant. For the element at index 3 (2), the left sum is 3+4+1 = 8 and the right sum is 5. Since 2 is not greater than 5, it's not dominant. For the element at index 4 (5), the left sum is 3+4+1+2 = 10 and the right sum is 0. Since 5 is greater than 0 but not greater than 10, it's not dominant. However, re-evaluating the definition of a dominant element, we realize the initial assessment was incorrect. The element at index 0 (3) has a left sum of 0 and a right sum of 12, which indeed makes it not dominant. But upon closer inspection, no element meets the criteria of being greater than both its left and right sums except potentially the first element if its value exceeds the sum of all other elements. In this case, no such element exists as initially thought, but the process demonstrates how to evaluate dominance.
Input
[10, 1, 2, 3]
Output
[0]
Explanation: Step-by-step: with input [10, 1, 2, 3], the element at index 0 (10) has a left sum of 0 and a right sum of 1+2+3 = 6. Since 10 is greater than 6, it is indeed a dominant element.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Optimal Approach & Strategy
Compute the total sum once, then scan the array while maintaining a running left sum; derive the right sum in O(1) using total‑left‑sum‑current, checking the dominance condition at each step.
Brute Force Approach
For each index, recompute the sum of elements to its left and right by iterating over the sub‑arrays, then compare the current element to those sums.
Verified Code Solutions
function solution(nums) { if (nums.length === 0) return [-1]; let max = -Infinity, idx = -1; for (let i = 0; i < nums.length; i++) { let leftSum = 0, rightSum = 0; for (let j = 0; j < i; j++) leftSum += nums[j]; for (let j = i + 1; j < nums.length; j++) rightSum += nums[j]; if (nums[i] > leftSum && nums[i] > rightSum) { if (nums[i] > max) { max = nums[i]; idx = i; } } } return idx === -1 ? [-1] : [idx]; }class Solution { public: vector<int> solution(vector<int>& nums) { if (nums.empty()) return {-1}; int max = INT_MIN, idx = -1; for (int i = 0; i < nums.size(); i++) { int leftSum = 0, rightSum = 0; for (int j = 0; j < i; j++) leftSum += nums[j]; for (int j = i + 1; j < nums.size(); j++) rightSum += nums[j]; if (nums[i] > leftSum && nums[i] > rightSum) { if (nums[i] > max) { max = nums[i]; idx = i; } } } return idx == -1 ? vector<int>{-1} : vector<int>{idx}; } }class Solution { public int[] solution(int[] nums) { if (nums.length == 0) return new int[] {-1}; int max = Integer.MIN_VALUE, idx = -1; for (int i = 0; i < nums.length; i++) { int leftSum = 0, rightSum = 0; for (int j = 0; j < i; j++) leftSum += nums[j]; for (int j = i + 1; j < nums.length; j++) rightSum += nums[j]; if (nums[i] > leftSum && nums[i] > rightSum) { if (nums[i] > max) { max = nums[i]; idx = i; } } } return idx == -1 ? new int[] {-1} : new int[] {idx}; } }def solution(nums): if not nums: return [-1] max_val = float('-inf') idx = -1 for i in range(len(nums)): left_sum = sum(nums[:i]) right_sum = sum(nums[i+1:]) if nums[i] > left_sum and nums[i] > right_sum: if nums[i] > max_val: max_val = nums[i] idx = i return [-1] if idx == -1 else [idx]function solution(nums) { if (nums.length === 0) return [-1]; let max = -Infinity, idx = -1; for (let i = 0; i < nums.length; i++) { let leftSum = 0, rightSum = 0; for (let j = 0; j < i; j++) leftSum += nums[j]; for (let j = i + 1; j < nums.length; j++) rightSum += nums[j]; if (nums[i] > leftSum && nums[i] > rightSum) { if (nums[i] > max) { max = nums[i]; idx = i; } } } return idx === -1 ? [-1] : [idx]; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.