Category: foundational_interview
-
LeetCode 621: Task Scheduler
link Note len(tasks)is the lower bound for interval count. If all tasks are distinct, scheduling them in any order achieves the lower bound. However, when some tasks are repeated, we may need to insert idle cycles to cool the CPU down. With repeated tasks, if possible, we should put two instances of the same task…
-
LeetCode 253: Meeting Rooms II
link We schedule meetings in order of their start times. If there is a free room, we use it or we declare a new room is required. Say we are trying to schedule the -th meeting and currently there are meeting rooms with earlier meetings scheduled. Which among these rooms would be the most likely…
-
LeetCode 759: Employee Free Time
link Pre-sort A single employee’s free times are the gaps between consecutive work intervals. For more than one employees, we can merge overlapping work intervals and have a list of disjoint work intervals across all employees. Then, free times once again would be the gaps between consecutive work intervals. Say there are employees and the…
-
LeetCode 424: Longest Repeating Character Replacement
link We can convert any characters to any other character. Say in a substring of s, the char has the most frequency. We should try matching other characters in the window to using replacements. In other words, as long as window_length – count_of[c] , the window is good. Longer windows can be good only if…
-
LeetCode 727: Minimum Window Subsequence
link Starting at each index of s1 we can try matching s2. Say len(s1) = and len(s2) = . Time: , space: . The window in s1 that contains s2 as a subsequence must have all characters of s2. So, to decrease the number of match_window() calls, we may first try finding the minimum window…
-
LeetCode 239: Sliding Window Maximum
link If we find that is bigger than all numbers in the current (sliding) window, we need to keep track of just from then on. With the above observation, we can maintain a queue of possible maxes for the current and future windows. The head of the queue will be the current max. Each number…
-
LeetCode 287: Find the Duplicate Number
link Here values in nums is a permutation of the indices. If we consider i and nums[i] as consecutive nodes of a linked list, we have a permutation of the indices in the linked list. Say nums[i] = 2 and nums[j] = 2. This creates a cycle. With fast and slow pointers we can find…
-
LeetCode 457: Circular Array Loop
link Since the array is circular, there is always a cycle. A loop is: For example, below, if we start from index 0, the direction changes at the hop . But within the cycle: , the direction does not change. So, we declare it has a loop. Starting from each index we can check the…
-
LeetCode 202: Happy Number
link We run until we see a repeated number and check if that is 1. Say is an digit number. So, . Let . The maximum value of is when digits are all ‘s. In other words, the maximum value of . Since , . So, one step of sum of digit squared reduces to…
-
LeetCode 1442: Count Triplets That Can Form Two Arrays of Equal XOR
link All triplets For all (i, j, k), we check if xor(i, j) = xor(j, k+1). Time: , space: . Prefix XOR Say XOR(i, j) represents the xor of the numbers in the sublist nums[i : j+1], then XOR(i, j) = XOR(0, j) XOR(0, i-1). So, we could precompute xor’s of prefixes and avoid computing…
unreasonably effective 