LeetCode 862: Shortest Subarray with Sum at Least K

Question

I'm posting my code for a LeetCode problem copied here. If you would like to review, please do so. Thank you for your time!

Problem

• Return the length of the shortest, non-empty, contiguous subarray of nums with sum at least k.
• If there is no non-empty subarray with sum at least k, return -1.

Example 1:

Input: nums = [1], k = 1 Output: 1

Example 2:

Input: nums = [1,2], k = 4 Output: -1

Example 3:

Input: nums = [2,-1,2], k = 3 Output: 3

Note:

• \$1 <= \text{nums.length} <= 50000\$
• \$-10 ^ 5 <= \text{nums}[i] <= 10 ^ 5\$
• \$1 <= k <= 10 ^ 9\$

Code

#include <vector>
#include <algorithm>
#include <deque>

class Solution {
public:
    static int shortestSubarray(std::vector<int> nums, const int k) {
        const int length = nums.size();
        int shortest = length + 1;

        std::deque<int> deque_indicies;

        for (int index = 0; index < length; index++) {
            if (index) {
                nums[index] += nums[index - 1];
            }

            if (nums[index] >= k) {
                shortest = std::min(shortest, index + 1);
            }

            while (!deque_indicies.empty() && nums[index] - nums[deque_indicies.front()] >= k) {
                shortest = std::min(shortest, index - deque_indicies.front());
                deque_indicies.pop_front();
            }

            while (!deque_indicies.empty() && nums[index] <= nums[deque_indicies.back()]) {
                deque_indicies.pop_back();
            }

            deque_indicies.emplace_back(index);
        }

        return shortest <= length ? shortest : -1;
    }
};

• Problem

• Solution

• Discuss

Answer 1

Passing by reference or value

Currently,

std::vector<int> nums

forces callers to pass a copy of the entire vector by value. You could argue that this is actually useful, since your algorithm needs to mutate it (or a copy of it) in-place. My preference is usually to make this copy-step explicit instead:

• Pass a const & reference, not a mutable copy
• Make a local copy of the vector explicitly, invoking the copy constructor
• Mutate your copy.

Spelling

deque_indicies -> deque_indices

Answer 2

This is not a proper review. I just want to show an argument why passign the input by value is actually more useful then passing it by const reference, in this particular case.

Yes, it's true you should not modify the input for the caller, because he didnt ask you to do so.

But it is also true, that your implementation takes advantage of the ability to modify the input.

As @Reinderien proposed, if you pass it by reference and create a copy inside your function you satisfy both the caller (who doesnt want his input changed) and the implementation (who wants to change the input so it can do its job effectively).

int solution(const vector<int> & input)
{
  vector<int> inputClone = input;

  // do the thing mutating inputClone

  return result;
}

But if you passed it by value, you actually satisfy both too and you get a shorter code.

int solution(vector<int> input)
{
  // do the thing mutating input which already is a clone

  return result;
}

What make the pass-by-value approach even better is the fact that now you are allowing the caller to have its input vector mutated, if he doesn't need it after the function is called.

if caller wants immutable input he calls the function directly:

int result = solution(input);

// here input is unchanged and I can work with it

if caller does not care if the input changes he can std::move it into the function:

int result = solution(std::move(input));

// here input is probably changed, but I don't intend to touch it here anymore anyway

This cannot be done with const reference. If you make it accept const reference, the code is doomed to always create a copy, regardless of the caller requiring it.

So yes pass by const reference is generaly prefered, but when the function needs to copy the input so it can modify it so it can work efficiently and not mutate input for caller, use pass by value and let caller decide if he wants it to work with a copy or move the input to the function.