Sliding Window Technique - Part 14

-

A bit of vintage coding, no GAI involved. This is a sliding window problem, it is a bit tricky because you have to maintain not only the numbers in the candidate subarray but also the sum of pairs in that subarray, so two different data structures (I used hash tables but you can use other dictionary data structures) to keep this information. You need to update both of them accordingly when moving either the right pointer or the left one. Complexity is N^2 (N==1000) however the usage of untyped hash tables is slowing down the constant significantly, there are other ways especially given that the numbers in the array are small-bounded. Code is down below, cheers, ACC.


Longest Subarray With Restricted Pair Sums - LeetCode

You are given an integer array nums.

A nums[l..r] is valid if there are no three distinct indices i, j, and k such that l <= i, j, k <= r and:

  • nums[i] + nums[j] == nums[k]

Return the maximum length of a valid subarray of nums.

 

Example 1:

Input: nums = [2,3,5,3,2,1]

Output: 3

Explanation:

Consider the subarray [3, 5, 3]. The pairs of elements at distinct indices have the following sums:

  • 3 + 5 = 8
  • 3 + 3 = 6, using the two different occurrences of 3
  • 5 + 3 = 8

None of these sums is an element at the remaining index, so the subarray is valid.

Every subarray of length 4 contains 2, 3, and 5 at distinct indices, where 2 + 3 = 5. Therefore, no longer valid subarray exists, and the answer is 3.

Example 2:

Input: nums = [3,4,5,6]

Output: 4

Explanation:

The sums obtained from every pair of elements at distinct indices are 7, 8, 9, 9, 10, and 11. None of these values appears at the remaining index, so the entire array is valid.

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 500

public class Solution {
    public int MaxSubarray(int[] nums)
    {
        int retVal = 0;
        int left = 0;
        int right = 0;

        Hashtable sumOfPairsInSubarray = new Hashtable();

        Hashtable numbersInSubarray = new Hashtable();
        numbersInSubarray.Add(nums[left], 1);
        retVal = 1;
        right++;
        while (right < nums.Length)
        {
            bool validSubArray = true;
            if (sumOfPairsInSubarray.Contains(nums[right]))
            {
                validSubArray = false;
            }
            else
            {
                for (int i = left; i < right; i++)
                {
                    int sum = nums[i] + nums[right];
                    if (numbersInSubarray.Contains(sum) || sum == nums[right])
                    {
                        validSubArray = false;
                        break;
                    }
                }
            }
            if (validSubArray)
            {
                retVal = Math.Max(retVal, right - left + 1);

                if (!numbersInSubarray.Contains(nums[right])) numbersInSubarray.Add(nums[right], 0);
                numbersInSubarray[nums[right]] = (int)numbersInSubarray[nums[right]] + 1;

                for (int i = left; i < right; i++)
                {
                    int sum = nums[i] + nums[right];
                    if (!sumOfPairsInSubarray.Contains(sum)) sumOfPairsInSubarray.Add(sum, 0);
                    sumOfPairsInSubarray[sum] = (int)sumOfPairsInSubarray[sum] + 1;
                }

                right++;
            }
            else
            {
                numbersInSubarray[nums[left]] = (int)numbersInSubarray[nums[left]] - 1;
                if ((int)numbersInSubarray[nums[left]] == 0)
                    numbersInSubarray.Remove(nums[left]);

                for (int i = left + 1; i < right; i++)
                {
                    int sum = nums[left] + nums[i];
                    if (sumOfPairsInSubarray.Contains(sum))
                    {
                        sumOfPairsInSubarray[sum] = (int)sumOfPairsInSubarray[sum] - 1;
                        if ((int)sumOfPairsInSubarray[sum] == 0)
                            sumOfPairsInSubarray.Remove(sum);
                    }
                }

                left++;
            }
        }

        return retVal;
    }
}

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

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

Simulation: Build Generations

-
This was a very interesting problem in my opinion. It is a classic exercise in simulation, especially related to population growth. The constraints are small enough that you can brute-force and you'll be fine. Some techniques worth mentioning: 1/ Use a hash set for quick verification whether a point is in the generation 2/ Hash using the boundaries - using 7 as a seed works, hence x*7*7 + y*7 + z is a solid hash without the worry of overflowing 3/ Use two lists for generations: current and next 4/ Build next generation using an N^2 approach (it is OK since N = 6) 5/ Prune using the fact that the points in the next generation always have smaller numbers (due to the floor((a+b)/2)), hence if ever any of the indexes of your target is larger than the largest corresponding index in the current generation, you can safely assume that there won't be a solution. Also, prune using the fact that if the next generation isn't larger than the previous one, no solution will be found Code ...
Read more