Problem overview
The function rowSums receives grid, a vector<vector<int>>, and returns a vector<int> that holds the sum of each row, in the same order as the rows. The grid is a table: the outer vector holds the rows, and every row has the same number of values.
For [[1, 2, 3], [4, 5, 6]] the result is [6, 15]. For [[-1, -2], [-3, -4], [5, 5]] it is [-3, -7, 10]. For [[3], [1], [4]], where every row has one value, it is [3, 1, 4].
Approach: a fresh total for every row
The result has one number per row, so the function loops over the rows once. For each row it needs the sum of that row alone. That calls for a second, inner loop over the row's values and a total that starts at 0 for every row. Once the inner loop ends, the total is complete, and it is appended to the result.
The placement of the total matters. If it were created before the outer loop, it would keep growing across rows, and each result would include all the rows above it. Declaring it inside the outer loop gives each row a new variable that starts at 0.
Following the first example: for row [1, 2, 3], total goes 1, 3, 6 and 6 is appended. For row [4, 5, 6], a new total starts at 0 and goes 4, 9, 15, and 15 is appended. The result is [6, 15].
Step by step
- Create an empty
vector<int>namedsums. The row sums will be added one at a time. - Loop over the rows with a range-based
for, using avector<int>namedrow. The loop runs once per row, from the top. - Create
totalinside that loop, set to 0. It belongs to the current row only. - Loop over the values of the row with an
intnamedvalue. This inner loop visits the current row and nothing else. - Add
valuetototal. After the inner loop,totalis the row's sum. - Append the total with
sums.push_back(total), after the inner loop but still inside the outer one. Appending keeps the sums in row order. - Return
sumsafter the outer loop. Returning inside it would send back only the first row's sum.
The solution in C++
class Solution {
public:
vector<int> rowSums(vector<vector<int>> &grid) {
vector<int> sums;
for (vector<int> row : grid) {
int total = 0;
for (int value : row) {
total += value;
}
sums.push_back(total);
}
return sums;
}
};
C++ details:
- Scope. A variable declared inside a loop body exists only during one turn of that loop.
totalis created and set to 0 at the start of every turn, and it disappears at the end. That is why the sums can't leak from one row to the next. - Returning a vector.
return sums;hands the whole vector to the caller. C++ moves it out rather than copying it, so returning a local vector by value is cheap. - Copies of the rows.
vector<int> rowis a copy of each row. Writingconst vector<int>& rowreads the row in place without the copy, and the result is the same. - Row lengths. Each row is looped over using its own length, so the function does not need to know the number of columns.
Complexity
With R rows and C columns, every cell is visited once, so the time is O(R * C). The result holds R numbers, so the extra space is O(R), not counting the row copy.
Edge cases and common mistakes
- Total declared outside the outer loop. For
[[1, 2, 3], [4, 5, 6]], the second result would be 21 instead of 15, since the total would still hold the first row's 6. - Appending in the wrong place. A
push_backinside the inner loop would add a running total after every value, giving more numbers than there are rows. - Single column.
[[3], [1], [4]]gives[3, 1, 4]: each row's sum is its only value. - Negative values. A row of negatives has a negative sum, such as -3 for
[-1, -2]. - Returning too early. A
returninside the outer loop produces one sum only.
Testing
[[1, 2, 3], [4, 5, 6]]gives[6, 15].[[-1, -2], [-3, -4], [5, 5]]gives[-3, -7, 10].[[3], [1], [4]]gives[3, 1, 4].
