Eco-Grid Effective Energy — Problem Statement & Solution Guide

ArraysMediumRange Sum Query using Prefix Sum

TimeO(n + q)

SpaceO(n)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Eco-Grid Effective Energy problem optimally.

TopicArrays

PatternRange Sum Query using Prefix Sum

TimeO(n + q)

SpaceO(n)

Problem Description

You are managing an energy grid represented by an integer array energy of size n, where energy[i] denotes the power output of the i-th generator (0-indexed). The grid operators want to analyze the performance of various sectors. A sector is defined by a range [L, R]. Due to eco-incentives, generators at even indices (i.e., i is even) produce double their standard energy output, while generators at odd indices produce their standard energy output. Given q queries where each query is represented by an array of two integers [L, R], return an array of integers representing the total effective energy output for each query sector.

DSA Pattern Breakdown

"Eco-Grid Effective Energy"

medium

WHY DOES IT MATTER?

Prefix‑sum range queries are a cornerstone technique for transforming linear‑time scans into constant‑time lookups.

OPTIMIZATION CHALLENGE

The key is reducing per‑query work from O(length) to O(1) by leveraging pre‑computed aggregates.

REAL-WORLD CONNECTION

Think of a power‑grid dashboard that needs instant totals for any sector without re‑summing every meter each time.

Always build the prefix arrays once, validate them with a few manual checks, then trust the O(1) formula for every query.

COMPLEXITY AT A GLANCE

⏱ Time:O(n + q)

💾 Space:O(n)

Core Theory — Why This Approach?

The problem reduces to answering many range queries that depend on the parity of the original indices. A naïve scan of each sub‑array costs O(R‑L+1) per query, which explodes to O(n·q) for large inputs and exceeds time limits. The optimal paradigm is to pre‑compute two prefix‑sum arrays—one accumulating values at even positions and the other at odd positions—so that any query can be answered by a constant‑time subtraction of the appropriate prefix values, yielding overall O(n+q) time.

Interview Questions on This Problem

Q1How does a prefix‑sum array enable O(1) range‑sum queries?

Each prefix entry stores the cumulative sum up to that index; the sum of a range is the difference of two prefix values. This eliminates the need to iterate over the range.

Q2Why must we maintain separate prefix sums for even and odd indices?

The query’s result depends on the parity of the original indices, not the relative position inside the sub‑array. Separate arrays let us isolate contributions from each parity.

Q3What edge cases should be considered when handling 0‑based indexing in this problem?

Queries that start at index 0 or end at the last element require careful handling of prefix‑sum boundaries. Also, an empty range (L>R) should be guarded against.

Examples

Example 1

Input

[2, 4, 6, 8, 10]

Output

[2, 6, 14, 26, 46]

Explanation: Step-by-step: For the input [2, 4, 6, 8, 10], we first calculate the prefix sum by doubling the energy values at even indices (0, 2, 4) and summing the normal energy values at odd indices (1, 3). This gives us 2 + 4 + 6 + 8 + 10 = 30. Then, we add the doubled energy values at even indices (2, 6, 14) to get the final prefix sum of 2 + 6 + 14 + 26 + 46.

Example 2

Input

[10, 20, 30, 40, 50]

Output

[20, 60, 160, 320, 570]

Explanation: Step-by-step: For the input [10, 20, 30, 40, 50], we first calculate the prefix sum by doubling the energy values at even indices (0, 2, 4) and summing the normal energy values at odd indices (1, 3). This gives us 10 + 20 + 30 + 40 + 50 = 150. Then, we add the doubled energy values at even indices (20, 60, 160) to get the final prefix sum of 20 + 60 + 160 + 320 + 570.

Constraints

1 <= energy.length <= 10^5
1 <= energy[i] <= 10^4
1 <= queries.length <= 10^5
queries[i].length == 2
0 <= L <= R < energy.length

Optimal Approach & Strategy

Build two prefix‑sum arrays (even, odd) in O(n) then answer each query with two subtractions; O(1) per query.

Brute Force Approach

Iterate from L to R for each query, adding values at even original indices; O(R‑L+1) per query.

Code Solutions

Language:

JavaScript Solution

Time: O(n + q)

function solution(energy) {
   let prefixSum = 0;
   for (let i = 0; i < energy.length; i++) {
       if (i % 2 === 0) {
           prefixSum += energy[i] * 2;
       } else {
           prefixSum += energy[i];
       }
   }
   return prefixSum;
}

class Solution {
   public:
       int solution(vector<int>& energy) {
           int prefixSum = 0;
           for (int i = 0; i < energy.size(); i++) {
               if (i % 2 == 0) {
                   prefixSum += energy[i] * 2;
               } else {
                   prefixSum += energy[i];
               }
           }
           return prefixSum;
       }
   };

class Solution {
   public int solution(int[] energy) {
       int prefixSum = 0;
       for (int i = 0; i < energy.length; i++) {
           if (i % 2 == 0) {
               prefixSum += energy[i] * 2;
           } else {
               prefixSum += energy[i];
           }
       }
       return prefixSum;
   }
}

def solution(energy):
   prefix_sum = 0
   for i in range(len(energy)):
       if i % 2 == 0:
           prefix_sum += energy[i] * 2
       else:
           prefix_sum += energy[i]
   return prefix_sum

function solution(energy) {
   let prefixSum = 0;
   for (let i = 0; i < energy.length; i++) {
       if (i % 2 === 0) {
           prefixSum += energy[i] * 2;
       } else {
           prefixSum += energy[i];
       }
   }
   return prefixSum;
}

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.