Contiguous elements of the list sum to K

Question

The task:

Given a list of integers and a number K, return which contiguous elements of the list sum to K.

For example, if the list is [1, 2, 3, 4, 5] and K is 9, then it should return [2, 3, 4].

My solution

// init
const arr = [1, 2, 3, 4, 5];
const K = 9;
// main
const getContiguousElementsSum = (arr, K) => {
 if (arr.length === 0 || K < 0) {
 return null;
 }
 let sum = 0;
 const returnResult = [];
 const found = arr.some(x => {
 sum += x;
 returnResult.push(x);
 return sum === K;
 });
 // exit case
 if (found) {
 return returnResult;
 }
 // recursive case
 return getContiguousElementsSum(arr.slice(1), K);
};
console.log(getContiguousElementsSum(arr, K));

Is there a shorter and/or more readable solution?

• Matthew Page: Could it also return [4, 5] ? I'm thinking work the array backwards (if it's always in order)
• thadeuszlay: Not from the given task. It explicitly says [2,3,4] for K=9.
• Peter Taylor: You haven't said what the source of the specification was, but I think the point implicit in Matthew Page's question (which I was also going to raise) is that if you can you should push back on the specifier and ask them for an unambiguous ruling on which of multiple possible answers should be returned.

Answer 1

Some points regarding readability.

Source code noise reduces overall readability. Noise is anything that is redundant or does not aid in the understanding of the code.

There are many way to introduce noise.

Not addressing the reader

One assumes that the reader of your code is proficient in the language and does not need to be told what various tokens do. You have two comments that assume the coder knows nothing.

• // exit case adds nothing to the code or the readability, thus it is noise and actually detracts from readability.
• // recursive case Really, and I thought it was flying a kite... :P

If you are writing code as a teaching example then you assume the reader has limited knowledge and in that case the obvious is stated in properly structured english (or whatever language)

• // exit case would be // When found exit the function returning the returnResult array.

  Note that if you add a comment it should be above the line it refers to with a blank line above it. Or it should be at the end of the line not going past the right margin (80 or I prefer 120 characters)

  Thus the example above would be

.

 ...
 return sum === K;
});
// When found exit the function returning the returnResult array.
if (found) {
 return returnResult;
}

Or

 ...
 return sum === K;
}); 
if (found) { // When found exit the function returning the returnResult array.
 return returnResult;
}

Misleading the reader

This is the worst type of noise.

Comments are not subject to compilation, verification, or any type of vetting process. The author quickly becomes blind to comments and will overlook them when making changes. The result is that comments can be in direct opposition of the code they are commenting. This will confuse the reader as to the intent of the code. They are left to guess, is the code in error or the comment.

• // main is a pullover from other languages and is general the entry point of the entire app, there is only one main, and it is only ever called once. It does not apply to JS and should not be used as a comment.
• // init initialize is not accurate, you are defining variable not reenstating them. Some constants can not be initialized as they can not change eg K. Others can be initialized eg initialize the array arr.length = 0; arr.push(...[1,2,3,4,5]);

Naming noise

We humans read words not by scanning each character in turn, but rather by recognising the shape, and using cues (such as the start and end characters).

Good names are short and to the point. They rely strongly on the context in which they are created to give them meaning. The more frequently a variable is used the shorter it is the better, as you reduce the overall bulk of the code.

• returnResult does the verb return add to the understanding of the name and what the variable represents. Not at all and thus can be considered naming noise. result is clear. We also use abbreviations in code, though you must use the common form, do not make up abbreviations. The common abbreviation for result is res

• getContiguousElementsSum is incorrect. When you get... something you know it exists and where it is. The function does not get a result, it searches for a result and if it exists returns it. Thus replace the get with find

  ...Elements... In JS and most languages the content of an array is referred to as array items, not array elements. In JS this is particularly important as in many contextes elements refer to DOM objects and thus using the term elements is misleading.

  ...Sum No you get items that sum to. getBlahBlahSum inferes a numeric result which the function does not do.

  The function name could be findContiguousItemsSummingTo It infers how the function works (a search), what the search criteria is (summing to), and what it returns (an array of items).

  The name is rather long and there are no convenient abbreviations but the find in this case can be dropped, items to arr, and to to 2 contiguousArrSumming2

Verbosity

There are many ways to stone a crow, and in most languages that remains true. The best way is the shortest way, less code is more readable by simple virtue of reducing time to read, and making it easier to scan large sections of code.

Readability is in part the ability to write a large code base. A good coder can create apps that have hundreds of thousands of lines of code. Saving 10% is substantial, saving 50% is a order of magnitude easier to comprehend.

You have 6 lines for something that could be one line.

// exit case
if (found) {
 return returnResult;
}
// recursive case
return getContiguousElementsSum(arr.slice(1), K);

You have 3 lines that could be one.

if (arr.length === 0 || K < 0) {
 return null;
}

