Scribd
Upload
50 views14 pages

Lecture 17 - Prefix Sum Leetcode

The document covers prefix sum problems in coding, explaining the concept of prefix sums and providing code examples for various problems. It includes solutions for problems such as calculating the minimum penalty for a shop, finding good days to rob a bank, and summing absolute differences in a sorted array. Each problem is accompanied by a brief explanation and the corresponding code implementation.

Uploaded by

moteom9021
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
50 views14 pages

Lecture 17 - Prefix Sum Leetcode

The document covers prefix sum problems in coding, explaining the concept of prefix sums and providing code examples for various problems. It includes solutions for problems such as calculating the minimum penalty for a shop, finding good days to rob a bank, and summing absolute differences in a sorted array. Each problem is accompanied by a brief explanation and the corresponding code implementation.

Uploaded by

moteom9021
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 14

DSA SERIES

- Learn Coding
Topic to be Covered today

Prefix Sum Problems


Lets start today’s Lecture
Prefix Sum
A prefix sum is an array (or sometimes a formula) that stores the
cumulative sum of a given array up to each index.

➢ Each element of the prefix sum array tells you the sum of all elements before (and including) that index.
Given an array: arr = [2, 4, 1, 3, 6]

We want to compute the sum from index i to j (inclusive) multiple times quickly.

vector<int> prefix(arr.size());
prefix[0] = arr[0];

for (int i = 1; i < arr.size(); i++) {


prefix[i] = prefix[i - 1] + arr[i];
}
Problem : 2483

Minimum Penalty for a Shop


Code

class Solution {
public:
int bestClosingTime(string customers) {
int n = customers.size();

vector<int> prefix(n+1,0); // No of N in 0 to j-1 index


vector<int> suffix(n+1,0); // No. of Y in j to n index

for(int i = 0;i<n;i++){
prefix[i+1] = prefix[i]+(customers[i]=='N'?1:0);
}

for(int i = n-1;i>=0;i--){
suffix[i]=suffix[i+1]+(customers[i]=='Y'?1:0);
}
int minPenalty = INT_MAX;
int bestHour = 0;

for(int i =0;i<=n;i++){
int penalty = prefix[i]+suffix[i];

if(penalty < minPenalty){


minPenalty = penalty;
bestHour = i;
}
}

return bestHour;
}
};
Problem : 2100

Find Good Days to Rob the bank


class Solution {
public:
vector<int> goodDaysToRobBank(vector<int>& security, int time) {
int n = security.size();

vector<int> prefix(n, 0);


vector<int> suffix(n, 0);

for (int i = 1; i < n; i++) {


if (security[i] <= security[i - 1]) {
prefix[i] = prefix[i - 1] + 1;
} else {
prefix[i] = 0;
}
}

for (int i = n - 2; i >= 0; i--) {


if (security[i] <= security[i + 1]) {
suffix[i] = suffix[i+1] + 1;
} else {
suffix[i] = 0;
}
}
vector<int> result;

for(int i = time ;i<n-time;i++){


if(prefix[i]>=time && suffix[i]>=time){
result.push_back(i);
}
}

return result;
}
};
Problem : 1685

Sum of Absolute Differences in a Sorted Array


class Solution {
public:
vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
int n= nums.size();

vector<int> ans;
vector<int> left(n,0);
vector<int> right(n,0);

for(int i = 1;i<n;i++){
left[i]=left[i-1]+nums[i-1];
}

for(int i = n-2;i>=0;i--){
right[i]=right[i+1]+nums[i+1];
}

for(int i = 0;i<n;i++){
int sum = abs(nums[i]*i - left[i]);
sum+= abs(right[i]-nums[i]*(n-i-1));

ans.push_back(sum);
}

return ans;
}
};
Learn coding

Thank you

You might also like