Start learning free

LESSON 254 OF 667 · NESTED LOOPS OVER GRIDS

Row Sums in C++: One Total per Row of a Grid

Practice Read the full explanation

Given a grid of integers grid, return a vector with the sum of each row, in the same order as the rows.

A grid is a table of numbers made of rows. Every row has the same number of values, one in each column. Rows are counted from the top and columns from the left, both starting at 0.

 

Example 1:

Input: grid = [[1, 2, 3],
               [4, 5, 6]]
Output: [6, 15]
Explanation: Row 0 adds up to 1 + 2 + 3 = 6 and row 1 to 4 + 5 + 6 = 15.

Example 2:

Input: grid = [[-1, -2],
               [-3, -4],
               [5, 5]]
Output: [-3, -7, 10]
Explanation: One sum per row, top to bottom. A row of negative numbers has a negative sum.

Example 3:

Input: grid = [[3],
               [1],
               [4]]
Output: [3, 1, 4]
Explanation: Every row has a single value, so each row's sum is that value.

 

Constraints:

  • grid has at least 1 row and at most 10 rows.
  • Every row has the same number of values, at least 1 and at most 10.
  • Every value is an integer between -1000 and 1000.
STEP 1 OF 7
    Ctrl + Enter to check

    C++ · NESTED LOOPS OVER GRIDS

    Row Sums in C++, explained

    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

    1. Create an empty vector<int> named sums. The row sums will be added one at a time.
    2. Loop over the rows with a range-based for, using a vector<int> named row. The loop runs once per row, from the top.
    3. Create total inside that loop, set to 0. It belongs to the current row only.
    4. Loop over the values of the row with an int named value. This inner loop visits the current row and nothing else.
    5. Add value to total. After the inner loop, total is the row's sum.
    6. 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.
    7. Return sums after 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. total is 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> row is a copy of each row. Writing const vector<int>& row reads 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_back inside 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 return inside 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].
    Keep going with C++650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free