Pankaj Tanwar
Published on

Running sum of 1D array + Richest Customer Wealth.

––– views

Honestly in the morning, i decided to solve this problem. I randomly picked it from array + easy filter. I was trying to find out its solution when ever I got some free time to think about this, during lunch or between meetings. BUT I soon realized that I have been cheated by leetcode. This problem is not an easy problem.

But I didn't want to just look at the discussion tab for a solution, just for the sake of my streak.

So, I decided to put this problem on hold as It's a really simple yet interesting problem. To compensate for it, I will solve two problems today.

Problem 1 of the day - Running Sum of 1d Array

Tag - Easy

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

That's a really nice problem. I remember solving it (when I started with programming) with some extra array and iterating the original to compute sum for each index. (Ahh, super slow and worst solution, I know).

But now I have a pretty clean and fast solution to this.

I will iterate only once and will keep on updating the sum for each index. So, for calculating sum for new index, I will just have to look at the previous index only.

If it sounds boring, here is the code -

class Solution {
public:
    vector<int> runningSum(vector<int>& nums) {
        for(int i=1;i<nums.size();i++) {
            nums[i] += nums[i-1];
        }
        return nums;
    }
};

Pretty straight forward. I checked out discussion tab too for something new, but seems everyone has this approach only. Cool.

No extra space and O(n) time.

Problem 2 of the day - Richest Customer Wealth

Tag - Easy

Just to simplify the problem statement, a 2D array is given. Each row represents money of a user, in each bank (column represents bank). I just need to find the wealth, richest customer has.

As, its pretty obvious to approach this problem. I will just iterate over the 2D array, row wise and keep track of the max wealth row-by-row.

Here is the code -

class Solution {
public:
    int maximumWealth(vector<vector<int>>& accounts) {
        int max_balance = INT_MIN;
        int total;
        for(auto row: accounts) {
            total = 0;
            for(auto col: row) {
                total += col;
            }
            max_balance = max(max_balance, total);
        }
        return max_balance;
    }
};

It's with no extra space (variables are not counted as extra space) and O(n2) time complexity.

It seems I am picking up very easy problems. Let's level up tomorrow.

You might like previous editions of my coding diary where I everyday solve a problem and share my thought process.

Tweet this article