LeetCode 370: Range Addition Solution

Master LeetCode problem 370 (Range Addition), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

370. Range Addition

Medium

Array Prefix Sum

Problem Explanation

Explanation

Given a list of non-negative integers length and a set of operations, where each operation consists of three integers start, end, and inc, update the list such that length[i] is incremented by inc for all indices i between start and end (inclusive).

To solve this problem efficiently, we can utilize the concept of prefix sum. Instead of updating each index in the list for each operation, we can keep track of the increment value at the start index and the negative increment value at the end+1 index. Then we can calculate the final increments by accumulating the values from left to right. This approach helps us avoid updating all indices individually.

Solution Code

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] result = new int[length];
        
        for (int[] update : updates) {
            int start = update[0];
            int end = update[1];
            int inc = update[2];
            
            result[start] += inc;
            if (end + 1 < length) {
                result[end + 1] -= inc;
            }
        }
        
        int sum = 0;
        for (int i = 0; i < length; i++) {
            sum += result[i];
            result[i] = sum;
        }
        
        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 370 (Range Addition)?

This page provides optimized solutions for LeetCode problem 370 (Range Addition) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 370 (Range Addition)?

The time complexity for LeetCode 370 (Range Addition) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 370 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 370 in Java, C++, or Python.

Back to LeetCode Solutions