They become

if (arr.length === 0 || K < 0) { return }
return found ? res : contiguousArrSumming2((arr.shift(), arr), val);

Note on null

Javascript functions do not return null Null is a placeholder, it means I have something that I reserve a reference for (Note The (削除) idiots (削除ここまで) people that wrote the DOM API miss used null). When something is not defined it is undefined To help reduce code size in JS undefined is the default return type and need not be defined. return null is both semantically incorrect and too verbose.

Reducing source code bulk

You can reduce code size using commas to separate lines. We use them in english to keep the size of a text document small and compact, you should do the same in code.

const contiguousArrSumming2 = (arr, val) => {
 var sum = 0;
 const res = [];
 const scan = num => (sum += num, res.push(num), sum === bal);
 if (arr.length === 0 ) { return res }
 return arr.some(scan) ? res : contiguousArrSumming2(arr.slice(1), val);
};
console.log(contiguousArrSumming2([1, 2, 3, 4, 5], 9));

Personally I would further reduce to

function contiguousArrSumming2(arr, val, res = []) {
 var sum = 0;
 const scan = num => (sum += num, res.push(num), sum === bal);
 return !arr.length || arr.some(scan) ? res : contiguousArrSumming2((arr.shift(), arr), val);
}

A competent coder will have no trouble reading the above code and should instantly spot the very important difference from your original.

Be professional.

Remember those that read your code are professionals. When you present your code and it looks like its a tutorial piece all you do is put distrust in your code as poor/simple language use and pointless comments make you look like a beginner, the result is they will rather rewrite than update or fix, making your efforts pointless.

Answer 2

// init
const arr = [1, 2, 3, 4, 5];
const K = 9;
// main
const getContiguousElementsSum = (arr, K) => {

It seems to me to be unnecessarily confusing to alias variable identifiers like this.

---

 if (arr.length === 0 || K < 0) {
 return null;
 }

I don't see this anywhere in the specification you've quoted. I would expect the function to handle K === 0 by returning [], and to give [-1,-2,-3] for getContiguousElementsSum([-1,-2,-3,-4], -6).

Also, since the specification doesn't say anything about error cases, I would assume by default that it should throw something (probably RangeError) if no matching subarray can be found.

---

 const found = arr.some(x => {
 sum += x;
 returnResult.push(x);
 return sum === K;
 });

It would be kinder to the garbage collector to just track indexes and use slice when you find a match.

---

 // recursive case
 return getContiguousElementsSum(arr.slice(1), K);

The overall complexity of this implementation is \$O(n^2)\$. It can be done quite easily in \$O(n \lg n)\$ in full generality using just arrays, and in \$O(n)\$ if you have an efficient set implementation, by using the property $$\sum_{i=a}^b A[i] = \left(\sum_{i=0}^a A[i]\right) - \left(\sum_{i=0}^{b-1} A[i]\right)$$To build an array of \$\left(\sum_{i=0}^a A[i]\right)\$ takes linear time; then either convert it into a set or sort it; and for each element in the array of partial sums you need to test for the presence of that partial sum minus the target.

And, of course, it can be done in \$O(n)\$ time with just arrays if you're guaranteed that the elements are positive, as described in janos' answer.

Answer 3

The current implementation sums the values of arr[0] + arr[1] + ... until the amount is equal to K, or if not found, then recursively call the function again, with the first element of the input array sliced off. For example if the input array is [3, 2, 1] and K is 1, it will compute 3 + 2 + 1, then 2 + 1, then 1. This is effectively trying all possible contiguous sub-sequences until a match is found, brute-force.

The only given example input used only positive numbers. If we can assume this is the case for all inputs, then a more efficient algorithm exists. In that case you could keep track of two index pointers in the array, start and end, and a running sum. Read elements one by one, moving forward start or end or both as needed, according to the current running sum. (This is technique is also known as the caterpillar method.) This will require a single pass over the elements (\$O(n)\$), without unnecessary summing or slicing.

const getContiguousElementsSum = (arr, K) => {
 for (let sum = 0, start = 0, end = 0; end < arr.length; end++) {
 sum += arr[end];
 while (K < sum) {
 sum -= arr[start];
 start++;
 }
 if (sum == K) {
 return arr.slice(start, end + 1);
 }
 }
 return null;
};

However, if there are negative values in the input, this technique will not work. When there are negative values, it's no longer obvious how to move the index pointers. One path may be to increase the range to compensate, another path may be to omit the negative element. With the logic branching, a linear solution can no longer work.

• Blindman67: Your function fails when the OP's solution finds the correct sequence. Consider the array [1,2,3,1,-1967,3,1,2,3,1,45,2,3,1] your function fails for many values. Eg sequences summing from 45 to 58 (inclusive) are not found.
• janos: @Blindman67 good point, thanks. I updated the post with a crucial assumption that was missed.