algoadvance

Leetcode 307. Range Sum Query

Problem Statement:

You are given an integer array nums and are required to implement a data structure that supports two operations:

  1. update(int index, int val) - Updates the value of nums[index] to val.
  2. sumRange(int left, int right) - Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

The nums array is not immutable, meaning we need to handle multiple update and range sum queries efficiently.

Clarifying Questions:

  1. What is the size range of the nums array? The size could be in a range of 0 to 30,000.

  2. What are the value ranges of the elements in nums? Elements could be in the range of -10^4 to 10^4.

  3. How frequent are update and sumRange calls? Both operations are frequent and need to be optimized.

  4. Could we have multiple updates before a sumRange query? Yes, multiple updates can happen.

Strategy:

Considering the requirement for multiple efficient updates and range sum queries, using a Binary Indexed Tree (also known as Fenwick Tree) will be an effective approach. This allows both update and sum operations in logarithmic time.

Structure:

  1. Binary Indexed Tree (Fenwick Tree):
    • Use an auxiliary array BIT which helps in achieving update and query operations in O(log n) time.

Code:

class NumArray {
    private int[] nums;
    private int[] BIT;
    private int len;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.len = nums.length;
        this.BIT = new int[len + 1];
        for (int i = 0; i < len; i++) {
            init(i, nums[i]);
        }
    }

    private void init(int index, int val) {
        index += 1;
        while (index <= len) {
            BIT[index] += val;
            index += index & -index;
        }
    }

    public void update(int index, int val) {
        int delta = val - nums[index];
        nums[index] = val;
        init(index, delta);
    }

    private int getSum(int index) {
        int sum = 0;
        index += 1;
        while (index > 0) {
            sum += BIT[index];
            index -= index & -index;
        }
        return sum;
    }

    public int sumRange(int left, int right) {
        return getSum(right) - getSum(left - 1);
    }
}

Time Complexity:

This solution provides an efficient way to handle dynamic updates and range sum queries which are frequent in this context.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI