| Random Link ¯\_(ツ)_/¯ | ||
| Jun 6, 2026 | » | Of [Non]Overlapping Intervals
3 min; updated Jun 6, 2026
Merge Overlapping IntervalsProblem Statement: Merge Overlapping IntervalsGiven an integer array Solution: Sort by Start Time and then Linear ScanLike
Minimum Size Subarray Sum
, contiguity hints at a linear scan being useful. If we sort |
| Jun 3, 2026 | » | Earliest Finish Time for Land and Water Rides
2 min; updated Jun 3, 2026
Problem StatementThere are \(L\) possible land rides and \(W\) possible water rides, with \(1 \le L, W \le 5 \times 10^4\). A tourist must experience exactly one ride from each category, in either order. A ride may be started at its opening time or any later moment. Immediately after finishing one ride, the tourist may board the other if it’s already open or wait until it opens. Return the earliest possible time at which the tourist can finish both rides. ... |
| Jun 1, 2026 | » | Minimum Cost of Buying Candies with Discount
2 min; updated Jun 1, 2026
The customer can choose any candy to takeaway for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought. Find the minimum cost of buying all the candies. Implementation: Sort then TraverseWhy is sorting in descending order and then skipping every 3rd candy optimal? A proof in two steps: ... |
| May 28, 2026 | » | Two Sum
3 min; updated May 28, 2026
Problem DescriptionGiven a 1-indexed array of integers that is sorted in non-decreasing order, find
two numbers such that they add up to a Solution: Linear Scan with Binary SearchAt its core, the problem is a binary search one. Given \(a\), find \(b = t -
a\) in the right side of |
| May 28, 2026 | » | Remove Duplicates from Sorted Array
1 min; updated May 28, 2026
Given a sorted integer array, remove some duplicates in-place such that each unique element appears at most twice. Maintain the relative order of the elements. If there are \(k\) elements after removing the duplicates, the first \(k\) elements of the array should hold the final result. This a two-pointer problem, where we have a tortoise and a hare. Establishing an
invariant that must be maintained throughout the array is useful to avoid
tripping up on index arithmetic. In this case, let |
| May 27, 2026 | » | Merging Sorted Arrays
1 min; updated May 27, 2026
Merge Sorted Arrays In-Place With BufferYou are given two integer arrays We don’t want to use extra \(\mathcal{O}(m + n)\) space. Traversing |
| May 27, 2026 | » | Majority Element in Array
3 min; updated May 27, 2026
Given an array of size \(N\), return the element that appears more than \(\lfloor N/2 \rfloor\) times. Solve the problem in \(\mathcal{O}(N)\) time and \(\mathcal{O}(1)\) space. Solving this in \(\mathcal{O}(N)\) time precludes sorting as that takes \(\mathcal{O}(N\ logN)\) time. Using \(\mathcal{O}(1)\) space precludes having a dictionary of frequencies. What is special about a frequency that is \(> \lfloor N/2 \rfloor\)? What kind of arithmetic would such a value survive? In a sorted array, a number that appears \(> \lfloor N/2 \rfloor\) times is also the median. How can we compute the median of an unsorted array in \(\mathcal{O}(N)\) time and \(\mathcal{O}(1)\) space? Scratch that, the median is a more general problem as the frequency need not be \(> \lfloor N/2 \rfloor\). ... |
| Aug 1, 2022 | » | K-th Smallest Element in Sorted Matrix
5 min; updated Aug 1, 2022
It’s not guaranteed that Using a priority queue that holds the \(K\) smallest elements does not work because the memory usage is \(O(K)\), where \(K\) can be any value in \([1, N^2]\). Furthermore, that doesn’t take into account that the rows and columns are already sorted. ... |
Writing the above algorithm felt right, but I couldn’t prove why it was optimal.