Sliding Window Technique - Part 7

-
There is usually one caveat on sliding window approaches: usually after the main loop, you still need to make one extra check for the very last case. Treat it as a corner case, albeit critical for the correctness of the code. Talking about this line here. Code is down below, cheers, ACC.


2461. Maximum Sum of Distinct Subarrays With Length K
Medium

You are 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, and
  • All the elements of the subarray are distinct.

Return the maximum subarray sum of all the subarrays that meet the conditions. If no subarray meets the conditions, return 0.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [1,5,4,2,9,9,9], k = 3
Output: 15
Explanation: The subarrays of nums with length 3 are:
- [1,5,4] which meets the requirements and has a sum of 10.
- [5,4,2] which meets the requirements and has a sum of 11.
- [4,2,9] which meets the requirements and has a sum of 15.
- [2,9,9] which does not meet the requirements because the element 9 is repeated.
- [9,9,9] which does not meet the requirements because the element 9 is repeated.
We return 15 because it is the maximum subarray sum of all the subarrays that meet the conditions

Example 2:

Input: nums = [4,4,4], k = 3
Output: 0
Explanation: The subarrays of nums with length 3 are:
- [4,4,4] which does not meet the requirements because the element 4 is repeated.
We return 0 because no subarrays meet the conditions.

 

Constraints:

  • 1 <= k <= nums.length <= 105
  • 1 <= nums[i] <= 105
Accepted
14,455
Submissions
44,090

public long MaximumSubarraySum(int[] nums, int k)
{
    //Sliding window approach
    long maxSum = 0;
    long currentSum = 0;
    Hashtable uniqueElements = new Hashtable();
    for (int i = 0; i < nums.Length; i++)
    {
        if (i < k)
        {
            if (!uniqueElements.ContainsKey(nums[i])) 
                uniqueElements.Add(nums[i], 0);
            uniqueElements[nums[i]] = (int)uniqueElements[nums[i]] + 1;
            currentSum += nums[i];
        }
        else
        {
            maxSum = (uniqueElements.Count == k && currentSum >= maxSum) ? currentSum : maxSum;

            int firstVal = nums[i - k];
            if (uniqueElements.ContainsKey(firstVal))
            {
                uniqueElements[firstVal] = (int)uniqueElements[firstVal] - 1;
                if ((int)uniqueElements[firstVal] <= 0) 
                    uniqueElements.Remove(firstVal);
                currentSum -= firstVal;
            }
            if (!uniqueElements.ContainsKey(nums[i])) 
                uniqueElements.Add(nums[i], 0);
            uniqueElements[nums[i]] = (int)uniqueElements[nums[i]] + 1;
            currentSum += nums[i];
        }
    }

    //Last, corner case
    maxSum = (uniqueElements.Count == k && currentSum >= maxSum) ? currentSum : maxSum;

    return maxSum;
}

Comments

Post a Comment

Popular posts from this blog

Standard Priority Queue IX: Vowels Frequency

-
Tally the frequency of the vowels. Push that into a pQueue, the caveat is when the frequencies are the same, you need to keep track of the first occurrence of each vowel and do some math to insert into the priority queue with the right order. After that, it is just dequeuing and inserting into the proper places. Use StringBuilder to avoid unnecessary string allocations. Code is down below, cheers, ACC. Sort Vowels by Frequency - LeetCode You are given a string  s  consisting of lowercase English characters. Rearrange only the  vowels  in the string so that they appear in  non-increasing  order of their frequency. If multiple vowels have the same  frequency , order them by the position of their  first occurrence  in  s . Return the modified string. Vowels are  'a' ,  'e' ,  'i' ,  'o' , and  'u' . The  frequency  of a letter is the number of times it occurs in the string.   Example 1: Input:   ...
Read more

The Power Sum, a recursive problem by HackerRank

-
Image
Another one by HackerRank:  https://www.hackerrank.com/challenges/the-power-sum : Find the number of ways that a given integer,  , can be expressed as the sum of the   power of unique, natural numbers. Input Format The first line contains an integer  .  The second line contains an integer  . Constraints Output Format Output a single integer, the answer to the problem explained above. Sample Input 0 10 2 Sample Output 0 1 Explanation 0 If   and  , we need to find the number of ways that   can be represented as the sum of squares of unique numbers. This is the only way in which   can be expressed as the sum of unique squares. Sample Input 1 100 2 Sample Output 1 3 Explanation 1 Sample Input 2 100 3 Sample Output 2 1 Explanation 2  can be expressed...
Read more

Binary Search to Find Next Greater Element V

-
You can use the .BinarySearch method of List<T>. It works well, there is a bit of a trick that you need to do when the return index is negative (just assign it to its complement, ~index). No need to perform the Binary Search "by hand" anymore. Achieves a good NLogN, fast solution. LC suggests a Tree to be used but this approach (two lists, one for even, one for odd) works well. Code is down below, cheers, ACC. Count Smaller Elements With Opposite Parity - LeetCode You are given an integer array  nums  of length  n . The  score  of an index  i  is defined as the number of indices  j  such that: i < j < n nums[j] < nums[i] nums[i]  and  nums[j]  have different parity (one is even and the other is odd). Return an integer array  answer  of length  n , where  answer[i]  is the score of index  i .   Example 1: Input:   nums = [5,2,4,1,3] Output:   [2,1,2,0,0] Explanation: Fo...
Read more