2
\$\begingroup\$

According to LeetCode, the following question is one of the most frequent interview questions asked by companies such as Facebook and Google. Here, I'm posting C++/Java codes, if you'd like to review, please do so.

LeetCode 560

Given an array of integers and an integer target (K), you need to find the total number of continuous subarrays whose sum equals to target.

Example 1:

Input:nums = [1,1,1], target = 2 Output: 2

Constraints:

The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer target is [-1e7, 1e7].

C++

class Solution {
public:
    int subarraySum(vector<int> &nums, int target) {
        map<int, int> prefix_sum;
        int sum = 0, subarrays = 0;
        prefix_sum[0]++;
        for (int index = 0; index < nums.size(); index++) {
            sum += nums[index];
            subarrays += prefix_sum[sum - target];
            prefix_sum[sum]++;
        }

        return subarrays;
    }
};

Java

class Solution {
    public int subarraySum(int[] nums, int target) {
        int sum = 0, subarrays = 0;
        Map<Integer, Integer> prefixSum = new HashMap<>();
        prefixSum.put(0, 1);

        for (int index = 0; index != nums.length; index++) {
            sum += nums[index];

            if (prefixSum.get(sum - target) != null)
                subarrays += prefixSum.get(sum - target);

            prefixSum.put(sum, -~prefixSum.getOrDefault(sum, 0));
        }

        return subarrays;
    }
}

Reference

\$\endgroup\$
2

2 Answers 2

3
\$\begingroup\$

I have some suggestion for the Java version

Always try to pass the size of the maximum size to the Collection / Map constructor when known

The map has a default size of 16 elements, if you have more elements, the map will have to resize its internal cache. By setting the size, you can prevent the resize and make your code faster.

In this case, you can set the maximum size since it's based on the size of the array + 1.

Map<Integer, Integer> prefixSum = new HashMap<>(nums.length + 1);

Extract the expression to variables when used multiple times

In your code, when you check if the key is present, you can extract the value to a variable to reuse it when present.

Before

if (prefixSum.get(sum - target) != null)
   subarrays += prefixSum.get(sum - target);

After

Integer currentValue = prefixSum.get(sum - target);
if (currentValue != null)
   subarrays += currentValue;

This will be better, since this will prevent the rechecking and the rehashing in the map.

Always add curly braces to loop & if

In my opinion, it's a bad practice to have a block of code not surrounded by curly braces; I saw so many bugs in my career related to that, if you forget to add the braces when adding code, you break the logic / semantic of the code.

Before

if (prefixSum.get(sum - target) != null)
   subarrays += prefixSum.get(sum - target);

After

if (prefixSum.get(sum - target) != null) {
   subarrays += prefixSum.get(sum - target);
}

Extract some of the logic to methods.

In this case, I suggest to extract the map creation to a method; this will allow to group the logic and make the main code shorter.

public int subarraySum(int[] nums, int target) {
   Map<Integer, Integer> prefixSum = buildMap(lengthOfNums + 1);
   //[...]
}

