Range Sum Query - Immutable

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

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

1. You may assume that the array does not change.
2. There are many calls to sumRange function.

Approach: Compute the sum till all the ith index in the array for all  0 <= i < n. Use this precomputed values to return the sum.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

class NumArray { public: vector<int> array; vector<int> sum; NumArray(vector<int> &nums) { for(int i = 0 ; i < nums.size(); i++){ array.push_back(nums[i]); } //preProcess after the vector is initialized preProcess(); } //preProcess to store the sum till all i in a vector since the function is called many times void preProcess(){ sum.push_back(0); for(int i = 1; i <= array.size(); i++){ sum.push_back(sum[i - 1] + array[i - 1]); } } int sumRange(int i, int j) { //return sum directly from the calculated sums int res = sum[j + 1] - sum[i]; return res; } }; // Your NumArray object will be instantiated and called as such: // NumArray numArray(nums); // numArray.sumRange(0, 1); // numArray.sumRange(1, 2);

Read More

Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16]. This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Approach: First find the place for the newly arrived interval in the existing intervals. Then perform the approach used in this problem.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ class Solution { public: vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) { int i = 0; int n = intervals.size(); vector<Interval> out; //find the location of new interval while(i < n && intervals[i].start < newInterval.start){ i++; } //add the vector at the specified location intervals.insert(intervals.begin() + i, newInterval); //merge the possible intervals stack<Interval> it; it.push(intervals[0]); n = intervals.size(); for(int i = 1; i < n; i++){ Interval topInterval = it.top(); //if start time of next is after the end of the prev, push the next if(intervals[i].start > topInterval.end){ it.push(intervals[i]); }else if(intervals[i].end > topInterval.end){ //if start time of next is before the end of the prev and the end of the next is after the end of the prev, then update the end of the prev topInterval.end = intervals[i].end; it.pop(); it.push(topInterval); } } while(!it.empty()){ Interval curr = it.top(); out.push_back(curr); it.pop(); } //reverse to get the output reverse(out.begin(), out.end()); return out; } };

Read More