Showing posts from May, 2021

Two Pointers for a Linear Solution V

Yet another hot-off-the-press problem requiring a two-pointers approach. Keep track of a pointer for the encoded1 and one for encoded2. As you traverse the arrays, make a decision on which one to add, and how to add, based on the equality or inequality of the frequencies. At that point, change the frequency of the "larger" array. When you add to the output list, just make sure to check against the "tail" of the list for the same frequency, in which case, merge them. Code is down below, cheers, ACC. Product of Two Run-Length Encoded Arrays - LeetCode 1868. Product of Two Run-Length Encoded Arrays Medium 3 0 Add to List Share Run-length encoding  is a compression algorithm that allows for an integer array  nums  with many segments of  consecutive repeated  numbers to be represented by a (generally smaller) 2D array  encoded . Each  encoded[i] = [val i , freq i ]  describes the  i th  segment of repeated numbers in  nums  where  val i  is the value that is repeated  fr

850 problems solved - XOR & subsets

This is my 850th problem solved on LC. It involves XOR and subsets. I'm sure there is a better way to do it but since the constraints are very small, a quick way was to generate all the subsets (standard iterative (not recursive!) code) and perform the respective XOR operations. Works well. Problem and code are down below - cheers! ACC. Sum of All Subset XOR Totals - LeetCode 1863. Sum of All Subset XOR Totals Easy 75 7 Add to List Share The  XOR total  of an array is defined as the bitwise  XOR  of  all its elements , or  0  if the array is  empty . For example, the  XOR total  of the array  [2,5,6]  is  2 XOR 5 XOR 6 = 1 . Given an array  nums , return  the  sum  of all  XOR totals  for every  subset  of  nums .  Note:  Subsets with the  same  elements should be counted  multiple  times. An array  a  is a  subset  of an array  b  if  a  can be obtained from  b  by deleting some (possibly zero) elements of  b .   Example 1: Input: nums = [1,3] Output: 6 Explanation: The 4 subset

Trie or HashTable?

Problems like this one can be solved with a Trie or Hashtable. The former is more "elegant" and uses less space, so it is preferred. The latter is an easier implementation (IMO). The following problem was solved using the Hashtable approach:  Longest Word With All Prefixes - LeetCode 1858. Longest Word With All Prefixes Medium 16 1 Add to List Share Given an array of strings  words , find the  longest  string in  words  such that  every prefix  of it is also in  words . For example, let  words = ["a", "app", "ap"] . The string  "app"  has prefixes  "ap"  and  "a" , all of which are in  words . Return  the string described above. If there is more than one string with the same length, return the  lexicographically smallest  one, and if no string exists, return  "" .   Example 1: Input: words = ["k","ki","kir","kira", "kiran"] Output: "kiran" Explan

Don't be ashamed of N^2

Easy problems on LeetCode are usually easy for a simple reason: you can solve them in polynomial time, most of the time in N^2, without worrying about the constraints since they are small. At the same time, there are probably better than N^2 solutions, but my advise is, if you can solve in N^2, and the N is super small, like 100, don't be ashamed of N^2. There is a great saying: "never let the great be the enemy of the good, and never let the good be the enemy of done ". Get it done. Problem is here, and code is down below. Cheers, ACC. Maximum Population Year - LeetCode 1854. Maximum Population Year Easy 72 16 Add to List Share You are given a 2D integer array  logs  where each  logs[i] = [birth i , death i ]  indicates the birth and death years of the  i th  person. The  population  of some year  x  is the number of people alive during that year. The  i th  person is counted in year  x 's population if  x  is in the  inclusive  range  [birth i , death i  - 1] . Note

Seat Manager == Priority Queue

This problem just requires a direct implementation of a Priority Queue, take a look:  Seat Reservation Manager - LeetCode 1845. Seat Reservation Manager Medium 54 6 Add to List Share Design a system that manages the reservation state of  n  seats that are numbered from  1  to  n . Implement the  SeatManager  class: SeatManager(int n)  Initializes a  SeatManager  object that will manage  n  seats numbered from  1  to  n . All seats are initially available. int reserve()  Fetches the  smallest-numbered  unreserved seat, reserves it, and returns its number. void unreserve(int seatNumber)  Unreserves the seat with the given  seatNumber .   Example 1: Input ["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"] [[5], [], [], [2], [], [], [], [], [5]] Output [null, 1, 2, null, 2, 3, 4, 5, null] Explanation SeatManager seatManager = new SeatManager