Leetcode – Range Sum Query – Immutable Solution in Python

Spread the love

In this thorough article, we will take an in-depth look at a classic problem on LeetCode, called ‘Range Sum Query – Immutable’. This problem is widely used in coding interviews and provides an opportunity to explore the concept of prefix sums and dynamic programming. We will break down the problem statement, and explore different approaches to solve this problem, analyzing their respective time and space complexities.

Introduction

Let’s start with the problem statement:

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. Implement the NumArray class:

  • NumArray(int[] nums) initializes the object with the integer array nums.
  • int sumRange(int i, int j) returns the sum of the elements of the nums array, inclusive, between indices i and j.

Example:

Input:

["NumArray","sumRange","sumRange","sumRange"]

[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]

Output:

[null, 1, -1, -3]

Understanding the Problem

The problem requires us to create a data structure that efficiently computes the sum of elements in a subarray of a given array of integers. Specifically, for multiple queries, we need to find the sum of elements between two indices, inclusive.

Approach 1: Brute Force

The most straightforward approach would be to calculate the sum for each query by iterating through the elements between the given indices.

  1. For the NumArray constructor, simply store the nums array.
  2. For the sumRange method, iterate from index i to j, and accumulate the sum.
class NumArray:

    def __init__(self, nums):
        self.nums = nums
        
    def sumRange(self, i, j):
        return sum(self.nums[k] for k in range(i, j + 1))

Time Complexity:

O(n) per query – where n is the number of elements between indices i and j.

Space Complexity:

O(1) – excluding the space needed to store the input array.

However, this approach is not efficient, especially when dealing with a large number of queries or large arrays.

Approach 2: Prefix Sum

To optimize the sumRange queries, we can preprocess the array by creating an array of prefix sums. Prefix sums can significantly reduce the time complexity of range sum queries.

  1. In the NumArray constructor, build an array prefixSum, where prefixSum[i] is the sum of elements nums[0] + nums[1] + ... + nums[i].
  2. For the sumRange method, return prefixSum[j] - prefixSum[i - 1] if i > 0, else return prefixSum[j].
class NumArray:

    def __init__(self, nums):
        self.prefixSum = [0] * (len(nums) + 1)
        for i in range(1, len(nums) + 1):
            self.prefixSum[i] = self.prefixSum[i - 1] + nums[i - 1]
        
    def sumRange(self, i, j):
        return self.prefixSum[j + 1] - self.prefixSum[i]

Time Complexity:

O(1) per query – Preprocessing takes O(n), but each query can be answered in constant time.

Space Complexity:

O(n) – We are using an additional array to store the prefix sums.

Conclusion:

The ‘Range Sum Query – Immutable’ problem on LeetCode is a staple example showcasing the power of prefix sums in optimizing range queries. By using a prefix sum array, we can reduce the time complexity of each query to constant time, making it a highly efficient solution especially when dealing with large datasets.

Leave a Reply