C# Coding Test Course, Getting Interval Sum 2

Problem Definition

Given an integer array nums and two integers left and right, we need to solve the problem of calculating the range sum from index left to right within nums. The range sum is defined as follows:

sum = nums[left] + nums[left + 1] + ... + nums[right]

The length of the array is between 1 and 10^5, and left and right are values between 0 and nums.Length - 1.

Example

Input

nums = [1, 2, 3, 4, 5]
left = 1
right = 3

Output

sum = 9

Here, the range sum is 2 + 3 + 4 = 9.

Approach to the Problem

There are two approaches to solve this problem:

• Using a direct loop
• A more efficient method using a prefix sum array

1. Using a Direct Loop

First, the simplest method is to iterate over the range using a loop and calculate the sum. However, this method has a time complexity of O(n) when the range is large, making it inefficient.

2. Using a Prefix Sum Array

To solve this problem more efficiently, we can use a prefix sum array. A prefix sum array stores the cumulative sum at each index of the given array, reducing the number of loops.

The process of constructing a prefix sum array is as follows:

prefix[0] = nums[0]
prefix[i] = prefix[i - 1] + nums[i] (1 ≤ i < nums.Length)

By utilizing this constructed prefix sum array, we can calculate the range sum in O(1) time complexity. The range sum is calculated as follows:

sum = prefix[right] - prefix[left - 1] (left > 0)
sum = prefix[right] (left == 0)

C# Code Implementation

Now, let’s write the C# code based on the methods explained above. The code below calculates the range sum based on the given array and range.

Code

using System;

class Program {
    static void Main(string[] args) {
        int[] nums = { 1, 2, 3, 4, 5 };
        int left = 1;
        int right = 3;

        int result = GetRangeSum(nums, left, right);
        Console.WriteLine(result);
    }

    static int GetRangeSum(int[] nums, int left, int right) {
        int n = nums.Length;
        int[] prefix = new int[n];
        prefix[0] = nums[0];

        // Initialize the prefix array
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] + nums[i];
        }

        // Calculate the range sum
        if (left == 0) {
            return prefix[right];
        }
        return prefix[right] - prefix[left - 1];
    }
}

This code takes the given array nums and the range left and right as inputs and returns the range sum. It efficiently calculates the range sum using a prefix sum array.

Complexity Analysis

Now, let’s analyze the time and space complexity of the code we wrote.

Time Complexity

The process of initializing the prefix array has a time complexity of O(n), while the range sum calculation has a time complexity of O(1). Therefore, the overall time complexity is O(n).

Space Complexity

Since O(n) additional space is required to store the prefix array, the space complexity is also O(n).

Conclusion

In this post, we covered the range sum problem. By utilizing an efficient approach with a prefix sum array, we can calculate the range sum in O(1) time complexity. This technique can be effectively applied to various algorithm problems, so be sure to remember it.

In the next post, we will tackle another algorithm problem. Thank you!