Hello! In this post, we will cover the second part of the job interview algorithm problem-solving lecture, focusing on the range sum problem using C#. This problem may seem simple, as it involves calculating the sum of consecutive numbers, but it requires an efficient approach.
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 = 3Output
sum = 9Here, 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!