private Map<Integer, Integer> buildMap(int defaultSize) {
   Map<Integer, Integer> prefixSum = new HashMap<>(defaultSize);
   prefixSum.put(0, 1);
   return prefixSum;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ About those curly braces: you know what happens when you don't do that? Heartbleed. Very good advice to add those braces indeed. It doesn't fix everything (as indicated by that article), but it does make the bug more obvious. \$\endgroup\$
    – Mast
    Jun 22, 2020 at 11:08
2
\$\begingroup\$

This will be a review of the C++ code. Some of this applies to the Java version as well, but my Java expertise is very much in the 20th century!

Algorithm

A good choice of algorithm. It may be worth adding some comments to indicate why you've chosen this one. From my reading, it scales well with the size of the input array: O(n) in time and O(n) in additional storage.

Unnecessary class

There is no need in C++ for your function to be a member of a class. Just make it a free function. If the interface is imposed on you, I still recommend a free function, which can be called from a small adapter, like this:

int count_subarrays_matching_sum(const vector<int> &nums, int target);

// Adapter for user that expects a class object
class Solution {
public:
    int subarraySum(vector<int> &nums, int target) const {
        return count_subarrays_matching_sum(nums, target);
    }
};

Unit tests

It's disappointing that you haven't included any tests for this code, particularly since the description gives at least one example of input and output. You could create a simple main() that exercises the function and verifies the output, or use one of the many available test frameworks to take care of the details. For example, using Google Test:

#include <gtest/gtest.h>

TEST(count_subarrays, empty)
{
    EXPECT_EQ(0, count_subarrays_matching_sum({}, 0));
    EXPECT_EQ(0, count_subarrays_matching_sum({}, 0));
}

TEST(count_subarrays, three_ones)
{
    EXPECT_EQ(0, count_subarrays_matching_sum({1, 1, 1}, 0));
    EXPECT_EQ(3, count_subarrays_matching_sum({1, 1, 1}, 1));
    EXPECT_EQ(2, count_subarrays_matching_sum({1, 1, 1}, 2));
}

Let's also include some tests of the tricky case when the elements are all zero:

TEST(count_subarrays, zeros)
{
    EXPECT_EQ(1, count_subarrays_matching_sum({0}, 0));
    EXPECT_EQ(6, count_subarrays_matching_sum({0, 0, 0}, 0));
}

namespace std

You've not shown the #include <map> and #include <vector> that are necessary for compilation. Also, we have std::map and std::vector in the global namespace due to a using that's not shown. That's a bad habit to get into; it's best to get used to writing the std qualifier where necessary. (In fact, since it's only needed twice here, that's the easy approach anyway!).

Data types

If you're mainly a Java programmer, you're probably used to the integer types having the same range on all platforms, but C++ adapts to the target processor in a way that Java doesn't.

Let's look again at the constraints in the question. The elements in the array may range from -1000 to +1000, so using int for those is reasonable (int must be able to represent at least the range [-32768,32767]). However, the target may be as large as ±10,000,000, so int isn't suitable for that. Thankfully, we can include <cstdint> for some suitable large-enough types:

  • std::int32_t - exact 32-bit type (only if possible on this platform)
  • std::int_least32_t - smallest 32-bit (or more) type available
  • std::int_fast32_t - fastest 32-bit (or more) type available

We don't need exactly 32-bit range, so the obvious choice here is std::int_fast32_t.

For the sum and count of matching subarrays, we'll need to think about the extreme cases. Since the array may hold up to 20,000 elements, then the sum can be as large as ±1000 * 20000 = ±20,000,000. Again std::int_fast32_t is suitable here. For the number of subarrays, the extreme case would be an input of 20,000 zeros, and a target of zero, making ½ * 20000 * 10000 = 100,000,000 matching subarrays. Again, we can use std::int_fast32_t for this, but given that this is a count of elements, it's probably more appropriate to use an unsigned type: std::uint_fast32_t.

It's a good idea to give names to the types we'll use, so that it's clear what's going on in the code, and to make it easier for us to adapt it to changes in the constraints:

#include <cstdint>
#include <map>
#include <vector>

using element_type = int;
using target_type = std::int_fast32_t;
using count_type = std::uint_fast32_t;

count_type count_subarrays_matching_sum(const std::vector<element_type> &nums,
                                        target_type target)

Increment and decrement operators

It's a good habit to get used to using the prefix forms of ++ and -- when you don't use the result. For the integer types used here, the resulting code will be identical, but classes that overload these operators generally need to make a copy for the postfix form, making that less efficient. Example:

    ++prefix_sum[sum];

Range-based for

I get a warning due to the mismatched types in the for loop:

243843.cpp:14:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
     for (int index = 0; index < nums.size(); ++index) {
                         ~~~~~~^~~~~~~~~~~~~

Although this isn't a problem given that we know the size will be less than 20000 elements, it's easy to use the correct type for index. Even better, since we only use it for accessing the elements, we can eliminate the arithmetic there entirely:

for (auto element: nums) {
    sum += element;

With the above changes, I now have:

#include <cstdint>
#include <map>
#include <vector>

using element_type = int;
using target_type = std::int_fast32_t;
using count_type = std::uint_fast32_t;

count_type count_subarrays_matching_sum(const std::vector<element_type> &nums,
                                        target_type target)
{
    using sum_type = std::int_fast32_t;

    // Maps each prefix sum to the number of times previously seen
    std::map<sum_type, count_type> prefix_sum;

    sum_type sum = 0;
    count_type matched_count = 0;

    ++prefix_sum[0];
    for (auto element: nums) {
        sum += element;
        matched_count += prefix_sum[sum - target];
        ++prefix_sum[sum];
    }

    return matched_count;
}

Generic interface

Slightly more advanced, we can consider accepting a pair of iterators instead of a std::vector. This allows the use of other containers without conversion.

Significantly, it also allows us to read from a stream iterator without having to store all the values at once, which is a useful technique for larger problems with a single-pass algorithm such as this.

Here's what that would look like (using std::enable_if, but it's somewhat easier to read if your compiler supports Concepts):

#include <cstdint>
#include <iterator>
#include <map>
#include <type_traits>
#include <vector>

using element_type = int;
using target_type = std::int_fast32_t;
using count_type = std::uint_fast32_t;

template<typename Iter, typename EndIter>
std::enable_if_t<std::is_same_v<element_type, typename std::iterator_traits<Iter>::value_type>, count_type>
count_subarrays_matching_sum(Iter first, EndIter last, target_type target)
{
    using sum_type = std::int_fast32_t;

    // Maps each prefix sum to the number of times previously seen
    std::map<sum_type, count_type> prefix_sum;

    sum_type sum = 0;
    count_type matched_count = 0;

    ++prefix_sum[0];
    for (auto it = first;  it != last;  ++it) {
        sum += *it;
        matched_count += prefix_sum[sum - target];
        ++prefix_sum[sum];
    }

    return matched_count;
}

count_type count_subarrays_matching_sum(const std::vector<element_type> &nums,
                                        target_type target)
{
    return count_subarrays_matching_sum(nums.begin(), nums.end(), target);
}
\$\endgroup\$
5
  • 1
    \$\begingroup\$ You might want to add something about std::span to your types part. \$\endgroup\$ Nov 5, 2020 at 11:36
  • 2
    \$\begingroup\$ I hadn't even considered std::span, and I don't actually see where one would be useful here. What were you suggesting? As an alternative to the std::vector of inputs? If so, then it probably belongs in the "Generic interface" section instead. \$\endgroup\$ Nov 5, 2020 at 11:57
  • 1
    \$\begingroup\$ Yes, that's the better place. \$\endgroup\$ Nov 5, 2020 at 12:01
  • 1
    \$\begingroup\$ Probably not a good choice for the interface: einpoklem recommends "Don't use it in code that could just take any pair of start & end iterators, like std::sort, std::find_if, std::copy and all of those super-generic templated functions." \$\endgroup\$ Nov 5, 2020 at 12:06
  • 1
    \$\begingroup\$ If you want to template it, sure. But that would be an additional step further. \$\endgroup\$ Nov 5, 2020 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.