In this post we will tackle the LeetCode 307. Range Sum Query – Mutable problem using the Java programming language and the VSCode IDE on a Windows computer. Unless you have a good reason (i.e., keep test code and solution on the same source code) my suggestion is to solve the problem using the online IDE provided by LeetCode.
Given an integer array nums, handle multiple queries of the following types: o Update the value of an element in nums. o Calculate the sum of the elements of nums between indices left and right inclusive where left <= right. Implement the NumArray class: o NumArray(int[] nums) Initializes the object with the integer array nums. o void update(int index, int val) Updates the value of nums[index] to be val. o int 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]). Constraints: o 1 <= nums.length <= 3 * 10^4 o -100 <= nums[i] <= 100 o 0 <= index < nums.length o -100 <= val <= 100 o 0 <= left <= right < nums.length o At most 3 * 10^4 calls will be made to update and sumRange. Related Topics: * Array o Design o Binary Indexed Tree * Segment Tree
We are given an int[] and asked to perform two operations as part of a class.
The simplest approach is to compute the sum of all integers from left to right and keep them in an int[] array `sums`. That takes O(n) time and O(n) space. When a query for the sum at a specific index is made, we are able to respond by looking into the int[] `sums` in O(1) time. Updating a value at a specified index forces us to add to all the values in `sums` the delta between the original value and the current. This operation takes O(n) time.
It seems that the best suggestion would be to use a segment tree. To experiment with such data structure I found Segment Tree | Set 1 (Sum of given range) and Segment tree | Efficient implementation articles with associate code in the GeeksforGeeks website.
For a set of nice diagrams / illustrations for the Segment Tree implementation I found happygirlzt/algorithm-illustrations on GitHub.
A segment tree, also known as a statistic tree, is a tree data structure used for storing information about intervals, or segments. It allows querying which of the stored segments contain a given point.
In addition to meet the requirements for the problem in question, the required operations take O(log(n)) each.
class NumArray {
public NumArray(int[] nums) {
}
public void update(int index, int val) {
}
public int sumRange(int left, int right) {
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* obj.update(index,val);
* int param_2 = obj.sumRange(left,right);
*/
The requirements boil to completing the three methods in the signature for the NumArray class.
NumArray, sumRange, update, sumRange 1, 3, 5 0, 2 1, 2 0, 2 main <<< n: 3 main <<< m: 4 main <<< cmdArr: [NumArray, sumRange, update, sumRange] main <<< argArr: [1, 3, 5] [0, 2] [1, 2] [0, 2] main <<< root: (sum: 9 [0 : 2]) main <<< preOrder: (sum: 9 [0 : 2]) (sum: 4 [0 : 1]) (sum: 1 [0 : 0]) (sum: 3 [1 : 1]) (sum: 5 [2 : 2]) main <<< levelOrder: (sum: 9 [0 : 2]) (sum: 4 [0 : 1]) (sum: 5 [2 : 2]) (sum: 1 [0 : 0]) (sum: 3 [1 : 1]) main <<< output: [null, 9, null, 8] NumArray 1,3,5,7,9,11 main <<< n: 6 main <<< m: 1 main <<< cmdArr: [NumArray] main <<< argArr: [1, 3, 5, 7, 9, 11] main <<< root: (sum: 36 [0 : 5]) main <<< preOrder: (sum: 36 [0 : 5]) (sum: 9 [0 : 2]) (sum: 4 [0 : 1]) (sum: 1 [0 : 0]) (sum: 3 [1 : 1]) (sum: 5 [2 : 2]) (sum: 27 [3 : 5]) (sum: 16 [3 : 4]) (sum: 7 [3 : 3]) (sum: 9 [4 : 4]) (sum: 11 [5 : 5]) main <<< levelOrder: (sum: 36 [0 : 5]) (sum: 9 [0 : 2]) (sum: 27 [3 : 5]) (sum: 4 [0 : 1]) (sum: 5 [2 : 2]) (sum: 16 [3 : 4]) (sum: 11 [5 : 5]) (sum: 1 [0 : 0]) (sum: 3 [1 : 1]) (sum: 7 [3 : 3]) (sum: 9 [4 : 4]) main <<< output: [null]
Since I am not developing the solution using the online IDE provided by LeetCode, I have to develop a simple test scaffold to read and populate the input `nums` int[] array, the different commands and associated argument,, call the methods of interest passing the associated arguments, and displaying the results. The test scaffold IS NOT PART OF THE SOLUTION.
Each test case is separated from the next by two blank lines.
The first line holds the list of commands to execute, followed by the associated arguments for each command on separate lines.
After the input lines are parsed the collected values are displayed to allow us to verify that all is well before calling the methods of interest.
The last line on each test case displays the output associated with each method invocation. Note that the number of commands in the first input line matches the number of results in the `output` Integer[] array.
(sum: 36 [0 : 5])
/ \
/ \
/ \
/ \
(sum: 9 [0 : 2]) (sum: 27 [3 : 5])
/ \ / \
/ \ / \
/ \ / \
/ \ / \
(sum: 4 [0 : 1]) (sum: 5 [2 : 2]) (sum: 16 [3 : 4]) (sum: 11 [5 : 5])
/ \ / \
/ \ / \
/ \ / \
/ \ / \
(sum: 1 [0 : 0]) (sum: 3 [1 : 1]) (sum: 7 [3 : 3]) (sum: 9 [4 : 4])
This diagram mimics one of the diagrams in the happygirlzt github repository. I created it using the output generated by the test scaffold.
/**
* Test scaffold
* @throws IOException
*
* !!! NOT PART OF THE SOLUTION !!!
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read cmdArr ****
String[] cmdArr = Arrays.stream(br.readLine().trim().split(","))
.map(cmd -> cmd.trim())
.toArray(size -> new String[size]);
// **** for ease of use ****
int m = cmdArr.length;
// **** declare argArr ****
int[][] argArr = new int[m][];
// **** populate argArr ****
for (int i = 0; i < m; i++)
argArr[i] = Arrays.stream(br.readLine().trim().split(","))
.map(cmd -> cmd.trim())
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// **** compute n ****
int n = argArr[0].length;
// ???? ????
System.out.println("main <<< n: " + n);
System.out.println("main <<< m: " + m);
System.out.println("main <<< cmdArr: " + Arrays.toString(cmdArr));
System.out.println("main <<< argArr: ");
for (int i = 0; i < argArr.length; i++)
System.out.println(Arrays.toString(argArr[i]));
// **** holds output ****
Integer[] output = new Integer[m];
// **** for starters ****
NumArray numArray = null;
// **** loop calling class methods ****
for (int i = 0; i < m; i++) {
switch (cmdArr[i]) {
case "NumArray":
numArray = new NumArray(argArr[i]);
// ???? ????
System.out.println("main <<< root: " + numArray.root.toString());
System.out.println("main <<< preOrder: ");
System.out.print(numArray.preOrder(numArray.root));
System.out.println("main <<< levelOrder:");
System.out.println(numArray.levelOrder(numArray.root));
break;
case "sumRange":
output[i] = numArray.sumRange(argArr[i][0], argArr[i][1]);
break;
case "update":
numArray.update(argArr[i][0], argArr[i][1]);
break;
default:
System.out.println("main <<< UNEXPECTED cmdArr[" + i + "] ==>" + cmdArr[i] + "<==");
break;
}
}
// **** display output ****
System.out.println("main <<< output: " + Arrays.toString(output));
}
The test scaffold starts by reading the input lines. The associated variables are then displayed.
The `numArray` variable is created. It will hold the `root` to the Segment Tree.
The following loop calls each command associated with the respective arguments. The results of each method call is stored in the `output` Integer[] array. The array is displayed after processing all method calls.
/**
*
*/
static class TreeNode {
/**
* Class members.
*/
public int sum; // sum in this range
public int start; // start index
public int end; // end index
public TreeNode left;
public TreeNode right;
/**
* Constructor.
*/
public TreeNode(int s, int e) {
this.start = s;
this.end = e;
}
/**
* String representation.
*/
@Override
public String toString() {
return String.format("(sum: %2d [%d : %d])", sum, start, end);
}
}
The TreeNode class is used to implement the segment tree. We declare the class members and a constructor. I added the `toString` method to experiment and display the TreeNode data structure. The `toString` method IS NOT PART OF THE SOLUTION.
/**
* Runtime: 98 ms, faster than 52.21% of Java online submissions.
* Memory Usage: 68.4 MB, less than 98.99% of Java online submissions.
*
* 15 / 15 test cases passed.
* Status: Accepted
* Runtime: 98 ms
* Memory Usage: 68.4 MB
*/
static class NumArray {
/**
* Class members.
*/
TreeNode root = null;
// other methods to follow ...
}
In the comments section of the NumArray class one can find the performance information for the different test cases executed by LeetCode when I submit the code for evaluation.
The `root` variable holds the root for the segment tree. The methods that follow will be discussed as we see their implementation.
/**
* Initializes the object with the integer array nums.
*/
public NumArray(int[] nums) {
root = buildTree(nums, 0, nums.length - 1);
}
The constructor for the `NumArray` class builds the segment tree and returns the root of the tree which is assigned to the `root` variable.
/**
* Build the tree.
* Recursive call.
*/
private TreeNode buildTree(int[] nums, int start, int end) {
// **** base case ****
if (start > end) return null;
// **** initialization ****
TreeNode res = new TreeNode(start, end);
// **** leaf node ****
if (start == end) {
res.sum = nums[start];
}
// **** not a leaf node ****
else {
// **** compute mid point in range ****
var mid = start + (end - start) / 2;
// **** generate left child subtree ****
res.left = buildTree(nums, start, mid);
// **** generate right child subtree ****
res.right = buildTree(nums, mid + 1, end);
// **** update sum ****
res.sum = res.left.sum + res.right.sum;
}
// **** ****
return res;
}
This recursive method is used by the constructor to populate the nodes in the segment tree.
/**
* Recursive call.
*/
private void update(TreeNode root, int i, int val) {
// **** leaf node ****
if (root.start == root.end) {
root.sum = val;
} else {
// **** ****
var mid = root.start + (root.end - root.start) / 2;
// **** go left ****
if (i <= mid) {
update(root.left, i, val);
}
// **** go right ****
else {
update(root.right, i, val);
}
// **** update sum ****
root.sum = root.left.sum + root.right.sum;
}
}
The `update` private method is used to process an update to the value `val` in the segment tree at the specified index `i`.
/**
* Updates the value of nums[index] to be val.
* Recursion entry point.
*/
public void update(int i, int val) {
update(root, i, val);
}
This is the entry point for the `update` method.
/**
*
*/
private int query(TreeNode root, int i, int j) {
// **** ****
if (root.start == i && root.end == j) {
return root.sum;
}
// **** ****
else {
// **** compute mid value ****
var mid = root.start + (root.end - root.start) / 2;
// **** ****
if (j <= mid) {
return query(root.left, i, j);
}
// **** ****
else if (i >= mid + 1) {
return query(root.right, i , j);
}
// **** ****
else {
return query(root.left, i, mid) + query(root.right, mid + 1, j);
}
}
}
The `query` private method is used to query the segment tree for a value within the specified range.
/**
* Returns the sum of the elements of nums
* between indices left and right inclusive
* (i.e. nums[left] + nums[left + 1] + ... + nums[right]).
*/
public int sumRange(int i, int j) {
return query(root, i, j);
}
The `sumRange` method returns the sum of the values within the specified range. It does so by calling the recursive private method with the same name which we looked at previously.
/**
* In-order traversal.
* Entry function.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
public String inOrder(TreeNode root) {
// **** initialization ****
StringBuilder sb = new StringBuilder();
// **** populate string builder ****
inOrder(root, sb);
// **** return string ****
return sb.toString();
}
/**
* In-order traversal.
* Helper function.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
private void inOrder(TreeNode root, StringBuilder sb) {
// **** base case ****
if (root == null) return;
// **** traverse left ****
inOrder(root.left, sb);
// **** add node to string builder ****
sb.append(root.toString() + "\n");
// **** traverse right ****
inOrder(root.right, sb);
}
These methods are used to perform an in-order traversal of the segment tree. I used them to debug and experiment with the code. They ARE NOT PART OF THE SOLUTION.
/**
* Post-order traversal.
* Entry function.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
public String postOrder(TreeNode root) {
// **** initialization ****
StringBuilder sb = new StringBuilder();
// **** populate string builder ****
postOrder(root, sb);
// **** return string ****
return sb.toString();
}
/**
* Post-order traversal.
* Helper function.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
private void postOrder(TreeNode root, StringBuilder sb) {
// **** base case ****
if (root == null) return;
// **** traverse left ****
postOrder(root.left, sb);
// **** traverse right ****
postOrder(root.right, sb);
// **** add node to string builder ****
sb.append(root.toString() + "\n");
}
These methods are used to perform a post-order traversal of the segment tree. I used them to debug and experiment with the code. They ARE NOT PART OF THE SOLUTION.
/**
* Pre-order traversal.
* Entry function.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
public String preOrder(TreeNode root) {
// **** initialization ****
StringBuilder sb = new StringBuilder();
// **** populate string builder ****
preOrder(root, sb);
// **** return string ****
return sb.toString();
}
/**
* Pre-order traversal.
* Helper function.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
private void preOrder(TreeNode root, StringBuilder sb) {
// **** base case ****
if (root == null) return;
// **** add node to string builder ****
sb.append(root.toString() + "\n");
// **** traverse left ****
preOrder(root.left, sb);
// **** traverse right ****
preOrder(root.right, sb);
}
These methods are used to perform a pre-order traversal of the segment tree. I used them to debug and experiment with the code. They ARE NOT PART OF THE SOLUTION.
/**
* Level-order tree traversal.
* Returns string with tree representation.
*
* !!! NOT PART OF THE SOLUTION !!!
*/
public String levelOrder(TreeNode root) {
// **** initialization ****
StringBuilder sb = new StringBuilder();
LinkedList<TreeNode> primaryQ = new LinkedList<>();
LinkedList<TreeNode> secondaryQ = new LinkedList<>();
// **** prime the primary queue ****
primaryQ.offer(root);
// **** loop while the primary queue is not empty O(n) ****
while (!primaryQ.isEmpty()) {
// **** remove head node ****
TreeNode node = primaryQ.remove();
// **** append node to string ****
sb.append(node.toString() + " ");
// **** offer left child ****
if (node.left != null) secondaryQ.offer(node.left);
// **** offer right child ****
if (node.right != null) secondaryQ.offer(node.right);
// **** swap queues if needed ****
if (primaryQ.isEmpty() && !secondaryQ.isEmpty()) {
// **** primary points to secondary queue ****
primaryQ = secondaryQ;
// **** create new secondary queue ****
secondaryQ = new LinkedList<>();
// **** update string builder ****
sb.append("\n");
}
}
// **** return string representation ****
return sb.toString();
}
This method is used to perform a level-order traversal of the segment tree. I used it to debug and experiment with the code. This IS NOT PART OF THE SOLUTION.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named RangeSumQueryMutableIII.
I spent a couple days researching and experimenting with the code.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John