Tuesday, December 22, 2015

Leetcode: Range Sum Query - Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.
Naive Solution 1: 
The first method is the most straight-forward. Use an array to store the numbers. So the update takes O(1) time. sumRange() takes O(n) time. 

Naive Solution 2:
Similar to the Range Sum Query - Immutable, we calculate the prefix of the elements in the array. Therefore, for the update(), it takes O(n) time to update the elements after the updated element. But the sumRange() take O(1) time. 

Better Solution:
Since the problem assumes that the two functions are called evenly, there exists a better method using Segment Tree in O(logn) time. 

Code (Java):
public class NumArray {
    class SegmentTreeNode {
        int start, end;
        int sum;
        SegmentTreeNode left, right;
        
        // Constructor
        public SegmentTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
            sum = 0;
        }
        
        public SegmentTreeNode(int start, int end, int sum) {
            this.start = start;
            this.end = end;
            this.sum = sum;
        }
        
    }
    
    private SegmentTreeNode root;
    
    public NumArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return;
        }
        root = buildSegmentTree(nums, 0, nums.length - 1);
    }

    void update(int i, int val) {
        updateHelper(root, i, val);
    }
    
    private void updateHelper(SegmentTreeNode root, int i, int val) {
        if (root == null) {
            return;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        
        if (i <= mid) {
            updateHelper(root.left, i, val);
        } else {
            updateHelper(root.right, i, val);
        }
        
        if (root.start == root.end && root.start == i) {
            root.sum = val;
            return;
        }
        
        root.sum = root.left.sum + root.right.sum;

    }

    public int sumRange(int i, int j) {
        return sumRangeHelper(root, i, j);
    }
    
    private int sumRangeHelper(SegmentTreeNode root, int start, int end) {
        if (root == null || end < root.start || start > root.end || 
            start > end) {
            return 0;
        }
        
        if (start <= root.start && end >= root.end) {
            return root.sum;
        }
        
        int mid = root.start + (root.end - root.start) / 2;
        
        return sumRangeHelper(root.left, start, Math.min(end, mid)) + 
               sumRangeHelper(root.right, Math.max(mid + 1, start), end);
    }
    
    private SegmentTreeNode buildSegmentTree(int[] nums, int start, int end) {
        if (nums == null || nums.length == 0 || start > end) {
            return null;
        }
        
        // Start == end
        if (start == end) {
            return new SegmentTreeNode(start, end, nums[start]);
        }
        
        SegmentTreeNode root = new SegmentTreeNode(start, end);
        int mid = start + (end - start) / 2;
        root.left = buildSegmentTree(nums, start, mid);
        root.right = buildSegmentTree(nums, mid + 1, end);
        
        root.sum = root.left.sum + root.right.sum;
        
        return root;
    }
}


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

Summary:
The take-away message for this problem is there is no such a BEST solution ever. You need to communicate with the interviewer to ask the use cases and choose the best solution. 

No comments:

Post a Comment