Posts

Standard Priority Queue V: PQueue as a Sorting Mechanism

-
Image
Priority Queues can be used as a standard NLogN sorting mechanism. Usually it isn't used as sorting due to the extra space required for the heap, but in terms of execution time it is as efficient as MergeSort for the worst case and even better than QuickSort on some cases. If you have a handy implementation of PQueue, don't be afraid of using it for sorting. Problem below requires a sorting of the elements based on the X-coordinate, followed by a linear scanning counting the number of rectangles. PQueue comes to the rescue here. Code is down below, cheers, ACC. Minimum Rectangles to Cover Points - LeetCode 3111. Minimum Rectangles to Cover Points Medium 47 2 Add to List Share You are given a 2D integer array  points , where  points[i] = [x i , y i ] . You are also given an integer  w . Your task is to  cover   all  the given points with rectangles. Each rectangle has its lower end at some point  (x 1 , 0)  and its upper end at some point  (x 2 , y 2 ) , where  x 1  <= x 2 , 
Post a Comment
Read more

Project Euler: Pisano Periods

-
Image
It has been a while since I had solved a PE problem. This one is simple, difficulty is 5%. As always I cannot share the solution or full code due to the rules of engagement with PE, but I can share the overall approach: 1/ Figure out a way to quickly find the Pisano Period. Hint: AI is your friend, so is Google or Bing 2/ Brute force it up to 1B. Takes a couple of minutes Cheers, ACC #853 Pisano Periods 1 - Project Euler
Post a Comment
Read more

Variation of the longest increasing subsequence algorithm

-
Image
This problem requires a solution similar to the longest increasing subsequence one. Basically on each step you either reset the current streak or increments it, adding the value to the return value. Code is down below, cheers, ACC. Count Alternating Subarrays - LeetCode 3101. Count Alternating Subarrays Medium 150 7 Add to List Share You are given a  binary array   nums . We call a  subarray   alternating  if  no  two  adjacent  elements in the subarray have the  same  value. Return  the number of alternating subarrays in  nums .   Example 1: Input:   nums = [0,1,1,1] Output:   5 Explanation: The following subarrays are alternating:  [0] ,  [1] ,  [1] ,  [1] , and  [0,1] . Example 2: Input:   nums = [1,0,1,0] Output:   10 Explanation: Every subarray of the array is alternating. There are 10 possible subarrays that we can choose.   Constraints: 1 <= nums.length <= 10 5 nums[i]  is either  0  or  1 . Accepted 26,802 Submissions 47,966 public long CountAlternatingSubarrays(int[] num
Post a Comment
Read more