TLDR

1. Welcome!

2. 2461. Maximum Sum of Distinct Subarrays With Length K

3. Self-Gaslight of the week

4. Hacks of the week

LeetCode problem

Day 29: 2461. Maximum Sum of Distinct Subarrays With Length K

Given an integer array nums and an integer k. 

Find the maximum subarray sum of all the subarrays of nums that meet the following conditions:

* The length of the subarray is k

* All the elements of the subarray are distinct.

Return the maximum subarray sum of all the subarrays that meet the conditions. 

Before we dive in,

What would be our naive solution?

If your answer was finding all of the subarrays, you are correct! But you like expensive things. And I’m cheap, so let’s see an optimized solution.

The clue to identifying that it’s a sliding window problem is that you don’t have to compute the sum of each subarray; you can compute the next subarray by modifying any limit (Left or Right pointer) of the previous subarray.

Given a length k, we can identify this as a fixed-size window problem.

Now that we got some clues…

Let’s dive in 🤿 :

We can start by defining the variables that we are going to use.

• currentSum: Stores the sum of the elements in the current window.

• maxSum: Holds the maximum sum of any subarray that meets our conditions.

• unique: A set used to ensure the subarray contains only distinct values.

• left: A pointer indicating the start of the window.

• right: A pointer indicating the end of the window.

  The sliding window technique involves iterating through our array using the left and right pointers. right will sliiide through the array (iterate with a for loop).

At each step of the iteration, we add the current value to currentSum and the value right to unique.

In each iteration, we check if the element at right is already in unique or if the size of unique exceeds k

If either of these conditions is true, we need to remove the unused values and increase our left pointer.

currentSum = currentSum-nums[l]; 
unique.erase(nums[l]);
l++;

At each step of the iteration, we need to check if the size of unique is k, if it is time to update our value maxSum .

currentSum = currentSum-nums[l]; 
unique.erase(nums[l]);
l++;

Once we are done iterating through our array, we return maxSum , which will hold our answer.

Let’s set an example:

Final Answer:

long long maximumSubarraySum(vector<int>& nums, int k) {
        long long maxSum =0; 
        long long currentSum=0; 
        set<int>unique; 
        int l=0; 
        for(int r=0; r<nums.size();r++){
            while(unique.contains(nums[r])|| unique.size()==k){
                    currentSum = currentSum-nums[l]; 
                    unique.erase(nums[l]);
                    l++;
            }
                unique.insert(nums[r]);
                currentSum = currentSum+nums[r]; 
                if(unique.size()==k){
                    maxSum = max(maxSum,currentSum); 
                }     
        }
        return maxSum; 
        
        }

Self-gaslight of the week

I truly believe you can gaslight yourself to success.

1. Read what your idols are reading, and find what they are reading here!!!

2. You're only as good as your competition. I recently listened to a podcast with Roger Federer, and you'd be surprised to learn who cried the most when he retired.

Hacks of the week

1. Share the questions you were asked in your interviews with your friends, and they'll likely share theirs with you in return.

2. KEEP TRACK OF ALL OF THE LEET CODE PROBLEMS YOU DO!!!!!!!!