Optimal Harvest Index — Problem Statement & Solution Guide
Problem Description
Given an integer array nums, an index i (0‑based) is called an optimal harvest position if it satisfies one of the following: (1) nums[i] is strictly greater than both its immediate neighbours nums[i‑1] and nums[i+1]; or (2) nums[i] is equal to at least one neighbour and its value equals the maximum value among all indices that share the same value as nums[i]. Only indices with both neighbours (i.e., 1 ≤ i < n‑1) are considered for condition 1; condition 2 applies to any index that has at least one neighbour with the same value. Return the smallest index i that is optimal. If no such index exists, return -1.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Optimal Harvest Index"
WHY DOES IT MATTER?
This pattern combines local neighborhood analysis with global state tracking. It is essential for problems involving signal processing, anomaly detection, and time-series analysis where 'peaks' are significant events. Understanding how to efficiently combine local and global constraints is a key skill for senior engineers.
OPTIMIZATION CHALLENGE
The key insight is that condition (2) depends on the global maximum of the array. By pre-computing the global maximum in O(N), we can reduce the check for condition (2) to a simple comparison in O(1) per element, rather than scanning the array for each element.
REAL-WORLD CONNECTION
In distributed systems, this is analogous to identifying 'hot spots' in a data center. A hot spot is either a node with significantly higher load than its immediate neighbors (local peak) or a node that is part of the cluster's maximum load tier (global max plateau). Efficiently identifying these allows for dynamic load balancing.
Always clarify the definition of 'maximum value among all indices that share the same value.' In most interview contexts, this simplifies to checking if the current value is the global maximum of the entire array. If it means 'maximum among the contiguous block of same values,' the logic changes slightly to require tracking block boundaries. Clarify this early.
COMPLEXITY AT A GLANCE
O(N)O(1)Core Theory — Why This Approach?
The 'Optimal Harvest Index' problem is a variant of local extremum detection combined with global frequency analysis. A naive approach might iterate through the array and for each index, check its neighbors for condition (1) or scan the entire array to verify condition (2). This results in O(N^2) time complexity, which is infeasible for large datasets (N > 10^5). The core theoretical challenge lies in efficiently determining if a value is the 'maximum among all indices sharing the same value.' Since the condition implies that if nums[i] equals a neighbor, it must be the global maximum of that specific value's occurrences, we can pre-process the array to identify the global maximum value and the count of that maximum. However, a more nuanced interpretation of 'maximum value among all indices that share the same value' in the context of local peaks usually simplifies to checking if the current value is a local peak or if it is part of a plateau that is the global maximum of the array. If the problem implies that for any value V, we only care if V is the global max of the array, the logic simplifies significantly. Assuming the standard interpretation where we look for local peaks (strict) or global maximum plateaus, we can solve this in a single pass after identifying the global maximum.
Interview Questions on This Problem
Q1At a fintech platform like Stripe, how would you adapt this algorithm to identify 'peak transaction volumes' in a time-series array where a peak is defined as a local maximum or a global maximum plateau?
I would first compute the global maximum of the array in O(N). Then, I would iterate through the array once. For each index i (excluding boundaries), I check if nums[i] > nums[i-1] and nums[i] > nums[i+1] (strict local peak). If not, I check if nums[i] equals the global maximum. If it does, I need to ensure it's part of a contiguous block of global maximums. I can track the start and end of the global max block in a single pass. Any index within that block is an 'optimal harvest position' under condition (2). This maintains O(N) time and O(1) space.
Q2In a high-growth startup context, if the array represents user engagement scores, how would you handle the edge case where the entire array consists of the same value?
If the entire array consists of the same value, then every index is part of a global maximum plateau. According to condition (2), since nums[i] equals its neighbors and its value is the maximum (trivially), all indices would be optimal harvest positions. My algorithm must correctly identify that the global maximum equals the minimum and that the entire array is a single contiguous block of that maximum. I would return all indices from 0 to N-1. This requires careful boundary checking to avoid out-of-bounds errors when checking neighbors for the first and last elements, although the problem statement restricts valid indices to those with both neighbors (1 to N-2).
Q3At a product company like Amazon, how would you optimize memory usage if the array is streamed in chunks rather than available in full memory?
If the array is streamed, I cannot store the entire array to check neighbors later. I would use a sliding window of size 3. I keep track of the previous two values. However, condition (2) requires knowing if the current value is the global maximum. This is a two-pass problem if I don't know the global max in advance. If the stream is finite and I can store the global max, I can do a single pass: maintain a variable for the global max (updated as I go) and a buffer of the last two values. But wait, if I update the global max, I might have missed earlier indices that were local peaks but not global max. Actually, condition (1) is local, condition (2) is global. I can identify local peaks in one pass. For condition (2), I need to know the global max. If I can't store the array, I might need to store indices of potential global max candidates. A better approach for streaming is to assume the global max is known or perform two passes if the data is re-readable. If not, I would store the indices of all occurrences of the current global max and update this list as I find larger values. This is O(N) space in the worst case but O(1) if the global max is unique or rare.
Examples
Input
[1,3,2,4,4,4,2]
Output
1
Explanation: Index 1 holds value 3, which is greater than its neighbours 1 and 2, satisfying condition 1. It is the first optimal index.
Input
[5,5,5,5]
Output
0
Explanation: All elements are equal to 5. The maximum value among indices with value 5 is 5 itself, so every index meets condition 2. The smallest such index is 0.
Input
[2,2,3,3,2]
Output
2
Explanation: Indices 2 and 3 contain the maximum value 3. Neither is strictly greater than both neighbours, but both satisfy condition 2 because their value equals the maximum among all indices with value 3. The first occurrence is index 2.
Constraints
- 1 <= nums.length <= 200000
- -1000000000 <= nums[i] <= 1000000000
- All calculations must run in O(n) time and O(1) extra space
Optimal Approach & Strategy
First, find the global maximum of the array in O(N). Then, iterate through the array once, checking if each index is a strict local peak or if its value equals the global maximum. This reduces the time complexity to O(N).
Brute Force Approach
Iterate through each index and for condition (2), scan the entire array to verify if the current value is the maximum among all occurrences of that value. This results in O(N^2) time complexity.
Verified Code Solutions
const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let pos = 0;
const n = data[pos++]||0;
const nums = data.slice(pos, pos+n);
function optimalHarvestIndex(nums){
const len = nums.length;
if(len < 3) return -1;
const globalMax = Math.max(...nums);
// Condition 1: strict peak
for(let i=1;i<=len-2;i++){
if(nums[i] > nums[i-1] && nums[i] > nums[i+1]) return i;
}
// Condition 2: equal neighbour and value is global maximum
for(let i=1;i<=len-2;i++){
if((nums[i]===nums[i-1] || nums[i]===nums[i+1]) && nums[i]===globalMax) return i;
}
return -1;
}
console.log(optimalHarvestIndex(nums).toString());#include <bits/stdc++.h>
using namespace std;
int optimalHarvestIndex(const vector<int>& nums) {
int n = (int)nums.size();
if(n < 3) return -1; // need both neighbours
int globalMax = *max_element(nums.begin(), nums.end());
// Condition 1: strict peak
for(int i=1;i<=n-2;++i){
if(nums[i] > nums[i-1] && nums[i] > nums[i+1]) return i;
}
// Condition 2: equal neighbour and value is global maximum
for(int i=1;i<=n-2;++i){
if((nums[i]==nums[i-1] || nums[i]==nums[i+1]) && nums[i]==globalMax) return i;
}
return -1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin>>n)) return 0;
vector<int> nums(n);
for(int i=0;i<n;++i) cin>>nums[i];
cout<<optimalHarvestIndex(nums);
return 0;
}import java.io.*;
import java.util.*;
public class Main {
private static int optimalHarvestIndex(int[] nums) {
int n = nums.length;
if(n < 3) return -1;
int globalMax = nums[0];
for(int v: nums) if(v > globalMax) globalMax = v;
// Condition 1: strict peak
for(int i=1;i<=n-2;i++){
if(nums[i] > nums[i-1] && nums[i] > nums[i+1]) return i;
}
// Condition 2: equal neighbour and value is global maximum
for(int i=1;i<=n-2;i++){
if((nums[i]==nums[i-1] || nums[i]==nums[i+1]) && nums[i]==globalMax) return i;
}
return -1;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
if(line==null||line.isEmpty()) return;
int n = Integer.parseInt(line.trim());
int[] nums = new int[n];
if(n>0){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++) nums[i] = Integer.parseInt(st.nextToken());
}
System.out.print(optimalHarvestIndex(nums));
}
}import sys
def optimalHarvestIndex(nums):
n = len(nums)
if n < 3:
return -1
global_max = max(nums)
# Condition 1: strict peak
for i in range(1, n-1):
if nums[i] > nums[i-1] and nums[i] > nums[i+1]:
return i
# Condition 2: equal neighbour and value is global maximum
for i in range(1, n-1):
if (nums[i] == nums[i-1] or nums[i] == nums[i+1]) and nums[i] == global_max:
return i
return -1
if __name__ == "__main__":
data = sys.stdin.read().strip().split()
if not data:
sys.exit(0)
n = int(data[0])
nums = list(map(int, data[1:1+n]))
print(optimalHarvestIndex(nums))const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
let pos = 0;
const n = data[pos++]||0;
const nums = data.slice(pos, pos+n);
function optimalHarvestIndex(nums){
const len = nums.length;
if(len < 3) return -1;
const globalMax = Math.max(...nums);
// Condition 1: strict peak
for(let i=1;i<=len-2;i++){
if(nums[i] > nums[i-1] && nums[i] > nums[i+1]) return i;
}
// Condition 2: equal neighbour and value is global maximum
for(let i=1;i<=len-2;i++){
if((nums[i]===nums[i-1] || nums[i]===nums[i+1]) && nums[i]===globalMax) return i;
}
return -1;
}
console.log(optimalHarvestIndex(nums).toString());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.