Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Go

Solution: Range Sum Query - Immutable

Explore how to use a prefix sum array to efficiently calculate the sum of elements between given indices in an integer array. Learn to implement the NumArray class with a constructor and sumRange method, achieving constant time queries after linear preprocessing.

We'll cover the following...

Statement

You are given an integer array, nums, and you need to handle multiple queries of the following type:

  • Query: Calculate the sum of elements in nums between indices i and j (inclusive), where i <= j.

Implement the NumArray class to support the following operations efficiently:

  • Constructor: Initializes the object with the integer array nums.

  • sumRange(i, j): Returns the sum of the elements of nums between indices i and j (inclusive), i.e., the sum of nums[i] + nums[i + 1] + ... + nums[j].

Constraints:

  • 1≤1 \leq nums.length ≤103\leq 10^3

  • −105≤-10^5 \leq nums[i] ...