How I react to algos
More time planning could mean less time correcting. That's why REACTO is so useful. It helps us focus on the plan before we act. Sort of like measuring twice and cutting once. Today, we will work with nested arrays and plan our approach to the solution using REACTO.
Before we move any further, I'd like to poit out the previous 4 posts in the series:
This is REACTO
REACTO is an acronym that represents the method we will use in solving this problem. As a reminder, these are the steps:
- R: Restate
- E: Example
- A: Approach
- C: Code
- T: Test
- O: Optimize
Let's stick to this order and get started!
The Prompt
Write a function called
sum_intervals()that accepts an array of intervals, and returns the sum of all the interval lengths. Overlapping intervals should only be counted once.Intervals are represented by a pair of integers in the form of an array. The first value of the interval will always be less than the second value. Interval example: [1, 5] is an interval from 1 to 5. The length of this interval is 4.
Overlapping Intervals
List containing overlapping intervals:
[
[1,4],
[7, 10],
[3, 5]
]The sum of the lengths of these intervals is 7. Since [1, 4] and [3, 5] overlap, we can treat the interval as [1, 5], which has a length of 4.
R: Restate the prompt
We need to restate the prompt so it could help us plan our approach later. When we restate the prompt we should try to keep our description brief. Brief are easier to scan read while working out the solution.
/*
R: Restate
*/
// create function sumIntervals
// args: array of arrays containing two integers => [[int, int], [int, int], [int, int], ...]
// overlapping intervals are counted once
// return value is integer, sum of all intervals of input array
Clarifying questions:
If there are any lingering questions we should ask them here but we can ask about them later as well. I have none so let's move on.
E: Examples
Let's get some examples listed so we can use it to guide our approach.
sample input
> sumIntervals( [
[1,2],
[6, 10],
[11, 15]
] );
9
> sumIntervals( [
[1,4],
[7, 10],
[3, 5]
] );
7
> sumIntervals( [
[1,5],
[10, 20],
[1, 6],
[16, 19],
[5, 11]
] );
19
A: Approach
This is the heartiest part of our journey to the solution. We need a plan. I like to build the approach as a comment so I could easily reorder them when necessary.
/*
A: Approach
- create function function()
*/
First step is to create the function. Now we need to handle the input. Let's think about why our example says that an interval [1, 5] is 4. When I think about it, 1 to 5 contain 5 numbers. So why is the length 4? Well, if we are dealing with time we don't count every integer but the space between them. So to get from 1 to 2 we will need 1 unit. Same for 1 to 5. Look at it like this:
-
1to2=1unit -
2to3=1unit -
3to4=1unit -
4to5=1unit
That's 4 units total.
/*
A: Approach
- create function function()
- init accumulator for sum of intervals, type int
- init accumulator for visited indices, arr type int
- iter over input intervals array, index i
-- declare const for current interval
-- iter over current interval, index j
--- if the arr accumulator for visited indices does not include this index j
---- increment accumulator for sum intervals by 1
---- push current index j to visited indices array accumulator
- return the sum of intervals accumulator
*/
The comments above lay out the approach. We know that we need to visit every element of the input array. Then we want to take account of the interval numbers we have visited in case we come across them again in another element. Another initial step is to create a variable to hold onto the return value that we can increment as we loop over the input array. We set up an empty array to keep tabs on the visited indices.
Next, we need to iterate over the input array. At each iteration we need to set a constant to hold onto the current interval of the input array. Then we loop over the interval, setting the first value of the interval as the starting index for this loop, and the second value of the interval as the end index. This way we are counting from starting integer to end integer of the interval pair (see below).
interval --> [1, 5]
for(let j=interval[0]; j<interval[1]; j++){ ... }
While in the inner loop, we check if the visited indices array does not include the current index. If the array contains the index we don't want to count it. If the array does not contain the index we need to count it. We do that by incrementing the accumulator for interval sum by 1. Then, while still in the conditional block, we will push the index number of this inner loop to the accumulator of visited indices.
When the outer loop is done we can then return the interval sum accumulator value.
C: Code
Time to code! 🧑💻
Let's set up the function and then copy the approach as comments into the function to use as a guide.
// create function function()
function intervalSum() {
// init accumulator for sum of intervals, type int
let intervalSum = 0;
// init accumulator for visited indices, arr type int
let intArr = [];
// iter over input intervals array, index i
for (let i = 0; i < intervals.length; i++) {
// declare const for current interval
const interval = intervals[i];
// iter over current interval, index j
for (let j = interval[0]; j < interval[1]; j++) {
// if the arr accumulator for visited indices does not include this index j
if (intArr.includes(j) === false) {
// increment accumulator for sum intervals by 1
intervalSum++;
// push current index j to visited indices array accumulator
intArr.push(j);
}
}
}
// return the sum of intervals accumulator
return intervalSum;
}
That should be everything! Now I am going to remove the comments for readability, but I would usually keep comments in if I am saving this to my local machine so that I may review the thought process in the future. Here's the code without the comments:
function sumIntervals(intervals) {
let intervalSum = 0;
let intArr = [];
for (let i = 0; i < intervals.length; i++) {
const interval = intervals[i];
for (let j = interval[0]; j < interval[1]; j++) {
if (intArr.includes(j) === false) {
intervalSum++;
intArr.push(j);
}
}
}
return intervalSum;
}
Doesn't that look great? We could have actually tested the code before removing the comments. Let's continue.
T: Test
Let's test! Here is a Codepen with the function in the JS tab on the left and the results on the right. Feel free to play around with the code and explore.
All of our tests passed! Feel free to play around with the function and the tests to experiment.
O: Optimize
Can you find a more optimal solution than using two for loops? I bet you can find a more efficient solution. That is the task of our next step. At this point we have found the solution so it's worth celebrating. It is good practice to then look for a more optimal solution if one exists.
Thank You
Thank you for taking time out of your day to read this post. Follow me here on DEV if you'd like to see more content like this and follow my explorations into the world of web development. I'll see you around!
Top comments (0)